[백준] [7562] 나이트의 이동 (BFS) (JAVA)

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

7562번: 나이트의 이동

---

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력 1 복사

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1 복사

5
28
0

---

※ JAVA 코드 (나이트의 이동)

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

public class Main {
	// 체스판 변의 크기
	static int N;
	
	// 시작좌표(x, y), 도착좌표(x, y)
	static int sX, sY, eX, eY;
	static int[][] map;
	static boolean[][] visited;
	
	// 나이트가 이동할 수 있는 방향
	static int[] dx = {-1, -2, -2, -1, 1, 2,  2,  1};
	static int[] dy = {-2, -1,  1,  2, 2, 1, -1, -2};
	
	// 맵의 좌표와 이동 횟수
	static class Node {
		int x, y, cnt;
		public Node(int x, int y, int cnt) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
	}
	
	public static int BFS(int x, int y) {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(x, y, 0));
		visited[x][y] = true;
		
		while(!q.isEmpty()) {
			Node now = q.poll();
			// 현재 큐의 좌표
			int nowX = now.x;
			int nowY = now.y;
			
			// 현재 좌표가 도착지점이라면 이동횟수 리턴
			if(nowX == eX && nowY == eY) {
				return now.cnt;
			}
			
			for(int i = 0; i < 8; i++) {
				// 다음으로 이동해야 할 좌표
				int nextX = nowX + dx[i];
				int nextY = nowY + dy[i];
				
				// 이동경로가 체스판의 범위를 벗어난다면 
				if(nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) {
					continue;
				}
				
				// 이미 방문한 좌표는 방문하지 않도록 체크
				if(visited[nextX][nextY] == true) {
					continue;
				}
				
				// 방문체크
				visited[nextX][nextY] = true;
				// 현재좌표에 이동횟수 1을 추가하여 큐에 담는다
				q.offer(new Node(nextX, nextY, now.cnt + 1));
			}
		}
		return 0;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		// 테스트케이스 수
		int T = Integer.parseInt(br.readLine());
		
		while(T-- > 0) {
			// 체스판의 크기
			N = Integer.parseInt(br.readLine());
			
			// 체스판 초기화
			map = new int[N][N];
			// 방문배열 초기화
			visited = new boolean[N][N];
			
			// 시작좌표 입력
			st = new StringTokenizer(br.readLine());
			sX = Integer.parseInt(st.nextToken());
			sY = Integer.parseInt(st.nextToken());
			
			// 도착좌표 입력
			st = new StringTokenizer(br.readLine());
			eX = Integer.parseInt(st.nextToken());
			eY = Integer.parseInt(st.nextToken());
			
			// 출력
			System.out.println(BFS(sX, sY));
		}
	}
}

---

※ 생각정리 (나이트의 이동)
나이트의 이동문제는 BFS알고리즘을 이용하여 쉽게 해결할 수 있었다.
체스말의 이동을 위해 이동 방향을 담아두었다.
static int[] dx = {-1, -2, -2, -1, 1, 2, 2, 1};
static int[] dy = {-2, -1, 1, 2, 2, 1, -1, -2};
또한 노드 클래스에 좌표뿐만이 아니라 이동횟수를 담을 수 있는 변수하나를 추가하여 이동할때마다 해당 값을 1씩 추가하며 반복문을 이어나갔다.

// 맵의 좌표와 이동 횟수
	static class Node {
		int x, y, cnt;
		public Node(int x, int y, int cnt) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
	}

// 현재좌표에 이동횟수 1을 추가하여 큐에 담는다
q.offer(new Node(nextX, nextY, now.cnt + 1));

큐에서 현재좌표를 뽑아낼때 해당 좌표가 도착해야할 좌표와 같다면 그때의 이동횟수(cnt)를 리턴하고 BFS를 종료한다.
이동 방향만 잘 담아두고 이동한다면 쉽게 해결할 수 있었던 문제이다.
-새벽코딩-