[백준] code.plus(BFS 알고리즘,JAVA)16948번, 데스 나이트

문제 링크

16948번: 데스 나이트

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

그래프 알고리즘이란?

각 정점과 연결하는 선분의 정보를 가지고 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) .... 등을 이용하여 정점에서 다른 정점으로 가는 최소값, 최대값 등의 문제에서 출력하라는 결과를 구하는 알고리즘입니다.

 

BFS?

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. N × N 크기의 체스판이 존재합니다.

2. 새로운 말인 "데스 나이트"의 이동 경로는 일반적인 나이트와 다르다.

3. 시작 지점에서 도착 지점에 최소 이동 경로를 출력하거나 도착하지 못한다면 -1을 결과로 출력해야 합니다.

 

데스 나이트의 이동 경로

 

x의 변경값 : {-2, -2, 0, 0, 2, 2}

y의 변경값 : {-1, 1, -2, 2, -1, 1}

 

위 변경값을 토대로 BFS탐색을 진행하여 가장 먼저 도착 지점에 도착했을 때 이동 횟수를 결과로 출력하였습니다.

 

BFS 탐색을 진행하였어도 도착 지점에 도착하지 못하였을 때 -1을 결과로 출력하였습니다.

 

예제입력3

 

O : 데스 나이트 현재 위치

X : 데스 나이트가 방문했던 위치

★ : 도착 지점

O				★

첫 번째 탐색 시작!

O
		O
X				★
		O
O

두 번째 탐색 시작!

		O
X				O
		X
X				★(O)
		X
X				O
		O

 

목표 지점 도착!

이동 횟수 : 2번

 

결과로 2을 출력합니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 출발, 도착 위치를 저장하였습니다.
• 출발 위치에서 "다크 나이트"가 이동하여 도착 위치에 가는 최소 이동 횟수를 구하는 bfs함수를 실행하였습니다.
• 도착하지 못할 때는 -1, 도착했을 때는 최소 이동 횟수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 "다크 나이트"의 이동값 dx[], dy[]를 이용하여 BFS 탐색으로 최소 이동횟수를 구하였습니다.
• bfs함수는 도착 위치에 도달하지 못하였을 경우 -1을 반환합니다.

 

import java.util.*;
import java.io.*;

public class Main {
    static int N;
    static boolean[][] board;		//체스판 방문 확인 함수
    static int[] dx = {-2, -2, 0, 0, 2, 2};		//"다크 나이트" x값 변경값
    static int[] dy = {-1, 1, -2, 2, -1, 1};	//"다크 나이트" y값 변경값
    //"다크 나이트" 현재 위치 관련 생성자
    static class position{
        int x, y, count;
        public position(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
    static public void  main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        N = Integer.parseInt(br.readLine());
        board = new boolean[N][N];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //시작 위치, 도착 위치 저장
        int r1 = Integer.parseInt(st.nextToken());
        int c1 = Integer.parseInt(st.nextToken());
        int r2 = Integer.parseInt(st.nextToken());
        int c2 = Integer.parseInt(st.nextToken());
        int result = bfs(r1,c1,r2,c2);		//BFS 탐색 시작
        bw.write(result + "\n");	//결과 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS탐색으로 최소 이동 횟수 및 도착 불가능시 -1 반환하는 함수
    static int bfs(int r1, int c1, int r2, int c2){
        Queue<position> queue = new LinkedList<>();
        board[c1][r1] = true;
        queue.add(new position(r1, c1,0));
        while(!queue.isEmpty()){
            position cur = queue.poll();
            int x = cur.x;
            int y = cur.y;
            int count = cur.count;
            if(x==r2 && y==c2)		//도착 위치 도달시.
                return count;
            //현재 위치에서 "다크 나이트" 이동
            for(int i=0;i<6;i++){
                int tempX = x + dx[i];
                int tempY = y + dy[i];
                if(tempX>=0 && tempY>=0 && tempX<N && tempY<N && !board[tempY][tempX]){
                    board[tempY][tempX] = true;
                    queue.add(new position(tempX,tempY,count+1));
                }
            }
        }
        return -1;		//도달 못했을 때 -1을 반환
    }
}