[백준 알고리즘] 백준 16948번 데스 나이트 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 16948번 데스 나이트 자바(Java)

1) 문제번호 : 16948번

 

2) 문제 출처

www.acmicpc.net/problem/16948

16948번: 데스 나이트

 

2. 문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

 

3. 제약사항

- 

4. 입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.

 

5. 출력

첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

 

6. 풀이

- BFS의 가장 기본적인 문제다.

- 위치를 받아서 큐에 넣고, 6방면 탐색을 한다.

- 체스판 범위를 넘어가거나 방문을 했으면 다시 돌아간다.

- 탐색하면서 도착해야하는 열과 행의 위치가 됐으면 이동 횟수를 1 증가시켜 출력하고 종료한다.

- 도착못했으면 방문 체크하고, 다시 큐에 넣어 BFS 돌렸는데도 도착못했으면 종료한다.

 

7. 소스 코드

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

//데스나이트 객체
class knight{
	int r; // 열
	int c; // 행
	int cnt; // 이동 횟수
	knight(int r, int c, int cnt){
		this.r = r;
		this.c = c;
		this.cnt = cnt;
	}
}

public class Main {
	static int N; // 체스판의 크기
	static int r1, c1; // 데스 나이트 위치
	static int r2, c2; // 데스 나이트가 도착해야하는 위치
	
	static int[][] board; // 체스판
	static boolean[][] check; //방문체크
	
	static int[] dr = {-2, -2, 0, 0, 2, 2}; //문제에 나온 열 좌표 
	static int[] dc = {-1, 1, -2, 2,-1, 1}; //문제에 나온 행 좌표
	
	static int result = Integer.MAX_VALUE;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); // 체스판의 크기
		
		board = new int[N+1][N+1]; // 체스판
		check = new boolean[N+1][N+1]; // 방문체크
		
		r1 = sc.nextInt(); // 데스 나이트 열 위치
		c1 = sc.nextInt(); // 데스 나이트 행 위치
		r2 = sc.nextInt(); // 데스 나이트가 도착해야하는 열 위치
		c2 = sc.nextInt(); // 데스 나이트가 도착해야하는 행 위치
		
		BFS();
		
	}
	
	public static void BFS() {
		Queue<knight> que = new LinkedList<knight>();
		que.add(new knight(r1,c1,0));
		check[r1][c1] = true;
		
		while(!que.isEmpty()) {
			knight k = que.poll();
			
			//6방면 탐색
			for(int i=0;i<6;i++) {
				int nr = k.r + dr[i];
				int nc = k.c + dc[i];
				
				//체스판 범위를 넘어가거나 방문을 했으면
				if(nr<0 || nc<0 || nr>N || nc>N || check[nr][nc]) continue;
				
				//탐색하면서 도착해야하는 열과 행의 위치가 됐으면 이동 횟수를 1 증가시켜 출력하고 종료
				if(nr==r2 && nc==c2) {
					System.out.println(k.cnt+1);
					System.exit(0);
				}
				
				//도착못했으면 방문 체크하고, 다시 큐에 넣어
				check[nr][nc] = true;
				que.add(new knight(nr,nc,k.cnt+1));
			}
		}
		
		//BFS 돌렸는데도 도착못했으면 종료
		System.out.println(-1);
		
	}
}

 

---