[BOJ 7562] 나이트의 이동

문제

• BOJ 7562
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

BFS를 사용해서 풀린 문제이다. 다른 문제와 마찬가지로 for문을 돌면서 얻은 다음 좌표가 범위 안에 있고, 아직 방문하지 않았다면 큐에 넣고 다시 다음 좌표를 검사하는 흐름으로 탐색이 진행된다. map배열에는 출발점으로부터의 이동 거리(큐를 한번 비웠을 때)를 넣었기 때문에 방문체크는 따로 배열을 만들지 않고 map배열값이 0인 경우로 구분을 해주었다. 다른 문제들과 다르게 좌,우,상,하 방향이 아니라는 점때문에 살짝 헷갈렸으나 원리를 이해하면 쉽게 풀리는 문제이다.

코드

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

//DFS와 BFS
```java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Boj_7562 {

	static int T;
	static int N;// 체스판 한변의 길이
	static int map[][]; // 체스판
	static Queue<Point> queue;
	static int toX, toY;
	static int[] di = {2,1,-1,-2,-2,-1,1,2};
	static int[] dj= {1,2,2,1,-1,-2,-2,-1};
	static String[] input;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];

			input = br.readLine().split(" "); // 출발 좌표
			queue = new LinkedList<Point>();
			queue.offer(new Point(Integer.parseInt(input[0]), Integer.parseInt(input[1]))); // 출발좌표 큐에 넣기

			input = br.readLine().split(" "); // 도착 좌표
			toX = Integer.parseInt(input[0]);
			toY = Integer.parseInt(input[1]);

			// BFS ㄱㄱ
			int cnt = 1;
			while (!queue.isEmpty()) {
				int size = queue.size();
				for(int i=0; i<size; i++) {
					Point current = queue.poll(); // 큐에서 하나 꺼냄
					int x = current.x;
					int y = current.y;
					
					if(x == toX && y == toY) break; 
					
					for (int dir = 0; dir < 8; dir++) {
						int nx = x + di[dir];
						int ny = y+ dj[dir];
						
						// 범위 체크
						if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] == 0) {
							map[nx][ny] = cnt;
							queue.offer(new Point(nx, ny));
						}
					}
				}
				cnt++;
			}
			System.out.println(map[toX][toY]);
		}
	}

	public static class Point {
		private int x;
		private int y;

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