BOJ 7562 나이트의이동

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

 

문제 분석

bfs로 풀어서 목적지까지 도달하면 되는 문제이다.

 

 

문제 풀이

1) 시작좌표와 목적지좌표를 받아서 해당 숫자 내에서 bfs탐색을 한다.

2) bfs 탐색을 하다가 해당 목적지가 나오면 출력할 값과 비교한다. 

3) 최종적으로 모든 영역을 탐색하면 정답을 출력한다.

 

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 Main {
	private static int tc, I, sx, sy, ex, ey, min;
	private static boolean[][] visited;
	private static int[] dr = { -2, -1, 1, 2, 2, 1, -1, -2 };
	private static int[] dc = { 1, 2, 2, 1, -1, -2, -2, -1 };

	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		tc = Integer.parseInt(br.readLine());
		for (int i = 0; i < tc; i++) {
			I = Integer.parseInt(br.readLine());

			StringTokenizer st;
			min = Integer.MAX_VALUE;

			st = new StringTokenizer(br.readLine());
			sx = Integer.parseInt(st.nextToken());
			sy = Integer.parseInt(st.nextToken());

			st = new StringTokenizer(br.readLine());
			ex = Integer.parseInt(st.nextToken());
			ey = Integer.parseInt(st.nextToken());

			visited = new boolean[I][I];

			bfs(sx, sy);
			System.out.println(min);
		}
	}// input()

	private static void bfs(int sx, int sy) {
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(sx, sy, 0));
		visited[sx][sy] = true;

		while (!q.isEmpty()) {
			Node cur = q.poll();
			int r = cur.x;
			int c = cur.y;
			int d = cur.depth;

			if ((r == ex) && (c == ey)) {
				min = d;
				break;
			}

			for (int i = 0; i < 8; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				if (nr >= 0 && nr < I && nc >= 0 && nc < I) {
					if (!visited[nr][nc]) {
						q.add(new Node(nr, nc, d + 1));
						visited[nr][nc] = true;
					}
				}
			}
		}
	}

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

	static class Node {
		int x, y, depth;

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

	}
}