[문제] 백준 16948 데스나이트

www.acmicpc.net/problem/16948

16948번: 데스 나이트

풀이

 

BFS 문제다. 큐에다가 이동거리를 확인할 수 있도록 좌표와 이동거리가 포함된 배열을 넣도록 했다.

처음에 visited 처리를 아래 주석의 위치에다가 했다가 메모리 초과가 나서 큐에 삽입하는 시점으로 바꿨더니 문제가 풀렸다.

 

여기서 주의해야 할 케이스는 시작점과 목표점이 동일할 때이다. 

답을 0으로 먼저 처리 안하고 저 방식대로 실행하니까 0이 아닌 값이 나왔다.

public class BOJ_16948 {
	static int dx[] = { -2, -2, 0, 0, 2, 2 };
	static int dy[] = { -1, 1, -2, 2, -1, 1 };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine()); // 정사각 배열 크기

		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int r1 = Integer.parseInt(st.nextToken()); // 시작점 (r1,c1)
		int c1 = Integer.parseInt(st.nextToken());
		int r2 = Integer.parseInt(st.nextToken()); // 도착점 (r2,c2)
		int c2 = Integer.parseInt(st.nextToken());

		boolean isPossible = false; // (r1,c1) -> (r2, c2)로 도착할 수 있는지 확인하는 flag
		int ans = Integer.MAX_VALUE;// 도착할 수 있는 후보들 중 가장 최소 거리 찾기
		boolean[][] visited = new boolean[N][N]; // 해당 영역을 방문했는지 체크

		if (r1 == r2 && c1 == c2) { // 시작점과 도착점이 동일하면 0 반환 후 종료
			System.out.println(0);
			return;
		}
		// BFS
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] { r1, c1, 0 }); // 삽입할 원소: {시작 x, 시작 y, 이동 거리}

		while (!q.isEmpty()) {
			int[] curr = q.poll();
			int cx = curr[0]; // 현재 x좌표
			int cy = curr[1]; // 현재 y좌표
			int cnt = curr[2]; // 현재까지 이동한 거리
//			visited[nx][ny] = true;		=> 여기에서 방문 표시하니까 메모리 초과 나서 아래로 옮기니까 풀렸다.
			// 6방 탐색
			for (int i = 0; i < 6; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny]) {

					if (nx == r2 && ny == c2) { // 도착점이라면,
						ans = Math.min(ans, cnt + 1);// 지금까지 이동 거리 중 최소값 갱신해서 ans에 넣어주기
						isPossible = true; // 도착했으니 true
						break;
					}
					q.offer(new int[] { nx, ny, cnt + 1 }); // 이동한 거리 1 증가
					visited[nx][ny] = true; // 방문 표시
				}
			}
		}
		// 이동할 수 없다면 -1 반환,이동 가능하면 ans 반환
		if (!isPossible) {
			System.out.println(-1);
		} else {
			System.out.println(ans);
		}
	}

}