(JAVA) [BOJ]백준 18404번, 현명한 나이트

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

18404번: 현명한 나이트

18404, 현명한 나이트

[ 난이도 : 실버 1 ]

이번 문제는 BFS 를 사용해서 풀어보겠다.

 

BOJ [7562] 나이트의 이동과 굉장히 유사한 문제이기 때문에 참조하면 좋을 것 같다.

https://seung-seok.tistory.com/57

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

 

# Process

input

: 체스판의 크기와 도달할 말의 수와 위치가 주어진다.

BFS 를 실행하여 좌표를 완성하고 M만큼 목적좌표를 받고 그대로 출력하는 식으로 코드를 작성하였다.

static void input() 
{
    N = scan.nextInt(); 
    M = scan.nextInt();
    // 시작 좌표
    sx = scan.nextInt();
    sy = scan.nextInt();
    // (1-N , 1-N)
    dist  = new int[N+1][N+1];
}

static void pro()
{
    bfs();
    while(M-- >0)
    {
        int ex = scan.nextInt();
        int ey = scan.nextInt();
        sb.append(dist[ex][ey]+" ");
    }
    System.out.println(sb);
}

 

BFS

: 동일한 형식으로 dist 의 모든 좌표를 -1 로 초기화 해준다. 이는 방문하기 전의 상태임을 의미한다.

 

시작좌표를 기점으로 체스가 이동할 수 있는 8개의 좌표를 순회하며 예외처리를 진행하고이동이 가능하다면 큐에 다시 넣어 다음 While 에서 좌표를 넓혀나아가며 dist 를 완성한다.

static void bfs()
{
    // 방문하기 전의 상태 = -1
    for(int i=1; i<=N; i++){ 
        for(int j=1; j<=N; j++) { 
            dist[i][j] = -1; 
        }
    }
    // 시작 좌표를 방문한 상태로 변경 = 0
    dist[sx][sy] = 0;

    Queue<Integer> que = new LinkedList<>();

    que.add(sx);
    que.add(sy);

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

        for(int k=0;k<8;k++)
        {
            int nx = x + dir[k][0];
            int ny = y + dir[k][1];
            // 범위 예외처리
            if(nx<1 || ny<1 || nx>N || ny>N) continue;
            // 방문한 곳에 대한 예외처리
            if(dist[nx][ny] != -1) continue;

            que.add(nx);
            que.add(ny);
            // (nx,ny) 의 이동 횟수는 (x,y) 에서 +1
            dist[nx][ny] = dist[x][y] + 1;
        }
    }

}

 

전체 코드

: 자세한 풀이는 위의 링크의 문제에서 다뤄놔서 참조하면 좋을 것 같다 : )

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

static void input() 
{
    N = scan.nextInt(); 
    M = scan.nextInt();
    // 시작 좌표
    sx = scan.nextInt();
    sy = scan.nextInt();
    // (1-N , 1-N)
    dist  = new int[N+1][N+1];
}

static void pro()
{
    bfs();
    while(M-- >0)
    {
        int ex = scan.nextInt();
        int ey = scan.nextInt();
        sb.append(dist[ex][ey]+" ");
    }
    System.out.println(sb);
}

static void bfs()
{
    // 방문하기 전의 상태 = -1
    for(int i=1; i<=N; i++){ 
        for(int j=1; j<=N; j++) { 
            dist[i][j] = -1; 
        }
    }
    
    // 시작 좌표를 방문한 상태로 변경 = 0
    dist[sx][sy] = 0;

    Queue<Integer> que = new LinkedList<>();

    que.add(sx);
    que.add(sy);

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

        for(int k=0;k<8;k++)
        {
            int nx = x + dir[k][0];
            int ny = y + dir[k][1];
            // 범위 예외처리
            if(nx<1 || ny<1 || nx>N || ny>N) continue;
            // 방문한 곳에 대한 예외처리
            if(dist[nx][ny] != -1) continue;

            que.add(nx);
            que.add(ny);
            // (nx,ny) 의 이동 횟수는 (x,y) 에서 +1
            dist[nx][ny] = dist[x][y] + 1;
        }
    }
}

public static void main(String[] args) 
{

    input();
    pro();
}