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

문제 출처

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

문제 설명

나이트는 체스 말의 나이트처럼 움직인다.

2차원 좌표계에서 탐색하는 문제다.

문제 풀이

bfs로 해결한다.

코드

코드 해설

    public static void main(String[] args) {
        readInput();
        for (int tc = 0; tc < testCase; tc++) {
            int answer = bfs(tc);
            System.out.println(answer);
        }
    }

readInput()에서 모든 입력을 받는다.

테스트케이스만큼 bfs를 연산하고 결과를 출력한다.

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(knight[tc]);
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            if (current[0] == goal[tc][0] && current[1] == goal[tc][1]) {
                return map[current[0]][current[1]];
            }
            for (int d = 0; d < dr.length; d++) {
                int[] next = {current[0] + dr[d], current[1] + dc[d]};
                // System.out.println(Arrays.toString(next));
                if (inRange(next, side) && map[next[0]][next[1]] == 0) {
                    queue.offer(next);
                    map[next[0]][next[1]] = map[current[0]][current[1]] + 1;
                }
            }
        }

큐는 나이트의 좌표이고 map은 나이트가 몇번만에 이 좌표에 왔는 지를 담고있다.

모든 큐를 확인하며 목적지에 도착했다면 결과를 출력한다.

목적지가 아니라면 갈 수 있는 모든 좌표를 큐에 넣을 지 고려한다.

이미 한번 갔던 좌표라면 큐에 넣지 않는다.

map이 0이라면 처음 가는 좌표라는 뜻이므로 그 좌표를 큐에 넣으며 몇번의 이동만에 도착했는지 map에 담는다.

 

나이트의 시작 지점은 map 상에서 0이어야하지만 2번 이동 후에 2로 표기된다.

로직 상 중요하지 않으므로 무시하자.