[BOJ] 7562. 나이트의 이동(BFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

현재 나이트가 있는 칸에서 이동하려고 하는 칸까지

최소의 움직임으로 이동해야하므로 BFS로 해결해야 한다.

가장 기본적인 BFS 문제에 탐색을 체스에서 나이트처럼 한다는 점?

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class BOJ7562 {       static int T, N;     static boolean visited[][];     static int[] dr = { -1, -2, -2, -1, 1, 2, 2, 1 }, dc = { -2, -1, 1, 2, -2, -1, 1, 2 };     static State start, end;       static class State {         int r, c, dist = 0;           public State(int x, int y, int dist) {             this.r = x;             this.c = y;             this.dist = dist;         }     }       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;           T = Integer.parseInt(br.readLine());         for (int i = 0; i < T; i++) {               N = Integer.parseInt(br.readLine());             visited = new boolean[N][N];               // 나이트의 현재 위치             st = new StringTokenizer(br.readLine());             start = new State(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);             // 나이트가 이동하려고 하는 위치             st = new StringTokenizer(br.readLine());             end = new State(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);                          System.out.println(bfs());         }       }       private static int bfs() {                  Queue<State> q = new LinkedList<>();         q.add(start);         visited[start.r][start.c] = true;                  while(!q.isEmpty()) {             State now = q.poll();             // 도착 지점에 도달하면             if(now.r == end.r && now.c == end.c)                 return now.dist;             // 나이트처럼 8방 탐색             for (int d = 0; d < 8; d++) {                 int rr = now.r + dr[d];                 int cc = now.c + dc[d];                 // 범위를 벗어나면 pass                 if(rr < 0 || cc < 0 || rr >= N || cc >= N) continue;                 // 이미 방문한 적이 있다면 pass                 if(visited[rr][cc]) continue;                                  visited[rr][cc] = true;                 q.add(new State(rr, cc, now.dist + 1));             }         }                  return 0;     }   }   Colored by Color Scripter

cs