[PS] BOJ18404 현명한 나이트 ( BFS ) with JAVA

18404번: 현명한 나이트

 

 

◎ 문제풀이

 

나이트를 이동시켜 체스말을 잡을 때, 나이트의 최소 이동수를 구하는 문제이다.

 

그래프의 좌표가 주어지고 이동비용이 동일할 때 최소이동수를 구하는 문제이니, BFS 풀이이다.  이 문제를 풀며, 시간초과가 발생했을 때 시간복잡도를 계산해서 문제를 다시 리빌딩하는 능력이 부족함을 깨달았다. 처음에는 잡아야하는 체스말이 3개 주어지면 DFS 탐색도 3번하는 방식으로 풀었다. 그랬더니 시간초과가 발생했다. 시간복잡도를 계산하지 않고 그냥 풀었다가 발생한 문제였다. 

 

N은 최대 500이니 체스판의 노드 개수는 최대 250,000개이다. DFS 탐색은 방문처리를 하면 큐에 한번 들어간 노드는 다시 들어갈 수 없으니, 노드의 개수가 V이면 시간복잡도는 O(V)이다.  체스말의 개수(M)는 최대 1000이다. 만약 체스말의 개수만큼 DFS 탐색을 한다면 시간복잡도는 O(VM)이 된다. 250,000 x 1,000은 250,000,000으로 시간제한 1초를 넘긴다. 

 

그러므로 시간복잡도 O(V)안에 문제를 풀 수 있도록 다시 리빌딩해야 한다.

 

DFS 탐색을 하여 체스판의 모든 노드에 비용을 미리 계산해놓고 잡아야하는 체스말의 위치만 O(1) 시간복잡도로 가지고 오면 시간복잡도 O(V)안에 문제를 풀 수 있다.

 

 

◎ 코드

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

//BOJ18404 현명한 나이트 
public class Main {

    static int[] dx = {-2,-1,1,2,-2,-1,1,2}; // 나이트 x축 이동 경우의 수
    static int[] dy = {1,2,2,1,-1,-2,-2,-1}; // 나이트 y축 이동 경우의 수
    static int[][] costs; // 체스판 비용 테이블

    static int n;
    static int m;

    public static class ChessObject{
        int x;
        int y;
        public ChessObject(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());

        costs= new int[n+1][n+1]; // 체스판의 비용을 저장하는 테이블
        bfs(new ChessObject(x,y),costs); // BFS로 비용 계산하기

        //잡아야 하는 체스말의 비용을 O(1) 시간복잡도로 가져오기 
        for(int i =0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int ix = Integer.parseInt(st.nextToken());
            int iy = Integer.parseInt(st.nextToken());

            sb.append(costs[iy][ix]).append(" ");
        }
        
        //출력
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    public static void bfs(ChessObject start,int[][] costs){
        Queue<ChessObject> queue = new LinkedList<>();
        costs[start.y][start.x] = 0;
        queue.add(start);

         while(!queue.isEmpty()){
            ChessObject currNight = queue.remove();
            for(int i=0;i<8;i++){
                int nx = currNight.x + dx[i];
                int ny = currNight.y + dy[i];

                if(!isValid(nx,ny)) continue;
                if(costs[ny][nx] == 0 ) {
                    costs[ny][nx] = costs[currNight.y][currNight.x] + 1;
                    queue.add(new ChessObject(nx,ny));
                }
            }
        }
    }

    public static boolean isValid(int x, int y){
        if( x>0 && y>0 && x<=n && y<=n ) return true;
        else return false;
    }

}