[백준] 16948번 : 데스 나이트 – JAVA [자바]

 

 

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

16948번: 데스 나이트

 

 

 

 

---

 

• 문제

 

---

 

• 풀이 방법

이 문제는 전형적인 그래프 문제이다. 조금 더 구체적인 그래프 이론을 알고 싶으면 밑에 링크를 참고하면 되겠다.

https://propercoding.tistory.com/entry/자료구조-그래프Graph

[자료구조] 그래프(Graph)

 

 

이 문제는 실버 1의 그래프 문제이다. 그리고 그래프 중에 그래프 탐색 이론인 BFS (Breadth First Search), 즉 너비 탐색을 이용한다. 첫 시작점이 (r, c)라고 가정하고 최종적으로 이동하고 싶은 점이 (r2, c2)라고 가정하겠다. 그리고 데스 나이트는 한 점이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 이렇게 이동을 계속해서 결국에는 (r2, c2)로 갈 수 있는지 없는지만 확인하면 된다. 그리고 만약에 (r2, c2)로 갈 수 있으면 최소 이동 횟수를 구해주면 되는 문제이다.

 

이 문제에서는 int형 배열은 필요 없고 boolean형 배열 visited를 만들어서 그 정점을 방문했는지, 안 했는지만 확인해주면 된다. 일단은 시작점인 r1, c1을 visited에 넣고 시작한다. 그리고 이동할 수 있는 점들 중에서 아직 방문을 안 한 점들만 queue에 넣어주는 식으로 하면 문제를 풀 수 있다. 

 

예를 들어 보겠다. 문제에서 주어진 예제 3번을 보겠다. n = 7이고 (r1, c1) = (0, 3)이고 (r2, c2) = (4, 3)이다. 

일단 주어진 그래프를 표로 나타내면 다음과 같다. 즉 START에서 시작해서 END로 가야 한다.

처음에 visited 배열에 (0, 0)을 넣는다. 그리고 START에서 시작해서 갈 수 있는 점들은 (-2, 2), (-2, 4), (0, 1), (0, 5), (2, 2), (2, 4)인데 (-2, 2)와 (-2, 4)는 범위를 벗어난다. 따라서 (0, 1), (0, 5), (2, 2), (2, 4) 점들만 queue에 넣어주고 방문했다고 표시한다.

이번에 방문했던 점들을 살펴보겠다.

(0, 1)에서 시작했을 때 방문 안 한 점들 중에서 (2, 0)으로만 새로 갈 수 있다.

(0, 5)에서 시작했을때 방문 안 한 점들 중에서 (2, 6)으로만 새로 갈 수 있다.

(2, 2)에서 시작했을때 방문 안 한 점들 중에서 (4, 1)과 (4, 3)으로 새로 갈 수 있다. 근데 (4, 3)은 이동하고 싶었던 점이므로 여기서 너비 탐색은 마무리된다.

따라서 (0, 3) ⇒ (2, 2) ⇒ (4, 3)으로 총 2번 만에 갈 수 있다.

 

 

---

 

• 풀이

 

import java.io.*;
import java.util.*;
public class Main {
  static boolean[][] visited;
  static int count;
  static int n;
  static int[] dx = {-2, -2, 0, 0, 2, 2};
  static int[] dy = {-1, 1, -2, 2, -1, 1};
  static int r2;
  static int c2;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    visited = new boolean[n][n];
    StringTokenizer st = new StringTokenizer(br.readLine());
    int r1 = Integer.parseInt(st.nextToken());
    int c1 = Integer.parseInt(st.nextToken());
    r2 = Integer.parseInt(st.nextToken());
    c2 = Integer.parseInt(st.nextToken());
    count = 0;
    System.out.print(bfs(r1,c1));
  }

  static int bfs(int r1, int c1) {
    Queue<Integer> q1 = new LinkedList<>();
    Queue<Integer> q2 = new LinkedList<>();
    q1.add(r1);
    q2.add(c1);
    visited[r1][c1] = true;
    while (!q1.isEmpty()) {
      int size = q1.size();
      for (int j = 0; j < size; j++) {
        int x = q1.remove();
        int y = q2.remove();
        if (x == r2 && y == c2) return count;
        for (int i = 0; i < 6; i++) {
          int mx = x + dx[i];
          int my = y + dy[i];
          if (mx < 0 || mx > n-1) continue;
          if (my < 0 || my > n-1) continue;
          if (!visited[mx][my]) {
          visited[mx][my] = true;
          q1.add(mx);
          q2.add(my);
          }
        }
      }
      count++;
    }
    return -1;
  }
}

 

 

---

 

• 후기

되게 전형적인 그래프 탐색 문제였고 이 문제를 푸는 법을 익히면 나머지 실버 수준의 그래프 문제들도 충분히 풀 수 있다.