백준 7562 나이트의 이동 JAVA

solved.ac 티어 = 실버 2

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

7562번: 나이트의 이동

 

2178번과 같이 너비 탐색 기초 문제다.

 

1. 접근

 

테스트 케이스의 최대치가 나와있지는 않으나 체스판의 최대 크기인 300² 를 모두 밟아도 90,000으로 시간제한 걱정 없이 풀이에 접근하면 된다.

 

나이트의 이동 가능한 경로

그림 예제에 나와있듯 나이트의 이동 경로를 미리 배열로 짜둔다면 다음과 같다. (시계방향)

static int[][] dir = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};

입력 조건

문제에 나와있듯 나이트의 시작점에서 탐색을 시작하며 탐색이 종료되었을 때 목적지의 값을 출력해주면 끝이다.

 

2. 풀이

 

전역변수 및 input

static int N,T, startX, startY, goalX, goalY;
static int[][] dist;
static int[][] dir = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}}; // 나이트의 이동경로
public static void main(String[] args) throws IOException {
    T = Integer.parseInt(br.readLine());
    while (T --> 0) {
        N = Integer.parseInt(br.readLine());
        dist = new int[N][N];

        st = new StringTokenizer(br.readLine()); // 나이트의 시작 좌표
        startX = Integer.parseInt(st.nextToken());
        startY = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine()); // 나이트의 목적지 좌표
        goalX = Integer.parseInt(st.nextToken());
        goalY = Integer.parseInt(st.nextToken());

        solution();
    }
}

 

배열 초기화 및 BFS 호출

 

static void solution() {
    for (int i = 0; i < N; i++) {
        Arrays.fill(dist[i], -1); // 방문여부 체크를 위한 초기화
    }
    BFS(startX, startY);
    System.out.println(dist[goalX][goalY]); // 정답 출력
}

 

탐색

static void BFS(int x, int y) {
    Queue<Integer> Q = new LinkedList<>();
    Q.add(x);
    Q.add(y);
    dist[x][y] = 0; // 출발지에서는 카운트 하지 않는다

    while(!Q.isEmpty()) {
        x = Q.poll();
        y = Q.poll();

        for (int i = 0; i < 8; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue; // 배열범위 체크
            if (dist[nx][ny] != -1) continue; // 방문여부 체크
            dist[nx][ny] = dist[x][y] + 1; // 이동횟수 증가
            Q.add(nx);
            Q.add(ny);
        }
    }
}

 

3. 전체코드