[백준] code.plus(BFS 알고리즘,JAVA)16236번, 아기 상어

문제 링크

16236번: 아기 상어

---

주의사항

• 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. 상어의 처음 크기는 2입니다.

2. 상어는 자신보다 작거나 같은 공간에 이동할 수 있습니다.

3. 상어는 자신보다 크기가 작은 물고기만 잡아먹을 수 있습니다.

4. 상어의 크기가 커지는 것은 현재 크기의 물고기 개수만큼 먹었을 때 증가합니다.

5. 잡아먹을 수 있는 물고기를 모두 잡아먹을 경우 엄마 상어를 부릅니다.

6. 거리가 똑같은 물고기가 존재시 좌상단에 있는 물고기를 우선으로 합니다.

6. 엄마 상어를 부를 때 상어가 활동한 시간을 결과로 출력합니다.

 

입력받은 공간에서 물고기를 잡아먹은 위치를 기준으로 BFS탐색을 반복하고 더 이상 잡아먹을 물고기가 없는 경우 활동한 시간을 결과로 출력하도록 하였습니다.

 

 

예제입력 3.

 

아기 상어 위치에서 먹을 수 있는 물고기 BFS 탐색

4	3	2	1
0	0	0	0
0	0	9(아기상어)	0
1	2	3	4

상어 크기 : 2

가장 가까운 물고기 : (3, 0), (0, 3)

거리가 같을 때 우선순위로 위쪽, 왼쪽을 기준으로 (3, 0)을 잡아먹기

소요 시간 : 3

 

아기 상어 위치에서 먹을 수 있는 물고기 BFS 탐색

4	3	2	0(아기상어)
0	0	0	0
0	0	0	0
1	2	3	4

상어 크기 : 2

가장 가까운 물고기 : (0, 3)

(0, 3) 물고기 잡아먹기

소요 시간 : 6

 

아기 상어 위치에서 먹을 수 있는 물고기 BFS 탐색

4	3	2	0
0	0	0	0
0	0	0	0
0(아기 상어)	2	3	4

상어 크기 : 3

가장 가까운 물고기 : (1, 3)

(1, 3) 물고기 잡아먹기

소요시간 : 1

 

아기 상어 위치에서 먹을 수 있는 물고기 BFS 탐색

4	3	2	0
0	0	0	0
0	0	0	0
0	0(아기 상어)	3	4

상어 크기 : 3

가장 가까운 물고기 : (0, 2)

(0, 2) 물고기 잡아먹기

소요시간 : 4

 

아기 상어 위치에서 먹을 수 있는 물고기 BFS 탐색

4	3	0(아기 상어)	0
0	0	0	0
0	0	0	0
0	0	3	4

상어 크기 : 3

가장 가까운 물고기 : X

엄마 상어 부르기!

 

현재까지 소요된 시간 : 3 + 6 + 1 + 4 = 14

 

결과로 14을 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 공간에 대한 값들을 저장하였습니다.
• 아기상어에 위치에 따라 BFS탐색으로 물고기들을 잡아먹는 bfs함수를 반복 실행하였습니다.
• 총 소요시간을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 아기 상어 위치에서 BFS 탐색을 진행합니다.
• bfs함수는 물고기를 먹었다면 소요시간, 도달하지 못하면 -1 반환한다.
• bfs함수는 공간을 이동할 때에는 현재 아기 상어 크기 이하인 칸을 이동합니다.
• bfs함수는 물고기를 먹을 때에는 현재 아기 상어 크기보다 작은 것만 먹습니다.

 

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

public class Main {
	//현재 상어의 위치 및 소요 시간 관련 클래스
    static class position implements Comparable<position>{
        int x,y,count;
        public position(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
        //거리가 같을 때 위쪽, 왼쪽 기준 우선순위로 정렬
        @Override
        public int compareTo(position o) {
            if(this.count == o.count){		//거리가 같을 때
                if(this.y == o.y){		//위쪽 우선순위
                    return this.x - o.x;
                }else		//왼쪽 우선순위
                    return this.y - o.y;
            }else
                return this.count - o.count;
        }
    }
    static int N, result = 0;
    static int curX=0, curY=0, curSize=2, eatingCount = 0;
    static int[] dx = {0, 0, -1, 1};		//상하좌우 x값 변경값
    static int[] dy = {-1, 1, 0, 0};		//상하좌우 y값 변경값
    static int[][] box;		//공간 저장 배열
    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
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        box = new int[N][N];
        //입력되는 공간 저장 및 현재 아기 상어 위치 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<N;j++){
                box[i][j] = Integer.parseInt(st.nextToken());
                if(box[i][j] == 9){
                    curX = j;
                    curY = i;
                }
            }
        }
        box[curY][curX] = 0;		//현재 아기 상어 위치 0으로 변환
        while(true){		//아기 상어에 먹을 수 있는 물고기가 없을 때까지 BFS 탐색
            int temp = bfs();	//BFS 탐색 시작
            if(temp == -1)		//먹을 수 있는 물고기 존재 없을 때
                break;
            result += temp;		//소요시간 더하기
            if(eatingCount == curSize){		//먹은 횟수에 따라 사이즈 증가
                eatingCount = 0;
                curSize++;
            }
        }
        bw.write(result + "\n");	//총 소요시간 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //아기 상어 위치에서 물고기 탐색하는 BFS 함수
    static int bfs(){
    	//같은 거리일 때 우선순위로 정렬되도록 PriorityQueue 정의
        PriorityQueue<position> queue = new PriorityQueue<>();
        boolean[][] visited = new boolean[N][N];
        visited[curY][curX] = true;		//현재 아기 상어 위치 방문 확인
        queue.add(new position(curX,curY,0));		//아기 상어 위치 PriorityQueue 저장
        while(!queue.isEmpty()){
            position cur = queue.poll();
            int x = cur.x;
            int y = cur.y;
            int count = cur.count;
            if(box[y][x] != 0 && box[y][x] <curSize){	//먹을 수 있는 물고기 접근시
                box[y][x] = 0;	//물고기를 먹었기 때문에 공간을 0으로 변경
                //아기 상어 위치 변경
                curX = x;	
                curY = y;
                eatingCount++;		//먹은 횟수 증가
                return count;		//소요 시간 반환
            }
            //인접한 공간 탐색
            for(int i=0;i<4;i++){
                int tempX = x + dx[i];
                int tempY = y + dy[i];
                if(tempX>=0 && tempY>=0 && tempX<N && tempY<N && !visited[tempY][tempX]){
                    if(box[tempY][tempX]<=curSize){		//이동할 수 있는 공간일 때
                        visited[tempY][tempX] = true;
                        queue.add(new position(tempX, tempY, count+1));
                    }
                }
            }
        }
        return -1;		//먹을 수 있는 물고기 없을 때 -1 반환
    }
}