[백준, Java] 18404번, 현명한 나이트, (그래프 탐색, BFS)

문제 링크

18404번: 현명한 나이트

---

주의사항

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

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

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 나이트의 위치와 상대방의 말이 주어집니다.

2. 나이트가 상대방의 말을 잡을 때 걸리는 최소 이동 횟수를 결과로 출력합니다.

3. 상대방 말은 항상 나이트가 잡을 수 있는 위치에 존재합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. BFS을 통해서 나이트의 위치를 탐색하며 상대방의 말을 잡습니다.

 

3. 탐색이 끝난 뒤 상대방의 말을 잡는 최소 이동횟수를 결과로 출력합니다.

 

나이트의 이동

나이트의 위치는 문제에서 설명한 것처럼 이동하는 것을 배열로 표현하면

 

y축 이동 관련 배열 : {-1, -2, -2, -1, 1, 2, 2, 1}

 

x축 이동 관련 배열 : {-2, -1, 1, 2, -2, -1, 1, 2}

 

BFS(나이트 이동 탐색)

 

BFS을 이용해서 나이트의 이동을 진행합니다.

 

각 이동을 진행할 때마다 이동하는 횟수를 변수로 저장한 뒤, Queue.size()만큼 탐색할 때마다 +1을 진행해주면서 탐색을 진행하였습니다.

 

나이트가 움직이면서 각 상대방의 말에 최초로 도착하였을 때 이동한 횟수를 구합니다.

 

※예제 입력 과정을 살펴보시면 이해하시기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 5

 

M : 3

 

체스판 정보

 

			K
	E			E
				E

 

2. BFS을 통해서 나이트의 위치를 탐색하며 상대방의 말을 잡습니다.

 

1번째 나이트 이동 탐색

 

 

	X
			K
	E(X)			E
		X		E(X)

 

 

 

2번째 나이트 이동 탐색

 

X	X	X
	X		K
X	E(X)	X		E(X)
		X	X	E(X)
X		X		X

 

모든 상대방 말 잡기 완료!

 

 

3. 탐색이 끝난 뒤 상대방의 말을 잡는 최소 이동횟수를 결과로 출력합니다.

 

(3, 2) : 1

 

(3, 5) : 2

 

(4, 5) : 1

 

1 2 1 을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 나이트와 상대방 말의 정보를 띄어쓰기 기준 나누었습니다.
• search함수를 통해서 각 상대방 말을 잡는 최소 이동 횟수를 탐색합니다.
• 탐색이 끝난 뒤 각 상대방 말을 잡는 최소 이동 횟수들을 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 BFS을 통해서 나이트의 이동을 진행하여 상대방 말들을 잡는 과정을 진행합니다.
• search함수는 최초로 상대방 말을 잡았을 때 이동 횟수를 구합니다.
• inSpace함수는 나이트가 이동할 때 체스판에 존재하는 공간인지 확인합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
    //BFS을 진행할 때 위치 정보 관련 클래스
    static class Pos{
        int r, c;
        public Pos(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    //체스판에 상대방 말을 저장하는 배열
    static int[][] board;
    //상대방 말에 대해서 최소 이동 횟수 저장하는 배열
    static int[] result;
    static int N, M;
    //나이트 이동 관련 배열
    static int[] dr = {-1, -2, -2, -1, 1, 2, 2, 1};
    static int[] dc = {-2, -1, 1, 2, -2, -1, 1, 2};
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = new int[N+1][N+1];
        st = new StringTokenizer(br.readLine()," ");
        int X = Integer.parseInt(st.nextToken());
        int Y = Integer.parseInt(st.nextToken());
        //상대방 말 정보 저장
        for(int i=1;i<=M;i++){
            st = new StringTokenizer(br.readLine()," ");
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            board[A][B] = i;	//i는 순서에 대한 인덱스
        }
        result = new int[M+1];
        //BFS 탐색 진행
        search(X, Y);
        //BFS을 통해 얻은 상대방 말에 최소 이동 횟수 BufferedWriter 저장
        for(int i=1;i<=M;i++){
            bw.write(String.valueOf(result[i]));
            bw.newLine();
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS을 이용해서 나이트의 이동을 진행 및 상대방 말의 최소 이동 횟수 구하는 함수
    static void search(int r, int c){
        //BFS에 사용할 Queue
        Queue<Pos> queue = new ArrayDeque<>();
        //방문 확인 배열
        boolean[][] visited = new boolean[N+1][N+1];
        //시작 나이트 위치 정보 저장
        visited[r][c] = true;
        queue.add(new Pos(r, c));
        int cnt = 0;	//나이트 이동한 횟수
        int idx = M;	//상대방 말 남은 개수
        while(!queue.isEmpty()){
            int size = queue.size();
            //상대방 말을 모두 잡았을 때
            if(idx == 0){
                break;
            }
            //현재 이동 횟수에서 나이트 이동하기
            for(int i=0;i<size;i++){
                Pos cur = queue.poll();
                //현재 위치가 상대방 위치일 때
                if(board[cur.r][cur.c] > 0){
                    result[board[cur.r][cur.c]]= cnt;
                    idx--;
                }
                //나이트 이동 진행
                for(int j=0;j<8;j++){
                    int nr = cur.r + dr[j];
                    int nc = cur.c + dc[j];
                    //이동 가능한 체스판 공간일 때
                    if(inSpace(nr, nc) && !visited[nr][nc]){
                        visited[nr][nc] = true;
                        queue.add(new Pos(nr, nc));
                    }
                }
            }
            cnt++;	//이동한 횟수 증가
        }
    }
    //나이트가 이동하려는 공간이 체스판 안에 존재하는지 확인하는 함수
    static boolean inSpace(int r, int c){
        //체스판에 이동이 가능할 때
        if(r >= 1 && c >= 1 && r <= N && c <= N){
            return true;
        }
        return false;	//체스판에 없는 공간일 때
    }
}