[백준] 7562 : 나이트의 이동 - 자바(JAVA)

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

7562번: 나이트의 이동

 

문제해석

 

나이트는 다음그림과 같이 이동할 수 있습니다.

나이트가 이동하려는 칸이 주어질때 나이트는 몇 번 움직여서 목적지로 이동할 수 있을까요?

 

입력

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

 

각 테스트 케이스는 3줄로 이루어져 있습니다.

1. 체스판의 한 변의 길이 l 이 주어집니다. (체스판의 크기는 l x l 입니다)

2. 나이트가 현재 있는 칸이 주어집니다.

3. 나이트가 이동하려고 하는 칸이 주어집니다.

 

제약조건

4<= l <= 300

 

출력

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

 

문제 풀이 전 설계

 

나이트가 좌표계를 움직이며 최단 거리로 이동하는 방법을 찾아야 합니다.

DFS 와 BFS가 떠오르지만 최단 거리로 이동해야 하므로 BFS를 사용하면 될 것 같습니다.

보통 좌표의 탐색을 상하좌우로 하지만 여기서 특이한점은 나이트의 특별한 이동이 있기 때문에 이를 고려하면 됩니다.

만약 나이트가 방문한곳을 또 방문하는경우는? 절대 최단거리가 될 수 없습니다.

 

 

코드

package day0208;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Knight {
	int currentY;
	int currentX;
	int moveCount;

	Knight(int currnetY, int currentX, int moveCount) {
		this.currentY = currnetY;
		this.currentX = currentX;
		this.moveCount = moveCount;
	}
}

class Destination {
	int destinationX;
	int destinationY;

	Destination(int destinationY, int destinationX) {
		this.destinationY = destinationY;
		this.destinationX = destinationX;
		
	}
}

public class Main_7562_나이트의이동 {

	// 좌상2개 , 우상 2개, 우하 2개, 우좌 2개
	static int[] dy = { -1, -2, -2, -1, 2, 1, 2, 1 };
	static int[] dx = { -2, -1, 1, 2, 1, 2, -1, -2 };
	static final int SEARCH_COUNT = 8;

	static int size;
	static int[][] chessBoard;
	static boolean[][] visited;
	static Queue<Knight> queue = new LinkedList<Knight>();

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCase = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		for (int t = 0; t < testCase; t++) {
			// 보드 초기화
			size = Integer.parseInt(br.readLine());
			chessBoard = new int[size][size];
			visited = new boolean[size][size];

			// 나이트 위치
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			Knight knight = new Knight(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);

			// 목적지
			st = new StringTokenizer(br.readLine(), " ");
			Destination destination = new Destination(Integer.parseInt(st.nextToken()),
					Integer.parseInt(st.nextToken()));

			// 메인로직 BFS
			queue.add(knight);
			visited[knight.currentY][knight.currentX] = true;

			while (!queue.isEmpty()) {
				
				Knight tempKnight = queue.poll();
				if (isArrived(tempKnight, destination)) {
					sb.append(tempKnight.moveCount + "\n");
					break;
				}

				tempKnight.moveCount++;

				for (int i = 0; i < SEARCH_COUNT; i++) {
					int tempY = tempKnight.currentY + dy[i];
					int tempX = tempKnight.currentX + dx[i];
					if (!isValid(tempY, tempX)) {
						continue;
					}
					queue.add(new Knight(tempY, tempX, tempKnight.moveCount));
					visited[tempY][tempX] = true;
				}
			}
			queue.clear();
		}

		System.out.print(sb.toString());

	}

	// 나이트의 목적지 도착 검사
	static boolean isArrived(Knight k, Destination d) {
		return (k.currentX == d.destinationX && k.currentY == d.destinationY);
	}

	// 유효성 검사 : 배열 index + visited
	static boolean isValid(int tempY, int tempX) {
		return (tempY >= 0 && tempX >= 0 && tempY <= size-1 && tempX <= size-1 && visited[tempY][tempX] != true);
	}

}