[백준] 7562 나이트의 이동 - Graph Theory / Java

• 문제 링크

7562번: 나이트의 이동

 

• 풀이 과정

나이트의 이동을 구현할 방향 배열을 8방향으로 설정해둔다.

시작점과 도착점을 매개변수로 받아 bfs 탐색을 수행하며

시작점을 큐에 삽입 및 방문했음을 표시하기 위해 1로 값을 지정한다.

 

일반적인 bfs 탐색을 수행하되 각 다음 방문할 위치마다 현재 위치의 값 + 1 을 설정하여

해당 위치에 도달하기까지 몇 번을 이동했는지 나타낸다.

 

현재 위치가 도착점일 경우 bfs 함수를 빠져나가고

처음 시작점을 방문했음을 표시하기 위해 1로 설정했고 이는 이동 횟수를 의미하지 않으므로,

도착점에 설정된 나이트의 이동 횟수에 1을 뺀 값을 한 테스트 케이스 당 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

	static int l;
	static int[][] visit;
	static int[] dy = { 1, 1, -1, -1, 2, 2, -2, -2 };
	static int[] dx = { 2, -2, 2, -2, 1, -1, 1, -1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int t = Integer.parseInt(br.readLine());
		for (int i = 0; i < t; i++) {
			l = Integer.parseInt(br.readLine());
			visit = new int[l][l];

			st = new StringTokenizer(br.readLine());
			Node root = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			st = new StringTokenizer(br.readLine());
			Node dest = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

			bfs(root, dest);
			bw.write(visit[dest.y][dest.x] - 1 + "\n");
		}

		bw.flush();
	}

	private static void bfs(Node root, Node dest) {
		Queue<Node> q = new LinkedList<>();
		q.offer(root);
		visit[root.y][root.x] = 1;

		while (!q.isEmpty()) {
			Node now = q.poll();
			if (now.y == dest.y && now.x == dest.x) 
				return;

			for (int i = 0; i < 8; i++) {
				int ny = now.y + dy[i];
				int nx = now.x + dx[i];

				if (ny < 0 || nx < 0 || ny >= l || nx >= l)
					continue;
				if (visit[ny][nx] != 0)
					continue;

				q.offer(new Node(ny, nx));
				visit[ny][nx] = visit[now.y][now.x] + 1;
			}
		}
	}

	private static class Node {
		int y;
		int x;

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

}