백준 7562. 나이트의 이동 (BFS)

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

문제제목 : 나이트의 이동

문제난이도 : 실버2

문제유형 : BFS

 

문제

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

입력

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

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

출력

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

아이디어

1. 문제 : 주어진 시작점으로부터 나이트(체스)가 목적지까지 최단 이동 회수를 구하는 문제
2. 요구사항 : 
   1. 테스트케이스 개수, 체스판 크기, 나이트 말의 시작 위치, 도착위치를 입력받는다.
   2. 나이트의 현재 위치가 (n,n)일 경우 이동할 수 있는 위치는 (n-2, n-1),(n-1, n-2), (n-2, n+1), (n-1, n+2), (n+1, n+ 2), (n+2, n+1), (n+1, n-2), (n+2, n-1) 이다.
   3. 도착위치까지의 최단 이동 횟수를 출력해야한다.

문제풀이

1. 체스판은 2차원배열로 선언한다.
2. 앞에서 방문했던 위치는 다시 방문할 필요가 없으므로 방문유무를 알 수 있는 2차원배열을 선언한다.
3. 최단 이동 거리를 구하기 위해 BFS 알고리즘을 사용한다.

코드

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

public class BOJ7562 {
	public static int[] dx = { -2, -1, -2, -1, 1, 2, 1, 2 };
	public static int[] dy = { -1, -2, 1, 2, 2, 1, -2, -1 };
	public static boolean[][] visited;
	public static int[][] count;
	public static int tc, n;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		tc = Integer.parseInt(br.readLine()); //tc개수
		
		for (int i = 0; i < tc; i++) {
			n = Integer.parseInt(br.readLine());

			visited = new boolean[n][n];
			count = new int[n][n];

			String[] pos_input = br.readLine().split(" ");
			int start_x = Integer.parseInt(pos_input[0]);
			int start_y = Integer.parseInt(pos_input[1]);

			String[] de_input = br.readLine().split(" ");
			int end_x = Integer.parseInt(de_input[0]);
			int end_y = Integer.parseInt(de_input[1]);

			BFS(new Pos(start_x, start_y), new Pos(end_x, end_y));

			bw.write(String.valueOf(count[end_x][end_y]) + "\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}

	public static void BFS(Pos start, Pos end) {
		Queue<Pos> q = new LinkedList<>();
		q.add(start);
		visited[start.x][start.y] = true;

		while (!q.isEmpty()) {
			Pos now = q.poll();

			if (now.x == end.x && now.y == end.y) {
				return;
			}

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

				if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
					continue;
				}

				if (!visited[nx][ny]) {
					visited[nx][ny] = true;
					count[nx][ny] = count[now.x][now.y] + 1;
					q.add(new Pos(nx, ny));
				}
			}
		}

	}
}

class Pos {
	int x;
	int y;

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

 

---

신난다~!