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

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

 

드디어 DFS, BFS 문제를 풀이 없이 혼자 풀어봤다 !!!!! 최근 금융권 준비하면서 완전탐색, 문자열, DFS/BFS 위주로 문제 풀고 있는데 DFS/BFS가 문제에 나와도 잘 못푸는 걸 깨닫고 스스로 화났던 과거를 청산하기 위하여... 열심히 풀었던 문제 또 풀어보고 풀어보고를 반복하다보니 드디어 조금씩 감을 익히고 있는 것 같다.

 

사실 근데 문제 자체는 크게 어렵지 않다. 나이트가 이동할 수 있는 방향은 총 8개로, 기존에 미로 탐색 같은 문제에서 갈 수 있는 방향을 상, 하, 좌, 우 4군데로 지정해서 했던 것처럼 이번에는 8군데로 지정해서 BFS로 문제를 풀면 된다. 

 

원래 DFS/BFS 문제를 풀 때는 graph랑 visited를 같이 사용해서 푸는 경우가 대부분이었지만, 이 문제는 좌표이기도 해서 굳이 arr를 지정하지 않고 visited에 따라서 결정하면 된다. 그리고 좀 헷갈렸던 부분은 좌표의 범위를 어떻게 한정해야되는지 모르겠어서 처음에는 없이 풀었는데 당연히 오류가 났다. 예를 들어 한 변의 길이가 8이라고 했을 때 (0, 0)을 기준으로 했을 때 (0, 0)부터 (8, 8)까지의 범위 안에서 이동할 수 있는 거고 음수의 좌표를 갖는 경우는 없다고 생각하면 된다. 나는 처음에 8이 한 변인데 어떻게 (7, 0)을 갈 수 있는지에 대해서 생각하다가 범위가 없어도 되는지에 대한 고민을 하면서 조금 헷갈렸던 것 같다.

 

바로 맞았으면 참 좋았겠지만 다른 문제와 다르게 인덱스도 0, 0으로 시작해서 마지막에 어떤 수를 출력하면 되는지도 좀 헷갈렸고, 처음 BFS 함수에 들어갔을 때 방문 표시를 하지 않아도 되는데 방문 표시를 하면서 1씩 더 많게 답이 나오기도 했지만 결국 문제를 해결할 수 있었다! 

 

import java.util.*;
import java.io.*;

public class Main{
    public static int[][] arr;
    public static int[][] visited;
    public static int[] dx = {1, 2, 1, 2, -1, -2, -1, -2};
    public static int[] dy = {2, 1, -2, -1, -2, -1, 2, 1};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());
        for(int i = 0; i < t; i++){
            int l = Integer.parseInt(br.readLine());
            visited = new int[l][l];
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start_x = Integer.parseInt(st.nextToken());
            int start_y = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            
            int dest_x = Integer.parseInt(st.nextToken());
            int dest_y = Integer.parseInt(st.nextToken());
            
            bfs(start_x, start_y, dest_x, dest_y);
            
            sb.append(visited[dest_x][dest_y] + "\n");
        }
        System.out.println(String.valueOf(sb));
    }
    
    public static void bfs(int start_x, int start_y, int dest_x, int dest_y){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{start_x, start_y});
        
        while(!queue.isEmpty()){
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            
            if(x == dest_x && y == dest_y){
                return;
            }
            
            for(int i = 0; i < 8; i++){
                int next_x = x + dx[i];
                int next_y = y + dy[i];
                if(next_x >= 0 && next_y >= 0 && next_x < visited.length && next_y < visited.length){
                    if(visited[next_x][next_y] == 0){
                        queue.add(new int[]{next_x, next_y});
                        visited[next_x][next_y] = visited[x][y] + 1;
                    }
                }
            }
        }
    }
}

 

그래도 조금씩 성장하고 있구나 .. ㅎ