백준 - 7562

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

public class Main {
    static int[][] dir = {
            {-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}
    };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        for(int n = 0; n < N; n++){
            int l = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            int eX = Integer.parseInt(st.nextToken());
            int eY = Integer.parseInt(st.nextToken());

            if(r == eX && c == eY){
                System.out.println(0);
                continue;
            }
            System.out.println(bfs(l,r,c,eX,eY));
        }
    }
    static int bfs(int l, int r, int c, int eX, int eY){
        boolean[][] visited = new boolean[l][l];
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {r,c, 0});
        visited[r][c] = true;

        while(!q.isEmpty()){
            int[] a = q.poll();
            int x = a[0]; int y = a[1]; int cnt = a[2];

            for(int d = 0; d < 8; d++){
                int nr = x + dir[d][0];
                int nc = y + dir[d][1];

                if(nr >= 0 && nc >= 0 && nr < l && nc < l
                &&!visited[nr][nc]){
                    if(nr == eX && nc == eY) return cnt+1;
                    visited[nr][nc] = true;
                    q.offer(new int[] {nr,nc,cnt+1});
                }
            }
        }
        return -1;
    }
}

풀이과정 및 리뷰

1. 최단 거리를 구하는 로직이므로 BFS사용
2. 델타 배열에 나이트의 이동 8가지 경우 저장 → BFS안에서 방향배열로 사용
3. 만약 처음 주어진 시작점 == 끝점인 경우 0을 출력하고 continue
4. BFS

• 내부에서 int배열타입을 받는 큐 선언 후 시작점 offer + 방문체크
• 큐가 빌 때까지 반복
  • 배열 데이터를 각각 r / c / cnt에 할당한 후, 델타배열을 이용해 너비우선탐색 시작
  • 배열범위를 벗어나지 않으며 && 방문하지 않은 지점이라면, 조건에 걸려 로직 실행 → 이때 도착점에 도달한다면, 배열에 저장됫 횟수 + 1을 리턴하며 메서드 종료 → 그렇지 않다면, 방문체크 후 횟수 + 1 하며 큐에 삽입
    
  • 만약 도달할 수 없는 지점이라면 -1을 리턴(예외처리)

DFS & BFS는 어느 상황에 사용하는게 적합할까?

• BFS : 최단경로 탐색, 레벨별 탐색 등 최소 최단 키워드가 존재한다면 사용
• DFS : 경로의 모든 경우 탐색, 사이클 탐지, 경로가 깊거나 분기점이 많은 경우 사용