백준 16236 (아기상어) JAVA

문제

16236번: 아기 상어

N * N 크기의 공간에서 아기 상어가 먹이를 먹지 못할 때 까지 최소 시간을 구하는 문제이다.

아기 상어는 상하좌우 움직일 수 있고 한 칸 움직일 때 마다 1초가 지난다.

아기 상어는 항상 가장 가까운 먹이를 먹는다.

아기 상어의 크기는 처음에 2이고 먹이는 자신의 크기보다 작거나 0보다 클 경우 먹을 수 있다.

자신의 크기와 같은 먹이는 먹지는 못하고 이동만 가능하다. 반면에 자신의 크기보다 큰 먹이가 있는 곳은 지나갈 수 없다.

만약 먹을 수 있는 먹이가 같은 거리에 여러 마리가 있다면 위에 있는 먹이를 먼저 먹고, 그 다음에 왼쪽 순으로 먹는다.

아기 상어의 크기 만큼 먹이를 먹으면 크기가 1씩 커진다. 예를 들어 아기상어의 크기가 3이면 먹이를 3번 먹어야 4가 된다.

 

예를 들어 N =4이고 다음과 같이 공간이 주어진다면

4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4

9가 아기상어의 현재 위치이다. 아기상어의 크기는 현재 2이다.

먹을 수 있는 먹이는 1시 방향의 1과 7시방향의 1이 있다. 같은 거리 일경우 위쪽 먹이를 먼저 먹으므로 3만큼 움직여 1시 방향의 1을 먹는다.

그다음 1시방향의 위치 부터 7시방향의 위치의 1로 이동을 해서 1을 먹는다. 6번 이동한다.

아기상어는 총 2개의 먹이를 먹음으로 써 크기가 3으로 늘어났다.

7시방향 부터 시작해서 바로 오른쪽에 있는 2를 먹을 수 있다. 1번 이동한다.

또 해당위치에서 맨위에 있는 2로 이동이 가능하다. 총 4번이동한다.

나머지 먹이들은 3, 4 뿐이므로 먹이를 먹을 수 없다.

따라서 아기상어는 총 14번 이동했다.

---

처음에는 단순히 BFS를 돌며 진행하려 했지만, 상어의 크기라던지 먹이를 얼마나 먹었는지 체크해줄 때 BFS의 동시성 문제에서 걸렸다.

BFS는 처음위치에서 동시에 4방향으로 펴져나가기 때문에 한번에 이를 처리하기에는 무리가 있었다.

 

결국!!

로직부터 말하자면 처음 상어의 위치에서 BFS를 실행해 가장 가까운 먹이를 먹을 수 있는지 없는지 확인한다.

먹을 수 있으면 먹고 먹은 위치 부터 다시 BFS를 실행한다. 이렇게 해서 먹이를 먹을 수 없을 때 까지 BFS를 실행한다.

static boolean[][] visit; //방문 배열 체크
static int [][]map; //맵
static int []dy = {-1, 0, 1, 0};
static int []dx = {0, -1, 0, 1};
static int n; 
static int level = 2; //상어의 크기
static boolean eat; //먹었는지 체크
static Tuple start; // 시작점

먼저 전역변수로 설정한 것들이다.

class Tuple{
    int r; //행
    int c; //열
    int cost; //거리
    Tuple(){}
    Tuple(int r, int c, int cost){
        this.r = r;
        this.c = c;
        this.cost = cost;
    }
}

새롭게 만든 Tuple 클래스이다. BFS를 진행하면서 위치를 저장할 클래스이다.

int exp = 0; //몇마리 먹었는지 세는 변수
int answer=0; //최종 답
        
        boolean flag = true;
        while(flag){
            //visit 배열 초기화
            visit = new boolean[n][n];
            start = bfs(start);
            if (eat) { //1마리 먹었을 경우
                eat=false;
                exp++;
                map[start.r][start.c]=0;
                answer += start.cost;
                start.cost=0;
                if(exp == level){
                    level++;
                    exp=0;
                }
            }
            else flag = false; //1마리도 못먹었을 경우
        }

start 변수에 현재 상어 위치를 넣어 bfs를 실행시킨다. 

static Tuple bfs(Tuple start){
        Queue<Tuple>q = new LinkedList<>();
        q.add(start);
        visit[start.r][start.c]=true;

        Tuple nextStart = new Tuple(); //상어가 먹이를 먹은 위치를 저장할 변수
        while(!q.isEmpty()){
            int y = q.peek().r;
            int x = q.peek().c;
            int cost = q.peek().cost;

            if(map[y][x] >0 && map[y][x]<level && cost == nextStart.cost){ // 가장 위쪽, 왼쪽 순
                if(y < nextStart.r || (y == nextStart.r && x < nextStart.c)) {
                    nextStart.r = y;
                    nextStart.c = x;
                    continue;
                }
            }
            q.poll();
            for(int i=0;i<4;i++){
                int yy = y + dy[i];
                int xx = x + dx[i];
                if(yy<0 || xx<0 ||yy>=n || xx>=n) continue; //맵을 벗어나는 경우
                if(map[yy][xx]>level)continue; //먹이를 먹을 수 없을 경우
                if(visit[yy][xx])continue; //이미 방문한 경우


                if(map[yy][xx]>0 && map[yy][xx]<level  && eat==false){ //먹을 수 있는 경우
                    eat = true;
                    nextStart.r = yy;
                    nextStart.c = xx;
                    nextStart.cost = cost+1;
                }
                else{ //이동만 가능한 경우
                    q.add(new Tuple(yy, xx, cost+1));
                    visit[yy][xx]=true;
                }
//                if(map[yy][xx] == level || map[yy][xx]==0){ //이동만 가능할 때
//                    q.add(new Tuple(yy, xx, cost+1));
//                    visit[yy][xx]=true;
//                }
//                else if(map[yy][xx] < level && eat==false){ //물고기 먹을 수 있을 때
//                    eat = true;
//                    nextStart.r = yy;
//                    nextStart.c = xx;
//                    nextStart.cost = cost+1;
//                }
            }
        }
        return nextStart;
    }

위 BFS를 실행해 먹이를 먹을 수 있는 경우 eat변수를 true로 바꿔준다.

주석 처리한 곳은 내가 처음에 조건을 걸어준 것이다 (틀린 코드) 왜 틀렸는지 생각해 볼것

---

전체 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;

public class 연습용 {
    static boolean[][] visit;
    static int [][]map;
    static int []dy = {-1, 0, 1, 0};
    static int []dx = {0, -1, 0, 1};
    static int n;
    static int level = 2;
    static boolean eat; //먹었는지 체크
    static Tuple start; // 시작점
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        map = new int[n][n];

        start = new Tuple(); //상어 시작 위치 저장

        for(int i=0;i<n;i++){ //맵 입력
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<n;j++){
                map[i][j]=Integer.parseInt(st.nextToken());
                if(map[i][j] == 9){ //상어 위치 저장
                    start.r = i;
                    start.c = j;
                    start.cost = 0;
                    map[i][j] = 0;
                }
            }
        }
        int exp = 0; //몇마리 먹었는지 세는 변수

        int answer=0;
        boolean flag = true;
        while(flag){
            //visit 배열 초기화
            visit = new boolean[n][n];
            start = bfs(start);
            if (eat) { //1마리 먹었을 경우
                eat=false;
                exp++;
                map[start.r][start.c]=0;
                answer += start.cost;
                start.cost=0;
                if(exp == level){
                    level++;
                    exp=0;
                }
            }
            else flag = false; //1마리도 못먹었을 경우
        }

        System.out.println(answer);
    }
    static Tuple bfs(Tuple start){
        Queue<Tuple>q = new LinkedList<>();
        q.add(start);
        visit[start.r][start.c]=true;

        Tuple nextStart = new Tuple();
        while(!q.isEmpty()){
            int y = q.peek().r;
            int x = q.peek().c;
            int cost = q.peek().cost;

            if(map[y][x] >0 && map[y][x]<level && cost == nextStart.cost){ // 가장 위쪽, 왼쪽 순
                if(y < nextStart.r || (y == nextStart.r && x < nextStart.c)) {
                    nextStart.r = y;
                    nextStart.c = x;
                    continue;
                }
            }
            q.poll();
            for(int i=0;i<4;i++){
                int yy = y + dy[i];
                int xx = x + dx[i];
                if(yy<0 || xx<0 ||yy>=n || xx>=n) continue; //맵을 벗어나는 경우
                if(map[yy][xx]>level)continue; //먹이를 먹을 수 없을 경우
                if(visit[yy][xx])continue; //이미 방문한 경우


                if(map[yy][xx]>0 && map[yy][xx]<level  && eat==false){ //먹을 수 있는 경우
                    eat = true;
                    nextStart.r = yy;
                    nextStart.c = xx;
                    nextStart.cost = cost+1;
                }
                else{ //이동만 가능한 경우
                    q.add(new Tuple(yy, xx, cost+1));
                    visit[yy][xx]=true;
                }
//                if(map[yy][xx] == level || map[yy][xx]==0){ //이동만 가능할 때
//                    q.add(new Tuple(yy, xx, cost+1));
//                    visit[yy][xx]=true;
//                }
//                else if(map[yy][xx] < level && eat==false){ //물고기 먹을 수 있을 때
//                    eat = true;
//                    nextStart.r = yy;
//                    nextStart.c = xx;
//                    nextStart.cost = cost+1;
//                }
            }
        }
        return nextStart;
    }
}
class Tuple{
    int r;
    int c;
    int cost;
    Tuple(){}
    Tuple(int r, int c, int cost){
        this.r = r;
        this.c = c;
        this.cost = cost;
    }
}