7562번-나이트의 이동

문제

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

---

접근방법

1) 접근 사고

1. 나이트의 이동 좌표에 대한 설정값을 구해줍니다.

2. bfs 탐색을 통해 나이트의 이동에 대한 탐색을 시작합니다.

3. 이때 1초당 걸리는 탐색의 경우의 수는 탐색을 진행할 때 queue의 크기와 같으므로 탐색을 시작할 때 큐의 크기만큼 탐색을 진행하고 시간을 1증가 시켜줍니다.

 

2) 시간 복잡도

O(V+E)

 

3) 실수

 

4) 배운점

 

5) PS

다른 문제풀이를 보니 INT형의 dists 이차원 배열을 사용해 초기에 값을 -1로 초기화해서 중복을 제어하는 형식의 코드도 있는거 같은데 시간이 있을때 다시 풀어봐야 할 거 같습니다.

 

---

정답 코드

#include<bits/stdc++.h>

using namespace std;

const int MAX = 305;
int t;
int r;
pair<int, int> start, goal;
bool visited[MAX][MAX];
int moveY[] = { -1, -2, -2, -1, 1, 2, 2, 1  };
int moveX[] = { -2, -1, 1, 2, -2, -1, 1, 2 };

int bfs(){
	queue<pair<int, int>> q;
	q.push(start);
	visited[start.first][start.second] = true;
	int count = 0;
	while (!q.empty()){
		int qSize = q.size();
		for (int i = 0; i < qSize; i++){
			int y = q.front().first;
			int x = q.front().second;
			q.pop();

			if (y == goal.first && x == goal.second){
				return count;
			}

			for (int d = 0; d < 8; d++){
				int ny = y + moveY[d];
				int nx = x + moveX[d];

				if (ny >= 0 && ny < r && nx >= 0 && nx < r){
					if (!visited[ny][nx]){
						q.push({ ny, nx });
						visited[ny][nx] = true;
					}
				}
			}
		}
		count++;
	}
	return count;
}

void pro(){
	memset(visited, false, sizeof(visited));
	int ans = bfs();
	cout << ans << "\n";
}

void input(){
	cin >> r;
	cin >> start.first >> start.second;
	cin >> goal.first >> goal.second;
}

int main(){
	cin >> t;
	while (t--){
		input();
		pro();
	}
}