[알고리즘 / 백준] 7562 - 나이트의 이동

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

문제는 위와 같으며, 나이트가 한번씩 이동할 때마다 몇번째 이동인지와 해당 위치(x, y)를 배열 형태로 우선순위 큐에 저장한 뒤 저장된 위치가 도착 지점과 일치하는 경우 해당 위치까지 이동한 칸의 수(몇번째 이동인지)를 출력하여 문제를 해결할 수 있습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin
import heapq

# 나이트가 이동할 수 있는 위치 저장
dx = [-2, -2, -1, -1, 1, 1, 2, 2]
dy = [-1, 1, -2, 2, -2, 2, -1, 1]


def bfs(move, x, y):
    queue = []
    heapq.heappush(queue, [move, x, y])  # 우선 순위 큐를 생성 [지금까지 이동한 칸 수, x, y] 형태 저장
    visited[x][y] = 0  # 시작 위치까지 오는데 걸리는 칸 수는 0이므로 0저장

	# 이동할 수 있는 경우를 모두 확인하면서
    while queue:
        m, cx, cy = heapq.heappop(queue)  # 우선 순위 큐에서 '지금까지 이동한 칸 수'가 적은 순으로 pop

        if cx == ex and cy == ey:  # 현재 위치가 도착 위치와 같은 경우
            return m  # 현재 위치까지 이동한 칸 수를 반환

        for d in range(8):  # 나이트가 한번에 이동할 수 있는 위치를 모두 확인하면서
            nx = cx + dx[d]
            ny = cy + dy[d]

            if 0 <= nx < i and 0 <= ny < i:  # 다음 위치가 체스판 내에 존재하고
                if visited[nx][ny] == -1:  # 아직 방문하지 않은 경우라면
                    heapq.heappush(queue, [m + 1, nx, ny])  # [다음 위치까지 이동한 칸 수(현재 위치까지 이동한 칸 수 +1), 다음 x, 다음 y] 를 우선순위 큐에 저장
                    visited[nx][ny] = m + 1  # 다음 위치를 방문한 것으로 표시


t = int(stdin.readline())
for _ in range(t):
    i = int(stdin.readline())
    sx, sy = map(int, stdin.readline().split())  # 처음 나이트의 위치를 저장
    ex, ey = map(int, stdin.readline().split())  # 이동하고자 하는 칸을 저장

    visited = [[-1] * i for _ in range(i)]  # 각 위치를 방문했는지 확인할 이차원 배열 생성

    print(bfs(0, sx, sy))  # 처음 나이트의 위치를 파라미터로 넘겨 도착 지점까지 이동하는데 거치는 칸 수를 출력

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {

	// 나이트가 한번에 이동할 수 있는 위치 저장
    private static int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
    private static int[] dy = {-1, 1, -2, 2, -2, 2, -1, 1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            int[] start = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();  // 나이트의 시작 위치
            int[] end = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();  // 나이트가 이동하고자 하는 위치

			// 각 위치를 방문했는지 확인할 이차원 배열 생성
            int[][] visited = new int[n][n];
            for (int v = 0; v < n; v++) {
                Arrays.fill(visited[v], -1);
            }

			// 우선 순위 큐를 만들고 [해당 위치까지 몇번 이동하는지, 해당 위치의 x, 해당 위치의 y] 형태로 데이터를 저장하는데
            // '해당 위치까지 몇번 이동하는지' 를 기준으로 우선순위를 정하도록 선언
            PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] t1, int[] t2) {
                    return t1[0] - t2[0];
                }
            });
            queue.offer(new int[]{0, start[0], start[1]});  // 처음 나이트의 위치와 처음 위치까지 몇번 이동하는지(0)를 저장
            visited[start[0]][start[1]] = 0;  // 처음 위치까지 방문하는데 걸리는 이동칸을 저장

            while (!queue.isEmpty()) {
                int[] current = queue.poll();  // '해당 위치까지 몇번 이동하는지'가 가장 작은 위치부터 pop

                if (current[1] == end[0] && current[2] == end[1]) {  // 현재 위치가 도착 위치와 같은 경우 이동한 칸 수를 출력하고 해당 테스트 케이스 종료
                    System.out.println(current[0]);
                    break;
                }

				// 나이트가 이동할 수 있는 위치를 차례로 확인하면서
                for (int j = 0; j < 8; j++) {
                    int nx = current[1] + dx[j];
                    int ny = current[2] + dy[j];

                    if (nx >= 0 && nx < n && ny >= 0 && ny < n) {  // 체스판 범위 내에 있고
                        if (visited[nx][ny] == -1) {  // 아직 방문하지 않은 경우
                            queue.offer(new int[]{current[0] + 1, nx, ny});  // [다음 위치까지 몇번 이동하는지(현재 위치까지 몇번 이동하는지 + 1), 다음 위치 x, 다음 위치 y] 를 저장
                            visited[nx][ny] = current[0] + 1;  // 다음 위치를 방문한 것으로 표시
                        }
                    }
                }
            }
        }
    }
}