[백준] code.plus(BFS 알고리즘,JAVA)1600번, 말이 되고픈 원숭이

문제 링크

1600번: 말이 되고픈 원숭이

---

주의사항

• 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. 원숭이는 K번 이하의 체스말 나이트처럼 이동할 수 있습니다.

2. 원숭이는 기본적으로 상하좌우 인접한 칸으로 이동할 수 있습니다.

3. 0은 이동 가능한 칸, 1은 이동 가능하지 않은 칸입니다.

4. 원숭이의 출발 위치는 왼쪽 상단(0, 0), 목적지는 오른쪽 하단(N, M)입니다.

5. 원숭이가 목적지에 도착하는 최소 이동 횟수를 결과로 출력합니다.

 

원숭이는 상하좌우 인접한 칸으로 이동이 가능합니다.

 

dx[] = {0, 0, -1, 1}

dy[] = {-1, 1, 0, 0}

 

원숭이는 K번 이하의 체스말 나이트처럼 이동이 가능합니다.

 

dx[] = {-1, 1, -1, 1, -2, -2, 2, 2};

dy[] = {-2, -2, 2, 2, -1, 1, -1, 1};

 

 

BFS탐색으로 출발 위치에서 목적지까지 원숭이의 최소 이동을 구하였습니다.

 

예제입력 1.

K = 1

해석 : 원숭이는 1번만 체스의 나이트처럼 이동할 수 있습니다.

0(원숭이)	0	0	0
1	0	0	0
0	0	1	0
0	1	0	0(목적지)

 

BFS 탐색 시작!

0	0	0	0
1	0	0(나이트 이동)	0
0	0(나이트 이동)	1	0
0	1	0	0(목적지)

 

BFS 탐색중...

0	0	0	0
1	0	0	0
0	0	1	0
0	1	0	0(목적지)

BFS 탐색중...

0	0	0	0
1	0	0	0
0	0	1	0
0	1	0	0(목적지)

 

BFS 탐색중...!

0	0	0	0
1	0	0	0
0	0	1	0
0	1	0	0(목적지)

 

목적지 도착으로 현재 이동한 횟수 4를 결과로 출력한다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 동물원에 대한 정보를 저장하였습니다.
• 원숭이가 목적지까지 이동를 구하는 bfs함수를 실행하였습니다.
• 원숭이가 목적지까지 최소 이동횟수를 구하는 bfs함수의 결과를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs는 원숭이가 목적지까지 BFS탐색으로 최소 이동횟수를 구하는 함수입니다.
• bfs는 체스의 나이트처럼 이동한 횟수에 따른 x, y값 변경을 위한 Index을 설정하는 setSize를 실행합니다.
• setSize는 원숭이가 나이트처럼 이동한 횟수에 따라 탐색할 dx, dy의 크기를 반환합니다.
• inMap은 이동한 좌표가 동물원 안에 존재하는지 확인하는 함수입니다.

 

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

public class Main {
    
    //bfs탐색에 원숭이 이동에 관한 클래스
    static class position{
        int x, y, knightMove, count;
        public position(int x, int y, int knightMove, int count) {
            this.x = x;
            this.y = y;
            this.knightMove = knightMove;
            this.count = count;
        }
    }
    static int K, H, W;
    static int[][] map;
    //원숭이 이동에 관한 x, y 변경값
    static int dx[] = {0, 0, -1, 1, -1, 1, -1, 1, -2, -2, 2, 2};
    static int dy[] = {-1, 1, 0, 0, -2, -2, 2, 2, -1, 1, -1, 1};
    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;
        K = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine()," ");
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        map = new int[H][W];
        //동물원에 관한 정보 저장
        for(int i=0;i<H;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<W;j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }
        bw.write(bfs(0, 0) + "");	//탐색하여 최소 이동횟수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //원숭이가 목적지에 도착하는 BFS탐색으로 최소 이동횟수를 구하는 함수
    static int bfs(int x, int y){
        Queue<position> queue = new LinkedList<>();
        //방문 확인은 원숭이가 체스의 나이트처럼 이동한 횟수도 구분해서 확인해야 합니다.
        boolean[][][] visited = new boolean[H][W][K+1];
        visited[y][x][0] = true;	//처음 원숭이 위치 방문 확인
        queue.add(new position(x,y,0,0));
        while(!queue.isEmpty()){
            position cur = queue.poll();
            int curX = cur.x;
            int curY = cur.y;
            int knightMove = cur.knightMove;
            int count = cur.count;
            if(curX == W-1 && curY == H-1)	//원숭이 목적지 도착시
                return count;
            int size = setSize(knightMove);
            for(int i=0;i<size;i++){
                int tempX = curX + dx[i];
                int tempY = curY + dy[i];
                if(inMap(tempX,tempY)){
                    if(map[tempY][tempX]==0){
                        if(i<4){                        //상하좌우 이동시
                            if(!visited[tempY][tempX][knightMove]){
                                visited[tempY][tempX][knightMove] = true;
                                queue.add(new position(tempX,tempY, knightMove, count+1));
                            }
                        }else{                        //체스의 나이트처럼 이동시
                            if(!visited[tempY][tempX][knightMove+1]){
                                visited[tempY][tempX][knightMove+1] = true;
                                queue.add(new position(tempX,tempY,knightMove+1, count+1));
                            }
                        }
                    }
                }
            }
        }
        return -1;	//원숭이가 목적지 도착 불가능시.
    }
    //원숭이가 체스의 나이트처럼 이동한 횟수에 따른 변경값 크기 조정
    static int setSize(int knightMove){
        if(knightMove < K)
            return dx.length;
        return 4;
    }
    //동물원에 좌표가 벗어나는지 확인하는 함수
    static boolean inMap(int x, int y){
        if(x>=0 && y>=0 && x<W && y<H)
            return true;
        return false;
    }
}