/ BOJ

BOJ_7562_나이트의이동_JAVA

문제 : 나이트의 이동

링크 : BOJ_7562_나이트의이동

접근 방식

나이트가 움직일 수 있는 범위를 단위벡터 배열로 만들어 BFS로 탐색하면 되는 문제이다. 기존에 사방탐색을 BFS로 푸는 문제에서 큰 틀은 그대로였기 때문에, 쉽게 풀 수 있는 문제였다.

풀이 방법

  1. BFS에 사용할 Node 클래스를 하나 만들었다. 멤버변수로는 x,y좌표와 bfs의 깊이를 담을 int변수

  2. 주어진 값을 읽어들여 2차원 배열을 생성해 저장한다. 크기는 N*N크기이다.

  3. 나이트의 현재 위치의 좌표와 이동해야할 위치의 좌표를 읽어들여 나이트의 위치는 클래스로, 이동할 위치는 각각 변수로 저장한다.

  4. 나이트가 이동할 수 있는 종류는 총 8가지 이므로, 해당 이동 좌표에 맞게 dir 배열을 생성해준다. BFS를 통해 탐색을 한다. 각 노드에 대해 한 번 탐색이 이루어질 때마다 depth, 깊이를 1 증가시킨다.

  5. 나이트가 해당 위치로 이동할 수 없는 경우의 수는 없으므로 나이트가 이동해야하는 위치에 처음 도착한 노드의 깊이를 출력하고 종료한다.

소스 코드


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 BOJ_7562_나이트의이동 {

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

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(in.readLine());

		int[][] dir = { { -2, -1 }, { -1, -2 }, { -2, 1 }, { -1, 2 }, { 1, -2 }, { 2, -1 }, { 2, 1 }, { 1, 2 } };

		for (int tc = 0; tc < T; tc++) {
			int N = Integer.parseInt(in.readLine());

			StringTokenizer st = new StringTokenizer(in.readLine()," ");

			Node knight = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);

			st = new StringTokenizer(in.readLine(), " ");

			int endX = Integer.parseInt(st.nextToken());

			int endY = Integer.parseInt(st.nextToken());

			boolean[][] visited = new boolean[N][N];

			Queue<Node> queue = new LinkedList<>();

			queue.offer(knight);
			visited[knight.x][knight.y] = true;
			while (!queue.isEmpty()) {
				Node node = queue.poll();

				if(node.x == endX && node.y == endY) {
					System.out.println(node.depth);
					break;
				}

				for(int d=0;d<8;d++) {
					int dx = node.x + dir[d][0];
					int dy = node.y + dir[d][1];

					if(dx >= 0 && dx < N && dy >= 0 && dy < N && !visited[dx][dy]) {
						visited[dx][dy] = true;
						queue.offer(new Node(dx,dy,node.depth+1));
					}
				}
			}
		}

	}

}

class Node {

	int x;
	int y;
	int depth;

	public Node(int x, int y, int depth) {
		super();
		this.x = x;
		this.y = y;
		this.depth = depth;
	}

}