[백준/Java] 7562: 나이트의 이동

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

 

 

조건

• TimeLimit = 1s
• 나이트의 출발지와 목적지 정보가 주어질 때, 목적지로 이동하기 위한 최소 이동횟수를 출력하라
• 체스판은 n*n 크기이다 (4<=n<=300)

 

풀이

• 완전탐색
  • 최소를 찾아야 하므로 bfs 사용
  • n이 최대 300이므로 O(9만)에서 가능하지만, 나이트의 이동 방향에 제약이 걸려있어서 더 빠르게 처리 가능
  • 1시방향을 0으로 시작해서 시계방향으로 index를 부여한다면, 움직임은 다음과 같다
    dr = { -2, -1, 1, 2, 2, 1, -1, -2 }
    dc = {1, 2, 2, 1, -1, -2, -2, -1 }

 

코드

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




public class Main {

	static int n;
	static int t;
	static BufferedReader br;
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int cnt;
	static boolean[][] visited;
	static int[] dr = { -2, -1, 1, 2, 2, 1, -1, -2 };
	static int[] dc = { 1, 2, 2, 1, -1, -2, -2, -1 };



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

		// input
		br = new BufferedReader(new InputStreamReader(System.in));
		t = Integer.parseInt(br.readLine());

		// solution
		for (int i=0; i<t; i++) solution();

		// result
		System.out.print(sb);

	}



	static void solution() throws IOException {

		// input
		n = Integer.parseInt(br.readLine());

		st = new StringTokenizer(br.readLine());
		Node stt = new Node(
			Integer.parseInt(st.nextToken()),
			Integer.parseInt(st.nextToken()),
			0);

		st = new StringTokenizer(br.readLine());
		Node target = new Node(
			Integer.parseInt(st.nextToken()),
			Integer.parseInt(st.nextToken()),
			0);

		// bfs
		cnt = 0;
		visited = new boolean[n][n];
		bfs(stt, target);

		// result
		sb.append(cnt).append("\n");
	}



	static void bfs(Node stt, Node target) {

		Deque<Node> q = new ArrayDeque<>();
		q.add(stt);
		visited[stt.r][stt.c] = true;

		while (!q.isEmpty()) {

			Node cur = q.pop();

			if (cur.r == target.r && cur.c == target.c) {
				cnt = cur.move;
				return;
			}

			for (int i=0; i<8; i++) {

				int nr = cur.r + dr[i];
				int nc = cur.c + dc[i];

				if (nr<0 || nr>=n || nc<0 || nc>=n) continue;
				if (visited[nr][nc]) continue;
				visited[nr][nc] = true;

				q.add(new Node(nr, nc, cur.move + 1));
			}
		}
	}



	static class Node {

		int r;
		int c;
		int move;

		Node(int r, int c, int move) {
			this.r = r;
			this.c = c;
			this.move = move;
		}

	}


}