[백준] 나이트의 이동(java) Bfs

2020-02-26

나이트의 이동 (백준> Dfs_Bfs)

문제 링크

문제설명

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

img

입력

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

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

출력

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

예제 입력 1 복사

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1 복사

5
28
0


풀이

package Dfs_Bfs;

import java.util.*;

//40min
public class beak_나이트의이동 {

	static class Pos{
		int x;
		int y;
		int cnt;
		
		Pos(int x,int y,int cnt){
			this.x =x;
			this.y =y;
			this.cnt = cnt;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n=sc.nextInt();
		
		for(int i=0;i<n;i++) {
			int m = sc.nextInt();
			int arr[][] = new int[m][m];
			
			sc.nextLine();
			
			Queue<Pos> qu = new LinkedList<>();
			String a[] = sc.nextLine().split(" ");
			qu.add(new Pos(Integer.parseInt(a[0]),Integer.parseInt(a[1]),0));
			arr[Integer.parseInt(a[0])][Integer.parseInt(a[1])] = 1;
			
			String b[] = sc.nextLine().split(" ");
			int endx = Integer.parseInt(b[0]); int endy = Integer.parseInt(b[1]);
			
			while(!qu.isEmpty()) {
				Pos now = qu.poll();
				int nowx = now.x;
				int nowy = now.y;
				
				if(nowx == endx && nowy == endy) {
					System.out.println(now.cnt);
					break;
				}
				
				int dx[] = {-2,-2,-1,-1, 1,1, 2,2};
				int dy[] = {-1, 1,-2, 2,-2,2,-1,1};
				
				for(int j=0; j<8; j++) {
					int nx = nowx + dx[j];
					int ny = nowy + dy[j];
					
					if(nx>=0&&nx<m &&ny>=0&&ny<m && arr[nx][ny]==0){
						arr[nx][ny] = 1;
						qu.add(new Pos(nx,ny,now.cnt+1));
					}
				}
				
			}//while
			
		}
	}
}

후기 (40min)

사방에서 8개로 나뉘었을 뿐 일반 bfs랑 다를거 없는 문제였다!