[문제 링크](https://www.acmicpc.net/problem/7562)

성능 요약

메모리: 114744 KB, 시간: 380 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 6월 10일 16:22:02

문제 설명

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력 1

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1

5
28
0

설명

나이트의 이동문제를 해결 하기 위해 BFS 알고리즘을 사용하여 체스판에서 나이트가 이동할 수 있는 최소 횟수를 계산합니다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int I;
    static int x1, x2, y1, y2;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = {1, 2, 2, 1, -1, -2, -2, -1};
    static int[] dy = {2, 1, -1, -2, -2, -1, 1, 2};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());

        for (int i = 1; i <= T; i++) {
            I = Integer.parseInt(br.readLine());

            arr = new int[I][I];
            visited = new boolean[I][I];

            st = new StringTokenizer(br.readLine());
            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());

            bfs();

            sb.append(arr[x2][y2]).append("\n");
        }
        System.out.println(sb);
    }

    public static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x1, y1});
        visited[x1][y1] = true;

        while (!q.isEmpty()) {
            int[] now = q.poll();
            int nx = now[0];
            int ny = now[1];

            for (int i = 0; i < 8; i++) {
                int ox = nx + dx[i];
                int oy = ny + dy[i];

                if (ox >= 0 && oy >= 0 && ox < I && oy < I) {
                    if (!visited[ox][oy]) {
                        q.add(new int[]{ox, oy});
                        arr[ox][oy] = arr[nx][ny] + 1;
                        visited[ox][oy] = true;
                    }
                }
            }
        }
    }
}

세부 설명

변수 및 상수 정의

public class Main {
    static int I; // 체스판의 크기
    static int x1, x2, y1, y2; // 시작 위치(x1, y1)와 목표 위치(x2, y2)
    static int[][] arr; // 이동 횟수를 저장하는 배열
    static boolean[][] visited; // 방문 여부를 저장하는 배열
    static int[] dx = {1, 2, 2, 1, -1, -2, -2, -1}; // 나이트의 이동 방향 (x 좌표 변화량)
    static int[] dy = {2, 1, -1, -2, -2, -1, 1, 2}; // 나이트의 이동 방향 (y 좌표 변화량)
  • I는 체스판의 크기입니다.
  • x1, y1는 나이트의 시작 위치, x2, y2는 목표 위치입니다.
  • arr는 나이트가 각 칸에 도달하기까지의 이동 횟수를 저장합니다.
  • visited는 각 칸의 방문 여부를 저장합니다.
  • dx, dy 배열은 나이트가 이동할 수 있는 8가지 방향을 나타냅니다.

메인 메서드

public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    StringTokenizer st;
    int T = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수

    for (int i = 1; i <= T; i++) {
        I = Integer.parseInt(br.readLine()); // 체스판의 크기 입력

        arr = new int[I][I];
        visited = new boolean[I][I];

        st = new StringTokenizer(br.readLine());
        x1 = Integer.parseInt(st.nextToken());
        y1 = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        x2 = Integer.parseInt(st.nextToken());
        y2 = Integer.parseInt(st.nextToken());

        bfs(); // BFS 알고리즘 호출

        sb.append(arr[x2][y2]).append("\n"); // 목표 위치까지의 이동 횟수를 결과 문자열에 추가
    }
    System.out.println(sb); // 결과 출력
}
  • 테스트 케이스의 개수 T를 입력받습니다.
  • 각 테스트 케이스마다 체스판의 크기 I, 시작 위치, 목표 위치를 입력받습니다.
  • arr 배열과 visited 배열을 초기화합니다.
  • bfs 메서드를 호출하여 시작 위치에서 목표 위치까지의 최소 이동 횟수를 계산합니다.
  • 결과를 StringBuilder 객체에 저장하고, 모든 테스트 케이스가 끝난 후 결과를 출력합니다.

BFS 메서드

public static void bfs() {
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[]{x1, y1});
    visited[x1][y1] = true;

    while (!q.isEmpty()) {
        int[] now = q.poll();
        int nx = now[0];
        int ny = now[1];

        for (int i = 0; i < 8; i++) {
            int ox = nx + dx[i];
            int oy = ny + dy[i];

            if (ox >= 0 && oy >= 0 && ox < I && oy < I) {
                if (!visited[ox][oy]) {
                    q.add(new int[]{ox, oy});
                    arr[ox][oy] = arr[nx][ny] + 1;
                    visited[ox][oy] = true;
                }
            }
        }
    }
}
  • Queue를 사용하여 BFS 탐색을 수행합니다.
  • q.add(new int[]{x1, y1});를 통해 시작 위치를 큐에 추가하고, 해당 위치를 방문했다고 표시합니다.
  • 큐가 빌 때까지 반복하면서 현재 위치를 큐에서 꺼내고, 나이트가 이동할 수 있는 8가지 방향에 대해 새로운 위치를 계산합니다.
  • 새로운 위치가 체스판 범위 내에 있고 방문하지 않은 경우, 큐에 추가하고, 이동 횟수를 갱신하며, 방문 여부를 업데이트합니다.

1. 큐에서 현재 위치 꺼내기

int[] now = q.poll();
int nx = now[0]; // 현재 위치 x좌표
int ny = now[1]; // 현재 위치 y좌표
  • q.poll()은 큐에서 현재 위치를 꺼냅니다. now 배열에는 현재 나이트의 위치가 [nx, ny] 형태로 저장됩니다.
  • nx와 ny는 현재 위치의 x, y 좌표입니다.

2. 8가지 방향으로 이동 탐색

for (int i = 0; i < 8; i++) {
    int ox = nx + dx[i];
    int oy = ny + dy[i];
  • for (int i = 0; i < 8; i++)는 나이트가 이동할 수 있는 8가지 방향을 탐색하기 위해 8번 반복하는 반복문입니다.
  • dx와 dy 배열은 나이트가 이동할 수 있는 8가지 방향을 나타냅니다. 각 방향에 대해 이동 후의 새로운 좌표 (ox, oy)를 계산합니다.

나이트는 체스판에서 다음과 같은 8가지 방향으로 이동할 수 있습니다:

하나. (1, 2)
둘. (2, 1)
셋. (2, -1)
넷. (1, -2)
다섯. (-1, -2)
여섯. (-2, -1)
일곱. (-2, 1)
여덟. (-1, 2)

이 방향들을 dx와 dy 배열로 나타내면 다음과 같습니다:

dx = {1, 2, 2, 1, -1, -2, -2, -1}
dy = {2, 1, -1, -2, -2, -1, 1, 2}

이 배열을 사용해 새로운 위치를 계산할 수 있습니다. 예를 들어, dx[0]과 dy[0]은 첫 번째 방향 (1, 2)을 나타냅니다.

3. 새로운 위치가 유효한지 확인

if (ox >= 0 && oy >= 0 && ox < I && oy < I) {
  • ox와 oy가 체스판의 범위 내에 있는지 확인합니다. ox와 oy가 모두 0 이상이고, I보다 작은지 확인합니다. 이는 새로운 위치가 체스판 밖으로 나가지 않도록 하기 위함입니다.

4. 새로운 위치가 방문되지 않았는지 확인하고 큐에 추가

if (!visited[ox][oy]) {
    q.add(new int[]{ox, oy});
    arr[ox][oy] = arr[nx][ny] + 1;
    visited[ox][oy] = true;
}
  • 새로운 위치가 아직 방문되지 않았는지 확인합니다. 방문하지 않았다면 다음을 수행합니다:
    • q.add(new int[]{ox, oy});를 통해 새로운 위치를 큐에 추가합니다.
    • arr[ox][oy] = arr[nx][ny] + 1;을 통해 새로운 위치까지의 이동 횟수를 갱신합니다. 현재 위치 arr[nx][ny]에서 한 번 더 이동했으므로 +1을 해줍니다.
    • visited[ox][oy] = true;를 통해 새로운 위치를 방문했다고 표시합니다.

BFS 메서드 요약

  • for (int i = 0; i < 8; i++): 나이트가 이동할 수 있는 8가지 방향을 모두 탐색하기 위해 사용합니다.
  • dx와 dy 배열: 나이트가 이동할 수 있는 8가지 방향을 저장하고 있습니다.
  • ox와 oy 계산: 현재 위치에서 각 방향으로 이동한 새로운 위치를 계산합니다.
  • 범위 체크및 방문 여부 확인: 새로운 위치가 체스판 범위 내에 있는지 확인하고, 방문하지 않았으면 큐에 추가하고 이동 횟수를 갱신합니다.

BFS 핵심 동작

1. 큐 초기화 및 시작 위치 설정: 나이트의 시작 위치를 큐에 추가하고, 해당 위치를 방문했다고 표시합니다.
2. 반복문을 통한 탐색: 큐가 빌 때까지 반복하여, 현재 위치에서 나이트가 이동할 수 있는 모든 방향으로 이동해 봅니다.
3. 방문 여부 및 이동 횟수 갱신: 새로운 위치가 체스판 범위 내에 있고 아직 방문하지 않은 경우, 해당 위치를 큐에 추가하고, 시작 위치로부터의 이동 횟수를 갱신하고 방문 여부를 표시합니다.

저작자표시 (새창열림)

'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글

완전탐색 & 시뮬레이션 - 1  (0) 2024.06.12
[백준] 신기한 소수 찾기 - 2023번  (1) 2024.06.10
[백준] 열 개씩 끊어 출력하기 - 11721번  (0) 2024.06.01
[백준] KMP는 왜 KMP일까? - 2902번  (0) 2024.06.01
동적 프로그래밍과 반대 개념 프로그래밍  (1) 2024.05.31

티스토리툴바