[백준] 7562번 - 나이트의 이동 (Java)

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

1707번: 이분 그래프

 

 

<문제 분석>

1. BFS 탐색으로 최소이동거리를 구하는 문제이다.

2. TC가 여러개이므로 매번 맵을 초기화 해야 한다.

3. 누적거리는 map[][]에 탐색하면서 업데이트 한다.

4. 8방향으로 탐색이 가능하다.

 

<코드 구현>

import java.util.*;

/*
[백준] 7562번 - 나이트의 이동 (Java)
*/

public class Main {
    static int N, M;
    static int map[][];
    static int x1, y1, x2, y2;
    
    class Point {
        int x;
        int y;
        Point (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    void InputData() {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();
        map = new int[N][M];
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                map[i][j] = in.nextInt();
            }
        }
    }

    int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
    int BFS() {
        Queue<Point> Q = new LinkedList<Point>();
        Q.offer(new Point(x1, y1));//시작점 큐에 삽입

        while (!Q.isEmpty()) {
            Point tmp = Q.poll();
            for (int i=0; i<8; i++) {//8방향으로 탐색 시작
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                if (nx < 0 || nx >= M || ny < 0 || ny >= M) continue;//범위를 벗어나면 스킵
                if (map[nx][ny] != 0) continue;//이미 방문한 위치면 스킵
                Q.offer(new Point(nx, ny));//처음 방문한 곳이면 큐에 삽입
                map[nx][ny] = map[tmp.x][tmp.y] + 1;//누적거리+1해서 업데이트
            }
        }
        return map[x2][y2];//최종 목적지까지 저장된 거리 리턴
    }

    void Solve() {
    }

    static void PrintMap() {
        for (int i=0; i<M; i++) {
            for (int j=0; j<M; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }

	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        for (int i=0; i<N; i++) {
            M = in.nextInt();
            map = new int[M][M];
            x1 = in.nextInt();//시작점
            y1 = in.nextInt();
            x2 = in.nextInt();//도착점
            y2 = in.nextInt();
            if (x1 == x2 && y1 == y2) {//시작과 도착위치가 같으면 길이는 
                System.out.println(0);
            } else {
                System.out.println(m.BFS());
            }
        }
	}
}

 

<제출 결과>