[BFS] 백준 16948 : 데스 나이트

16948번: 데스 나이트 (acmicpc.net)

16948번: 데스 나이트

 

1. 양방향 / 일방향으로 이동 가능한(연결된) input이 주어지거나, 각 점으로부터 이동 가능한 점에 대한 규칙이 주어진다.

2. 최단거리, 최단루트를 묻는다

=> BFS

 

BFS 문제들을 예전에 몇 개 풀었었지만, 한동안 다른 카테고리의 문제들 위주로 접하다가 오랜만에 BFS 문제를 보니 어떻게 BFS를 구현하는지 잘 기억이 안 났다. 아니 내가 그렇게 어려운 걸 했었다고?

 

BFS는 주로 Queue 자료구조를 이용하여 구현한다. 

 

먼저 시작점을 Queue에 넣는다. 

 

그 후 큐에서 다시 시작점을 뱉어낸다. 그리고 그 뱉어낸 값을 바탕으로, 인접한 노드들을 탐색하여, 아직 방문하지 않았으면 해당 노드들을 큐에 넣는다.

 

다시 노드들을 뱉어내고, 그 노드로부터 인접 노드를 찾고... 이를 반복한다. 

 

구글링을 해 보면 온갖 전문적이고 어려운 설명들이 있지만, 나의 야매적 컴퓨터 지식으로는 이 정도가 가장 깔끔한 이해인 것 같다.

 

큐가 뱉어낸 노드로부터 인접 노드들을 방문한다, 방문처리가 안 되어 있으면 방문처리를 하고 해당 인접 노드를 큐에 넣는다, 다시 뱉어내고 다시 인접 노드들을 방문한다... 이 짓을 큐가 텅 빌 때까지 계속한다.

 

그렇게 하면, 해당 노드를 큐가 몇 번째로 뱉어냈는지가 시작점과 해당 노드 사이의 이동 거리가 된다. 

 

문답무용. 코드로 살펴보자. 나는 우선 배열에서의 좌표값 r,c, 그리고 원점으로부터의 거리 distance를 instance variable로 가지는 클래스 Node를 생성했다.

 

class Node{
    private int r;
    private int c;
    private int distance;

    public Node(int r, int c, int distance){
        this.r = r;
        this.c = c;
        this.distance = distance;
    }

    public int getRow(){
        return r;
    }

    public int getColumn(){
        return c;
    }

    public int getDistance(){
        return distance;
    }
}

 

그리고 원점, 도착점, 체스 보드(이중 배열)을 parameter로 받아 BFS를 수행하는 함수를 작성하였다.

 

먼저 큐를 생성하고, 큐에 시작점 노드를 만들어서 넣고 시작점에 대한 방문처리를 해 준다. 

 

        Queue<Node> q = new LinkedList<>();

        q.offer(new Node(r1,c1,0));
        board[r1][c1]=1;

 

첫 점을 큐에 넣었으니, 이제 뱉어내면서 뱉어낸 노드에 대해 이동 가능한 노드들을 방문하고, 방문처리하는 작업을 수행한다.

while(!q.isEmpty()){
            //방문한(큐에 들어있는) 노드를 꺼냄.
            Node currentNode = q.poll();

            //도착노드인지 확인
            if(currentNode.getRow()==r2&&currentNode.getColumn()==c2){
                isConnected=true;
                distance = currentNode.getDistance();
                return;
            }

            //해당 노드를 기준으로, 인접한 이동 가능한 위치들을 queue에 넣으며 탐색
            if(currentNode.getRow()-2>=0&&currentNode.getColumn()-1>=0){
                if(board[currentNode.getRow()-2][currentNode.getColumn()-1]==0){
                    board[currentNode.getRow()-2][currentNode.getColumn()-1]=1;
                    q.offer(new Node(currentNode.getRow()-2, currentNode.getColumn()-1, currentNode.getDistance()+1));
                }
            }

            if(currentNode.getRow()-2>=0&&currentNode.getColumn()+1<board.length){
                if(board[currentNode.getRow()-2][currentNode.getColumn()+1]==0){
                    board[currentNode.getRow()-2][currentNode.getColumn()+1]=1;
                    q.offer(new Node(currentNode.getRow()-2, currentNode.getColumn()+1,currentNode.getDistance()+1));
                }
            }

            if(currentNode.getRow()+2<board.length&&currentNode.getColumn()-1>=0){
                if(board[currentNode.getRow()+2][currentNode.getColumn()-1]==0){
                    board[currentNode.getRow()+2][currentNode.getColumn()-1]=1;
                    q.offer(new Node(currentNode.getRow()+2, currentNode.getColumn()-1,currentNode.getDistance()+1));
                }
            }

            if(currentNode.getRow()+2<board.length&&currentNode.getColumn()+1<board.length){
                if(board[currentNode.getRow()+2][currentNode.getColumn()+1]==0){
                    board[currentNode.getRow()+2][currentNode.getColumn()+1]=1;
                    q.offer(new Node(currentNode.getRow()+2, currentNode.getColumn()+1,currentNode.getDistance()+1));
                }
            }

            if(currentNode.getColumn()-2>=0){
                if(board[currentNode.getRow()][currentNode.getColumn()-2]==0){
                    board[currentNode.getRow()][currentNode.getColumn()-2]=1;
                    q.offer(new Node(currentNode.getRow(), currentNode.getColumn()-2,currentNode.getDistance()+1));
                }
            }

            if(currentNode.getColumn()+2<board.length){
                if(board[currentNode.getRow()][currentNode.getColumn()+2]==0){
                    board[currentNode.getRow()][currentNode.getColumn()+2]=1;
                    q.offer(new Node(currentNode.getRow(), currentNode.getColumn()+2,currentNode.getDistance()+1));
                }
            }
        }

매번 방문하지 않은 노드들을 방문할 때마다, 현재 뱉어낸 노드(q.poll()의 결과로 얻은 노드)의 distance 값에 1씩을 더하기로 했다.

 

그리고 노드를 뱉어낼 때, 도착 노드인지 확인하여 도착 노드임이 확인되면 BFS를 종료하는 코드를 위와 같이 추가하였다.

 

전체 코드를 첨부하고 마친다.

 

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ_16948 {
    static int[][] board;
    static boolean[][] visited;
    static int N;
    static int r1,r2,c1,c2;
    static int distance=0;
    static boolean isConnected;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        board = new int[N][N];
        visited = new boolean[N][N];

        String[] input = br.readLine().split(" ");
        r1 = Integer.parseInt(input[0]);
        c1 = Integer.parseInt(input[1]);
        r2 = Integer.parseInt(input[2]);
        c2 = Integer.parseInt(input[3]);

        BFS(r1,c1,r2,c2,board);
        if(isConnected){
            System.out.println(distance);
        }else{
            System.out.println(-1);
        }


    }

    static void BFS(int r1,int c1,int r2, int c2,int[][] board){
        if(r1<0||r1>board.length||c1<0||c1>board.length){
            return;
        }
        //큐 생성
        Queue<Node> q = new LinkedList<>();

        q.offer(new Node(r1,c1,0));
        board[r1][c1]=1;

        //이동 가능한 위치들을 큐에 넣는다.
        while(!q.isEmpty()){
            //방문한(큐에 들어있는) 노드를 꺼냄.
            Node currentNode = q.poll();

            //도착노드인지 확인
            if(currentNode.getRow()==r2&&currentNode.getColumn()==c2){
                isConnected=true;
                distance = currentNode.getDistance();
                return;
            }

            //해당 노드를 기준으로, 인접한 이동 가능한 위치들을 queue에 넣으며 탐색
            if(currentNode.getRow()-2>=0&&currentNode.getColumn()-1>=0){
                if(board[currentNode.getRow()-2][currentNode.getColumn()-1]==0){
                    board[currentNode.getRow()-2][currentNode.getColumn()-1]=1;
                    q.offer(new Node(currentNode.getRow()-2, currentNode.getColumn()-1, currentNode.getDistance()+1));
                }
            }

            if(currentNode.getRow()-2>=0&&currentNode.getColumn()+1<board.length){
                if(board[currentNode.getRow()-2][currentNode.getColumn()+1]==0){
                    board[currentNode.getRow()-2][currentNode.getColumn()+1]=1;
                    q.offer(new Node(currentNode.getRow()-2, currentNode.getColumn()+1,currentNode.getDistance()+1));
                }
            }

            if(currentNode.getRow()+2<board.length&&currentNode.getColumn()-1>=0){
                if(board[currentNode.getRow()+2][currentNode.getColumn()-1]==0){
                    board[currentNode.getRow()+2][currentNode.getColumn()-1]=1;
                    q.offer(new Node(currentNode.getRow()+2, currentNode.getColumn()-1,currentNode.getDistance()+1));
                }
            }

            if(currentNode.getRow()+2<board.length&&currentNode.getColumn()+1<board.length){
                if(board[currentNode.getRow()+2][currentNode.getColumn()+1]==0){
                    board[currentNode.getRow()+2][currentNode.getColumn()+1]=1;
                    q.offer(new Node(currentNode.getRow()+2, currentNode.getColumn()+1,currentNode.getDistance()+1));
                }
            }

            if(currentNode.getColumn()-2>=0){
                if(board[currentNode.getRow()][currentNode.getColumn()-2]==0){
                    board[currentNode.getRow()][currentNode.getColumn()-2]=1;
                    q.offer(new Node(currentNode.getRow(), currentNode.getColumn()-2,currentNode.getDistance()+1));
                }
            }

            if(currentNode.getColumn()+2<board.length){
                if(board[currentNode.getRow()][currentNode.getColumn()+2]==0){
                    board[currentNode.getRow()][currentNode.getColumn()+2]=1;
                    q.offer(new Node(currentNode.getRow(), currentNode.getColumn()+2,currentNode.getDistance()+1));
                }
            }
        }
    }


}

class Node{
    private int r;
    private int c;
    private int distance;

    public Node(int r, int c, int distance){
        this.r = r;
        this.c = c;
        this.distance = distance;
    }

    public int getRow(){
        return r;
    }

    public int getColumn(){
        return c;
    }

    public int getDistance(){
        return distance;
    }
}