난이도

Gold 3

풀이 참고 유무

x

막힌 부분

x

문제

문제 바로가기

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.
둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

• 0: 빈 칸
• 21, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

예제 입력

6
6 0 6 0 6 1
0 0 0 0 0 2
2 3 4 5 6 6
0 0 0 0 0 2
0 2 0 0 0 0
3 9 3 0 0 1

예제 출력

48

문제 검토

이동 시 1초가 걸리고 초를 구한다는 점에서 BFS를 사용하는 것이 맞다.
구현이 어려워 보이므로 구현 유형으로 봐야할 것 같다.

풀이(python)

Java

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

public class Main{
    static int[][] matrix,distance;
    static ArrayDeque<int[]> q;
    static int x,y;
    static int n;
    static int shark=2;
    static int sharkSto=0;
    static int answer=0;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n=Integer.valueOf(br.readLine());
        StringTokenizer st;
        matrix= new int[n][n];
        distance=new int[n][n];

        for(int i=0; i<n; i++){
            st=new StringTokenizer(br.readLine()," ");
            for(int j=0; j<n; j++){
                matrix[i][j]=Integer.valueOf(st.nextToken());
                if(matrix[i][j]==9){
                    x=i;
                    y=j;
                    matrix[i][j]=-1;
                }
            }
        }
        while(true){
            //distance 초기화
            distance=new int[n][n];
            //아기 상어의 좌표 구하기
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(matrix[i][j]==-1){
                        x=i;
                        y=j;
                    }
                }
            }
            //아기 상어 기준으로 거리 구하기
            bfs();

            ArrayList<int[]> canEatFish=new ArrayList<>();
            ArrayList<int[]> minDisFish=new ArrayList<>();
            //먹을 수 있는 물고기 구하기
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                //상어보다 작고, 상어가 아니고, 비어있는 공간도 아니고, 갈 수 없는 곳도 아니고, 출발 지점도 아닌
                    if(matrix[i][j]<shark && matrix[i][j] != -1 && matrix[i][j]!=0 && distance[i][j]!=0 && distance[i][j]!=1){
                        canEatFish.add(new int[]{i,j});
                    }
                }
            }
            //만약 먹을 수 있는 물고기가 없다면
            if(canEatFish.isEmpty()){
                break;
            }
            int[] targetFish=new int[2];
            int minDistance=99999;
            int minRow=99999;
            int minCol=99999;

            ArrayList<int[]> canEatFishFirst=new ArrayList<>();
            ArrayList<int[]> canEatFishSecond=new ArrayList<>();
            //그 중 현재 가장 적합한 물고기 구하기
            //가장 가까운 거리의 물고기 구하기
            if(canEatFish.size()>1){
                //가까운 거리 구하고
                for(int[] curr:canEatFish){
                    if(distance[curr[0]][curr[1]]<=minDistance){
                        minDistance=distance[curr[0]][curr[1]];
                    }
                }
                //해당하는 물고기 add
                for(int[] curr:canEatFish){
                    if(distance[curr[0]][curr[1]]==minDistance){
                        canEatFishFirst.add(new int[]{curr[0],curr[1]});
                    }
                }
            }else{
                targetFish=canEatFish.get(0);
            }
            //그 중 가장 위쪽
            if(canEatFishFirst.size()>1){
                for(int[] curr:canEatFishFirst){
                    if(curr[0]<=minRow){
                        minRow=curr[0];
                    }
                }
                for(int[] curr:canEatFishFirst){
                    if(curr[0]==minRow){
                        canEatFishSecond.add(new int[]{curr[0],curr[1]});
                    }
                }
            }else{
                if(!canEatFishFirst.isEmpty()){
                    targetFish=canEatFishFirst.get(0);
                }
            }
            //그게 여러개라면 그 중 가장 왼쪽
            if(canEatFishSecond.size()>1){
                for(int[] curr:canEatFishSecond){
                    if(curr[1]<minCol){
                        minCol=curr[1];
                        targetFish=new int[]{curr[0],curr[1]};
                    }
                }

            }
            else{
                if(!canEatFishSecond.isEmpty()){
                    targetFish=canEatFishSecond.get(0);
                }

            }
            answer+=distance[targetFish[0]][targetFish[1]]-1;
            matrix[x][y]=0;
            matrix[targetFish[0]][targetFish[1]]=-1;
            //shark크기 1 증가
            sharkSto++;
            if(sharkSto==shark){
                shark++;
                sharkSto=0;
            }

        }
        System.out.println(answer);
     }
    public static void bfs(){
        q=new ArrayDeque<>();
        q.add(new int[]{x,y});
        int[] dx={-1,1,0,0};
        int[] dy={0,0,-1,1};
        distance[x][y]=1;
        while(!q.isEmpty()){
            int[] cur=q.pollFirst();
            int cx=cur[0];
            int cy=cur[1];
            for(int i=0; i<4; i++){
                int nx=cx+dx[i];
                int ny=cy+dy[i];
                if(nx<0 || nx>=n || ny<0 || ny>=n ){
                    continue;
                }
                if(distance[nx][ny]!=0){
                    continue;
                }
                //shark보다 크면 갈 수 없다.
                if(matrix[nx][ny]>shark){
                    continue;
                }
                distance[nx][ny]=distance[cx][cy]+1;
                q.add(new int[]{nx,ny});
            }
        }
    }
}

아이디어:

//1. 먼저 아기 상어를 기준으로 bfs를 돌려서 distance[][]에 거리들을 저장해놓은다.
//2. n이 작으므로 distance와 matrix를 완탐하여 먹기 가장 알맞은 물고기를 고른다.
//3. 그 물고기 자리에 아기 상어를 위치하게 하고 아기 상어의 뱃속을 +1 해준다.(아기 상어의 뱃속이 상어의 크기와 같다면 상어 +1)
//4. 이후 distance를 초기화한 후 다시 1번 과정으로 돌아가서 이 과정을 반복한다.
//5. 먹을 물고기가 없다면 종료

시간복잡도

//n=20이라 bfs 문제 없고 완탐을 돌려도 문제 없다.

걸린 시간

1:14:25

총평

아이디어를 생각하는건 쉬웠지만, 조건이 많아서 구현하기가 까다로웠다.
구현 하는데 40분 정도 소요되었는데 오타와 문제를 잘못 이해하는 바람에 시간이 더 오래걸렸다.
구현이 까다로울 때는 중간 중간 꼭 디버깅하고 문제를 확실하게 꼼꼼히 이해하도록 하자.

또한 다른 사람의 풀이를 보니 bfs를 따로 호출하지 않고 bfs 과정을 진행하면서 아기 상어를 큐에 위치하게 하고 한번에 진행할 수 있고 최소 행과 열을 구하는 과정을 조금 더 지혜롭게 한 for문 안에서 진행하여 코드의 길이를 줄일 수 있더라.