백준 | 7562번. 나이트의 이동 - BFS 풀이

⬛ 백준 7562번. 나이트의 이동 - BFS 풀이

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

7562번: 나이트의 이동

문제

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

문제 그림

입력

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

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

출력

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

---

💚나의 풀이

• 문제의 그림을 보게 되면 나이트의 현재 위치에서 갈 수 있는 위치는 (5X5 범위 내로) 8가지 방향으로 제한되어 있다.
• 이를 이용하여 dx, dy 를 추론해야 풀 수 있는 문제이다.

dx, dy 추론 설명

• 위위의 그림을 토대로 현재 나이트의 위치를 1번 이동 시킬 때마다 뻗어갈 수 있는 위치가 8가지씩 있기 때문에 BFS로 너비우선 탐색을 시도 하다가 목적지 좌표 발견 시 return 하면 된다.

map[][] -> 최소 이동 횟수 result[][] 표현

• result[][] 2차원 배열에 기존 값보다 더 작게 이동 가능한 횟수를 업데이트하며 뻗어가는 방식을 택했다.
• 이떄 주의할 점은 result[][] 에 담기는 값이 ‘최소 이동 횟수’ 이기 때문에 최초에는 Integer.MAX_VALUE로 초기화 해야 한다는 것이다.
• 시작점은 result[][] 값도 0으로 세팅해주고, 이후 BFS로 1번 뻗어갈 때마다 기존 값보다 현재 cur 좌표에서 +1로 이동한 횟수가 더 작으면 갱신해주며 뻗어간다.
• 그러다 목표지점 발견 시 result[ed[0][ed[1]] 을 리턴하면 해당 값에 최소 이동 횟수가 담겨있다!

💚나의 코드

package to_1220_1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

/**
 * 7562번. 나이트의 이동 - BFS 문풀 
 * @author MYLG
 *
 */
public class Main {
	//8방향으로 뻗어감 
	static int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
	static int[] dy = {-1, -2, -2, -1, 1, 2, 2, 1};
	
	static int TC;
	static int I;
	static int[][] map;
	
	//BFS
	static int BFS(int[] st, int[] ed) {
		int[][] result = new int[I][I];
		
		for(int i=0; i<I; i++) {
			Arrays.fill(result[i], Integer.MAX_VALUE);
		}
		
		Queue<int[]> Q = new LinkedList<>();
		boolean[][] visited = new boolean[I][I];
		Q.offer(new int[] {st[0], st[1]});
		visited[st[0]][st[1]] = true;
		result[st[0]][st[1]] = 0;
		
		while(!Q.isEmpty()) {
			int[] cur = Q.poll();
			//목표지점
			if(cur[0] == ed[0] && cur[1] == ed[1]) { //발견하면
				return result[ed[0]][ed[1]];
			}
			
			for(int k = 0; k<8; k++) { //1번에 뻗어갈 수 있는 방향들임 
				int nx = cur[0] + dx[k];
				int ny = cur[1] + dy[k];
				//범위 벗어나거나 이미 방문한 좌표인 경우 넘어가고 
				if(nx <0 || nx >=I || ny <0 || ny >= I) continue;
				
				if(!visited[nx][ny]) {
					if(result[nx][ny] > result[cur[0]][cur[1]] + 1) {
						result[nx][ny] = result[cur[0]][cur[1]] + 1;
						visited[nx][ny] = true;
						Q.offer(new int[] {nx, ny});
					}
				}
			}
		}
		return 0;
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		
		TC = kb.nextInt();
		
		List<Integer> answer = new ArrayList<>();
		
		for(int t=0; t<TC; t++) {			
			I = kb.nextInt();
			map = new int[I][I];
			
			int[] st = new int[2];
			int[] ed = new int[2];
			
			st[0] = kb.nextInt();
			st[1] = kb.nextInt();
			
			ed[0] = kb.nextInt();
			ed[1] = kb.nextInt();
			
			answer.add(BFS(st, ed));
		}
		
		for(int x : answer) System.out.println(x);
	}
}