📙[Algo] 24.01.01 알고리즘

7562번: 나이트의 이동

문제 요약
나이트가 이동하려는 칸이 주어졌을 때, 몇 번 움직이면 해당 칸으로 이동할 수 있는가?
아래 그림은 나이트가 한 번에 이동할 수 있는 칸

시간 제한
1초

입력
테스트 케이스 개수
테스트 케이스 별 세 줄씩 주어짐
 - 체스판 한 변의 길이 I (4≤I≤300)
 - 각 칸은 두 수의 쌍 {0,…,l-1} * {0, …, l-1}
    - 나이트가 현재 있는 칸
    - 나이트가 이동하려는 칸

출력
테스트 케이스별 최소 몇 번만에 이동 가능한 지 출력

 

접근법

• 한 번에 이동할 수 있는 칸을 2차원 delta 배열로 만들었다.

static int[][] deltas = {{-2,-1},{-1,-2},{-2,1},{-1,2},{2,-1},{1,-2},{2,1},{1,2}};

• 최소로 도착해야 하므로 bfs 알고리즘을 사용함
• 카운트를 할 때는 한 사이클마다 카운트 할 수 있도록 했다
  • 현재 큐에 담겨진 후보 좌표들을 하나씩 훑는 걸 한 사이클로 생각했다. 

고민

• 이동 횟수를 카운트하는 다른 방법은 없을까?
  
  • 지금까지 이동하면서 이동 횟수를 map에 기록하는 방식도 있다.

// 지금까지 이동 횟수를 map 원소값에 갱신
// mRow, mCol : 이동한 좌표
// cRow, cCol : 이동전 기준이 되는 좌표
map[mRow][mCol] = map[cRow][cCol]+1;
...
// 출력할 때는 
map[tRow][tCol];

 

코드

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

public class Main {
    static int[][] deltas = {{-2,-1},{-1,-2},{-2,1},{-1,2},{2,-1},{1,-2},{2,1},{1,2}};
    static int I; // 체스판 한 변의 길이
    static int sRow, sCol, tRow, tCol; // 시작 좌표(sRow, sCol), 도착 좌표(tRow, tCol)
    static  boolean[][] visited;

    static int move(){
        int cnt = 0;

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {sRow, sCol});
        visited[sRow][sCol] = true;

        while(!q.isEmpty()){

            int size = q.size();

            // 한 사이클 => 현재 큐에 담겨진 후보 좌표들을 하나씩 훑는 것
            for(int i=0; i<size; i++){
                int cRow = q.peek()[0];
                int cCol = q.poll()[1];

                // 현재 좌표가 이미 도착 지점이라면 사이클 종료
                if(cRow == tRow && cCol == tCol){
                    return cnt;
                }

                // 나이트가 이동 할 수 있는 좌표만큼 이동시킨다.
                for(int dir=0; dir<deltas.length; dir++){
                    int mRow = cRow + deltas[dir][0];
                    int mCol = cCol + deltas[dir][1];

                    // 경계 체크
                    if(mRow<0 || mCol<0 || I<=mRow || I<=mCol) continue;

                    // 이동한 좌표가 도착 지점이라면 사이클 종료
                    if(mRow == tRow && mCol == tCol){
                        cnt++;
                        return cnt;
                    }

                    // 방문 하지 않은 좌표라면 후보 좌표가 되므로, 방문 체크하고 큐에 담음
                    if(!visited[mRow][mCol]){
                        visited[mRow][mCol] = true;
                        q.offer(new int[] {mRow, mCol});
                    }
                }
            }
            cnt++;
        }

        return cnt;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int TC = Integer.parseInt(br.readLine());

        while(TC-->0){
            I = Integer.parseInt(br.readLine());

            st = new StringTokenizer(br.readLine());
            sRow = Integer.parseInt(st.nextToken());
            sCol = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            tRow = Integer.parseInt(st.nextToken());
            tCol = Integer.parseInt(st.nextToken());

            visited = new boolean[I][I];
            sb.append(move()+"\n");
        }
        System.out.println(sb);
    }
}