[BOJ - JAVA] 7562 - 나이트의 이동(BFS)

# 주소

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

7562번: 나이트의 이동

# 문제

# 문제 해설 및 코드 리뷰

import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
	public static int[] dx = {1,2,2,1,-1,-2,-2,-1};
	public static int[] dy = {2,1,-1,-2,-2,-1,1,2};
	public static int n, i, start_x,start_y,end_x, end_y,count;
	public static int arr[][];
	public static ArrayList<Integer> list = new ArrayList<>();
	public static Queue<Point> queue = new LinkedList<>();
    public static void main(String[] args){
    	Scanner scan = new Scanner(System.in);
    	n = scan.nextInt();
    	while(n--> 0) {
    		i = scan.nextInt();
    		arr = new int[i][i];
    		for(int t = 0; t < i; t++) {
    			Arrays.fill(arr[t], -1);
    		}
    		int start_x = scan.nextInt();
    		int start_y = scan.nextInt();
    		int end_x = scan.nextInt();
    		int end_y = scan.nextInt();
    		
    		Point start = new Point(start_x, start_y);
    		
    		queue.offer(start);
    		arr[start_x][start_y] = 0;
    		
    		while(!queue.isEmpty()) {
    			if(start_x == end_x && start_y == end_y) {
    				break;
    			}
    			Point now = queue.remove();
    			int x = now.x;
    			int y = now.y;
    			for(int m = 0; m < 8; m++) {
    				int nx = x + dx[m];
    				int ny = y + dy[m];
    				if(nx >= 0 && nx < i && ny >= 0 && ny < i) {
    					if(arr[nx][ny] == -1) {
    						arr[nx][ny] = arr[x][y] + 1;
    						queue.add(new Point(nx,ny));
    					}
    				}
    			}
    		}
    		System.out.println(arr[end_x][end_y]);
    	}
    }
}

이번에도 BFS문제입니다. ㅋㅋ 확실히 마스터해야할 거 같아서 앞으로 더 풀어볼 생각입니다.

풀어도 풀어도 뭔가 100%가 아닌 느낌이라 당분간 계속 BFS, DFS만 할 것 같습니다.

이 문제는 '나이트의 이동'이란 문젠데, 체스의 개념을 잘 몰라서 조금 헤매기도 했습니다.

근데 이전의 문제들을 풀었던걸 잘 생각해보면서, 나이트의 움직임이 가로 1칸, 세로 2칸으로 움직인다는 옛날의 룰이 떠올랐고 혹시 몰라 dx, dy를 가로, 세로방향으로 정의해서 총 8가지 경우의 수로 나누어 각 움직임을 생각해주어야 한다는 규칙에 도달했습니다. 맞을지 몰랐는데 혹시 몰라서 시간 낭비하기 싫기도 하여 다른 분들이 푼 걸 찾아봤는데 이 접근이 맞더라고요. 그래서 이전 방법과 동일하게 Point를 써서 풀었습니다. 풀이를 시작해볼게요

 

일단 이번에도 Scanner로 입력받았습니다. 아무래도 Buffered를 쓰면 더 빠르고 습관이되면 좋다하지만, 입력할 때 코드량이 너무 많고... 전 귀찮은게 질색이라서 그냥 Scanner로 코딩하는 편입니다. 필요시에만 Buffered를 이용합니다..

그리고 while문 안으로 들어가서 n의 값을 줄여줄 때마다(테스트 케이스의 총 개수) 새로운 경우의 수를 구해주는 문제입니다. 그렇기 때문에 i를 입력받을 때 이 i는 배열의 가로,세로의 길이이고 arr의 크기는 각각 i,i이며 start_x와 start_y는 시작점을 의미하고 end_x, end_y는 우리가 도달해야할 점을 의미합니다.

Point start는 하나의 점으로서 우리의 시작점을 의미합니다. 이 start점을 queue에 담은 후 arr의 시작 점 값을 0으로 지정하겠습니다. 그리고 while문 안으로 들어가는데, 예전에도 설명했듯이 queue를 이용하여 문제를 풀때는 while(!queue.isEmpty())를 정말 자주 이용하니 참고해주시길 바랍니다!

우리가 원하는 것은 start_x와 start_y가 각각 end_x, end_y에 도달하는 것이 목표이므로 만약 이 값들이 end에 도달하면 break;를 이용하여 while문을 빠져나오게 코딩합니다. 이후 도달하지 못했을 경우 Point now = queue.remove()를 썼는데, queue.poll()를 하셔도 됩니다. 그리고 x는 현재의 x점, y는 현재의 y점이고 for문으로 들어가, nx와 ny를 아까 정적 변수로 지정해두었던 dx,dy의 값을 각각 더해주며 nx와 ny를 정립합니다. 이때 nx와 ny는 0보다 크거나 같고 i보다 작아야 한다는 것을 꼭 if안에 넣어주시고 arr가 -1일 때(방문하지 않았음을 의미) arr의 새 위치에 기존 arr의 값을 +1해주어 다시 queue에 넣습니다.

그렇게 되면 나이트로 이동할 수 있는 값을 queue에 담을 수 있는데, 이 때 nx와 ny를 담으면서 이 것이 end에 도달했는지를 보게끔 위에 설계를 해놓았으므로 만약 break되어 밖으로 나오면! 그것의 인덱스 값을 출력해야 정답이 되는 것입니다.

 

어려우시면 꼭 댓글 남겨주세요! 저도 아직 부족한 것이 많아서 소통하면서 배울 수 있음 좋겠네요.

감사합니다.