백준 16948번 : 데스 나이트

 문제

www.acmicpc.net/problem/16948

16948번: 데스 나이트

16948 데스 나이트

 

 구현 방법

 bfs를 사용하여 구현하였습니다. 최소 이동 횟수를 구해야 하므로 bfs를 선택하였습니다.

문제에 제시된 이동으로 델타를 만들어 주위를 탐색해 주었고 갈 수 있다면 queue에 값을 넣어주었습니다.

큐가 비었는데 못찾았으면 -1을 출력해주었습니다.

 

 구현 코드

package BOJ.Silver.bfsdfs;

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 B16948_데스나이트 {
	static int N, cnt, gr, gc;
	static boolean flag;
	static Queue<int[]> bfs;
	static int[][] check;
	static int[][] deltas = {{-2, -1}, {-2, 1}, {0, -2}, {0, 2}, {2, -1}, {2, 1}}; // 데스 나이트 이동
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		gr = Integer.parseInt(st.nextToken()); // 목표 지점
		gc = Integer.parseInt(st.nextToken());
		check = new int[N][N];
		bfs = new LinkedList<>();
		bfs.offer(new int[] {r, c}); // 초기 값 넣어줌
		check[r][c] = 1;
		
		bfsL(); 
		
		if (flag) System.out.println(cnt);
		else System.out.println(-1); // 큐가 비었는데 값을 못찾았다면 -1 출력
	}
	
	static void bfsL() {
		stop:while(!bfs.isEmpty()) {
			cnt++;
			int size = bfs.size();
			for (int i=0;i<size;i++) { // 현재 레벨에서 이동할 수 있는 모든 값들을 탐색 후 cnt 올려주기 위함
				int[] now = bfs.poll();
				for (int d=0;d<deltas.length;d++) {
					int nr = now[0]+deltas[d][0];
					int nc = now[1]+deltas[d][1];
					if (nr==gr && nc==gc) {
						flag = true;
						break stop;
					}
					if (isIn(nr, nc) && check[nr][nc]==0) {
						check[nr][nc]=1;
						bfs.offer(new int[] {nr, nc});
					}
				}
			}
		}
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<N && nc>=0 && nc<N;
	}
}

 

정답!