[백준 / JAVA] 7562. 나이트의 이동

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

7562번: 나이트의 이동

 

---

💻 풀이 결과

 

💯 최종 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Node {
	int r, c;

	Node(int r, int c) {
		this.r = r;
		this.c = c;
	}
}

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for (int tc = 0; tc < T; tc++) {
			int I = sc.nextInt();
			int[][] board = new int[I][I];

			int nowX = sc.nextInt();
			int nowY = sc.nextInt();

			int nextX = sc.nextInt();
			int nextY = sc.nextInt();

			Queue<Node> queue = new LinkedList<>();
			int cnt = 0;

			queue.add(new Node(nowY, nowX));
			board[nowY][nowX] = cnt;

			int[] dr = { -1, -2, -2, -1, 1, 2, 2, 1 };
			int[] dc = { -2, -1, 1, 2, -2, -1, 1, 2 };

			while (!queue.isEmpty()) {
				int size = queue.size();
				cnt++;

				for (int s = 0; s < size; s++) {
					Node curr = queue.poll();
					// 탈출 조건
					if (curr.r == nextY && curr.c == nextX) {
						queue.clear();
						System.out.println(board[curr.r][curr.c]);
						break;
					}

					for (int d = 0; d < 8; d++) {
						int nr = curr.r + dr[d];
						int nc = curr.c + dc[d];

						// 기저조건
						if (nr < 0 || nc < 0 || nr >= I || nc >= I) {
							continue;
						}
						if (board[nr][nc] > 0) {
							continue;
						}

						queue.add(new Node(nr, nc));
						board[nr][nc] = cnt;
					}
				}
			}

		}
	}
}

💢 틀린 이유

• dr, dc 배열을 잘못 설정하는 실수를 해서 계속 틀린 결과가 나왔다..
• nextY를 행으로, nextX를 열로 잡았는데, 처음 큐에 삽입할 때 (nowX, nowY)로 해서 행, 열 설정이 잘못되어 있었다.

💬 풀이 과정

• BFS를 돌리면서 8방 탐색을 하였다.
• 큐에 삽입을 할 때 보드판에 이동 횟수(cnt)를 저장한다.
• 방문 검사는 이동 횟수가 저장이 되어 있는지로 판별하였다.
• 큐에서 하나씩 꺼낼 때 도착지점이라면 큐를 비우고 이동 횟수(cnt)를 출력한다.

💡 깨달은 점

1. 사소한 실수

• 사소한 실수를 하지 않도록 설정을 잘해주어야 할 것 같다.