(JAVA) [BOJ]백준 7562번, 나이트의 이동

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

7562번: 나이트의 이동

7562, 나이트의 이동

[ 난이도 : 실버 1 ]

이번 문제는 체스말의 이동횟수를 측정해야 하므로 BFS (너비 우선 탐색)를 사용해서 풀어보겠다.

 

# Process

input

: 테스트 케이스 횟수 T를 입력받고, 체스판의 크기를 입력 받는다. 체스판의 크기를 기반으로 dist를 생성해주고

시작좌표화 목적좌표를 입력받는다.

여기서 dist[i][j] 는 (i,j) 까지 최소 이동횟수를 입력할 것이고, 방문여부까지 한번에 확인할 수 있게 

코드를 설계할 것이다.

static int N, sx, sy, ex, ey;
static int[][] dist;
static int[][] dir = {{-1,-2},{-2,-1},{-1,2},{-2,1},{1,-2},{2,-1},{1,2},{2,1}};

static void input() {
    N = scan.nextInt();
    sx = scan.nextInt();
    sy = scan.nextInt();
    ex = scan.nextInt();
    ey = scan.nextInt();
    dist = new int[N][N];
}

 

BFS

: BFS 를 통해 시작좌표부터 이동가능한 모든 좌표를 탐색하며 최소 이동 거리에 대한 값을 입력할 것이다.

먼저 dist 를 -1 로 초기화 해준다. 이는 아직 방문하지 않았음을 동시에 표현해주기 위해서이다.

// -1로 초기화
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        dist[i][j] = -1;
    }
}

 

그 후, Queue 를 생성하여 시작 좌표를 넣어줄 것이다. Queue 의 형태를 따로 클래스를 생성해주지 않고

Integer 로 해준 이유는 x 좌표를 먼저 넣어주고 그 후에 y 좌표를 넣어주는 형식을 고정으로 진행하기 때문에 순서가 변하지 않는다.

 

Queue 가 빌 때 까지 x, y 좌표를 꺼내 상하좌우로 가능할 때까지 이동시켜 나아가며 dist 를 완성해간다.

dist[nx][ny] 까지의 최소 이동 횟수는 dist[x][y] 까지 최소 이동 횟수에서 +1 만 더 해주면 되기 때문에 아래와 같이 코드를 작성하였다.

//시작 좌표
dist[sx][sy] = 0;
Q.add(sx);
Q.add(sy);

// BFS 과정 시작
while (!Q.isEmpty()) 
{
    int x = Q.poll();
    int y = Q.poll();

    for (int k = 0; k < 8; k++) 
    {
        int nx = x + dir[k][0];
        int ny = y + dir[k][1];
        // 지도를 벗어나는 곳으로 가는가?
        if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
        // 이미 방문한 적이 있는 곳인가?  
        if (dist[nx][ny] != -1) continue;  

        Q.add(nx);
        Q.add(ny);
        dist[nx][ny] = dist[x][y] + 1;
    }
}

return dist[ex][ey];

 

전체 코드

: 위와 같은 로직을 통해 쉽게 답을 얻을 수 있다.

static int N, sx, sy, ex, ey;
static int[][] dist;
static int[][] dir = {{-1,-2},{-2,-1},{-1,2},{-2,1},{1,-2},{2,-1},{1,2},{2,1}};

static void input() {
    N = scan.nextInt();
    sx = scan.nextInt();
    sy = scan.nextInt();
    ex = scan.nextInt();
    ey = scan.nextInt();
    dist = new int[N][N];
}

static void pro()
{
    sb.append(bfs()+"\n");
}

static int bfs() {
    // -1로 초기화
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            dist[i][j] = -1;
        }
    }
    
    Queue<Integer> Q = new LinkedList<>();

    //시작 좌표
    dist[sx][sy] = 0;
    Q.add(sx);
    Q.add(sy);

    // BFS 과정 시작
    while (!Q.isEmpty()) 
    {
        int x = Q.poll();
        int y = Q.poll();

        for (int k = 0; k < 8; k++) 
        {
            int nx = x + dir[k][0];
            int ny = y + dir[k][1];
            // 지도를 벗어나는 곳으로 가는가?
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            // 이미 방문한 적이 있는 곳인가?  
            if (dist[nx][ny] != -1) continue;  

            Q.add(nx);
            Q.add(ny);
            dist[nx][ny] = dist[x][y] + 1;
        }
    }

    return dist[ex][ey];
}