[백준] [16948] 데스 나이트 (BFS) (JAVA)

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

16948번: 데스 나이트

---

문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.

출력

첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

예제 입력 1 복사

7
6 6 0 1

예제 출력 1 복사

4

예제 입력 2 복사

6
5 1 0 5

예제 출력 2 복사

-1

예제 입력 3 복사

7
0 3 4 3

예제 출력 3 복사

2

---

※ JAVA 코드 (데스 나이트)

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

public class Main {
	static int N, r1, c1, r2, c2;
	
	// 체스판 맵 배열
	static int[][] map;
	
	// 방문 체크 배열
	static boolean[][] visited;
	
	// 말이 이동할 경로
	static int[] moveX = {-2, -2, 0, 0, 2, 2};
	static int[] moveY = {-1, 1, -2, 2, -1, 1};
	
	// 좌표를 담을 클래스
	static class Node{
		int x, y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static void BFS(int x, int y) {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(x, y));
		visited[x][y] = true;
		
		while(!q.isEmpty()) {
			Node now = q.poll();
			int nowX = now.x;
			int nowY = now.y;
			if(nowX == r2 && nowY == c2) {
				break;
			}
			for(int i = 0; i < 6; i++) {
				int nextX = nowX + moveX[i];
				int nextY = nowY + moveY[i];
				
				if(nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) {
					continue;
				}
				
				if(visited[nextX][nextY] == true) {
					continue;
				}
				
				q.offer(new Node(nextX, nextY));
				visited[nextX][nextY] = true;
				map[nextX][nextY] = map[nowX][nowY] + 1;
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		// 체스판 크기 N x N
		N = Integer.parseInt(br.readLine());
		
		map = new int[N][N];
		visited = new boolean[N][N];
		
		// r1, c1, r2, c2
		st = new StringTokenizer(br.readLine());
		r1 = Integer.parseInt(st.nextToken());
		c1 = Integer.parseInt(st.nextToken());
		r2 = Integer.parseInt(st.nextToken());
		c2 = Integer.parseInt(st.nextToken());
		
		if(r1 == r2 && c1 == c2) {
			System.out.println(0);
		} else {
			BFS(r1, c1);
			System.out.println(map[r2][c2] == 0 ? -1 : map[r2][c2]);
		}
	}
}

---

※ 생각정리 (데스 나이트)

데스나이트 문제는 맵의 이동을 상하좌우로만 하던 기존의 탐색문제와는 조금 다르게 이동하며 탐색한다.

이동할 좌표를 미리 정수배열에 담아두고 시작한다.

// 말이 이동할 경로
static int[] moveX = {-2, -2, 0, 0, 2, 2};
static int[] moveY = {-1, 1, -2, 2, -1, 1};

또한, 한번 이동했다면 이동하기 전의 좌표값에 +1을 하여 값을 더해가며 탐색을 이어간다.

이때 이미 방문한 좌표는 또 방문하지 않도록 방문체크를 같이 겸해준다.

q.offer(new Node(nextX, nextY));
visited[nextX][nextY] = true;
map[nextX][nextY] = map[nowX][nowY] + 1;

큐가 빌때까지 반복을 진행하고 큐가 끝나고도 값이 0이라면 방문할 수 없는 좌표이므로 -1을 출력한다.

방문할 수 있는 좌표라면 map[r2][c2]에 저장된 값을 출력한다.

-새벽코딩-