[백준 JAVA] 7562 나이트의 이동, BFS(너비 우선 탐색)

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

7562번: 나이트의 이동

 

https://www.acmicpc.net/problem/2178 미로탐색 문제와 아주 유사하다. 

너비우선 탐색을 이용하여 이동위치의 값을 갱신해가면서 이동하여 값을 출력한다

큐에는 이동한 거리가 작은 순으로 들어있으므로 최소값을 만족한다.

 

<코드>

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static final StringBuilder sb = new StringBuilder();
    //이동가능한 방향
    private static final int[][] dir = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
    private static int[][] visited;
    private static int[] start;
    private static int[] end;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int TC = Integer.parseInt(br.readLine());
        while (TC-- > 0) {
            int sz = Integer.parseInt(br.readLine());
            visited = new int[sz][sz];

            StringTokenizer st = new StringTokenizer(br.readLine());
            start = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};

            st = new StringTokenizer(br.readLine());
            end = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
            
            sb.append(bfs()).append("\n");
        }
        System.out.println(sb);
    }

    //너비우선 탐색으로 해결
    private static int bfs() {
        if (start[0] == end[0] && start[1] == end[1]) return 0;

        Queue<Point> q = new LinkedList<>();
        q.add(new Point(start[0], start[1]));
        visited[start[0]][start[1]] = 1;

        while (!q.isEmpty()) {
            Point now = q.poll();

	    //도착한 경우
            if(now.x==end[0]&& now.y==end[1]) return visited[end[0]][end[1]] - 1;

	    //움직이고 난 위치 
            for (int i = 0; i < 8; i++) {
                int mvx = now.x + dir[i][0];
                int mvy = now.y + dir[i][1];
                
		//가능한 범위를 벗어난 경우
                if (mvx < 0 || visited.length <= mvx || mvy < 0 || visited.length <= mvy) continue;

		//이전에 방문하지 않은경우 이동위치의 값을 수정하고, 큐에 넣는다 
                if(visited[mvx][mvy]==0){
                    visited[mvx][mvy]=visited[now.x][now.y]+1;
                    q.add(new Point(mvx,mvy));
                }
            }
        }

        return -1;
    }
}