[Java][자바][백준][7562번] 나이트의 이동

문제 설명

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

입력

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

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

출력

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

 

생각

bfs로 구하면 된다. 나이트가 이동할 수 있는 경우만 dx,dy에 설정해두고 목표하는 좌표로 이동할 때까지 이동한 횟수를 증가시키며 구해주면 된다. 간단한 문제이므로 추가 설명은 주석에 간단하게 적겠다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    //나이트가 이동할 수 있는 경우의 수를 설정해준다.
    static int[] dx = {-2,-1,2,1,2,1,-2,-1};
    static int[] dy = {1,2,1,2,-1,-2,-1,-2};
    static int[][] map;
    static boolean[][] visited;
    static int n;
    static int start_x, start_y, end_x, end_y;
    static int count = 0;
    static Queue<dot> q = new LinkedList<dot>();
 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        int t = Integer.parseInt(br.readLine());
        
        for(int i=0; i<t; i++) {
            n = Integer.parseInt(br.readLine());
            map = new int[n][n];
            visited = new boolean[n][n];
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            start_x = Integer.parseInt(st.nextToken());
            start_y = Integer.parseInt(st.nextToken());
            
 
            st = new StringTokenizer(br.readLine());
            end_x = Integer.parseInt(st.nextToken());
            end_y = Integer.parseInt(st.nextToken());
            
            bfs(new dot(start_x, start_y));
            System.out.println(map[end_x][end_y]);
        }
        
    }
    
    static void bfs(dot d) {
        //미리 설정해둔 도착지가 되면 return해준다.
        if(d.x == end_x && d.y == end_y) {
            return;
        }
        visited[d.x][d.y] = true;
        
        q.add(d);
        
        while(!q.isEmpty()) {
            dot t = q.remove();
            int x1 = t.x;
            int y1 = t.y;
            
            for(int i=0; i<dx.length; i++) {
                int x2 = x1 + dx[i];
                int y2 = y1 + dy[i];
                
                if(x2>=0 && x2<n && y2>=0 && y2<n && !visited[x2][y2]) {
                    q.add(new dot(x2,y2));
                    visited[x2][y2] = true;
                    //전의 이동 횟수에 +1 씩 더해주며 이동 횟수를 증가시켜준다.
                    map[x2][y2] = map[x1][y1] + 1;
                }
            }
        }
        
    }
 
}
 
class dot {
    int x;
    int y;
    
    public dot(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

방금 위 코드를 보다가 큰 오류가 발견된다. 43~45번째 줄에서 end_x, end_y에 도착하면 return 해주는데 bfs함수를 한번만 호출하기 때문에 저 곳에 접근을 하지 않는다. 따라서 나이트가 이동할 수 있는 모든 경우의 수를 다 돌고나서 queue가 empty가 되면 빠져나오면서 불필요한 연산을 하게 되었다.

 

여태까지 이렇게 푼 문제가 많은데...모두 쓸데없는 연산을 했다는 증거이다. loop를 활용해서 연산을 최대한 줄이도록 하자!!! 역시 복습을 하니 이런 실수도 발견하게 된다 ㅎㅎ