백준 : 16236 JAVA

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

부루드포스 + 최단거리(BFS)문제

 

N*N이라는 제한된 공간에 아기상어가 먹을 수 있는 물고기가 없을 때까지 몇칸을 이동하는지 문제이다.

 

조건은 항상 최단거리에 있는 상어를 먹으로가면 나보다 큰 물고기는 지나갈 수 없다. 

 

크기가 같은 물고기는 먹을수 없지만 지나갈수 있다.

 

따라서 반복문의 탈출조건은 map상 물고기가 0이거나 BFS탐색시 q에담은 데이터들이 널이되서 while문을 종료하는 시점이다.

 

BFS문제를 풀때 가끔식 q.push()를 하고 q.pop을 받고 pop받고나서 boolean 값을 마킹하는 경우가 있는데 이런경우

 

BFS에서는 많은 중복된 값을 가지게 되므로 시간초과가 나기싶다.

 

조건에만 충실하면 정답은 나온다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class B16236 {
    static int N;
    static int[][] map;
    static int fishNum;
    static int curSize;
    static int eatNum;
    static int[] Shark;
    static int endTime;
    static int[] dy = {-1,0,1,0};
    static int[] dx = {0,-1,0,1};
    public static class Pair{
        int y;
        int x;
        int cnt=0;
        Pair(int y,int x,int cnt){
            this.y = y;
            this.x = x;
            this.cnt = cnt;
        }
    }
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        map = new int[N][N];
        
        curSize = 2;
        eatNum = 0;
        fishNum = 0;
        endTime = 0;
        Shark = new int[2];
        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) {
                    Shark[0] = i;
                    Shark[1] = j;
                    map[i][j] = 0;
                }else if(map[i][j]!=0) {
                    fishNum++;
                }
            }
        }
        
        //상어이동
        
        while(fishNum!=0) {
            //BFS로 다음 탐색할 위치를 찾는다.
            //size가 큰녀석은 지나갈수없다.
            //size같은 녀석은 먹을수가 없다.
            //탐색은 위쪽 왼쪽 순으로하면 제일먼저먹어야할 위치를 찾을수가 있다.
            int sumCnt = BFS(Shark);
            if(sumCnt ==-1) break;
            endTime += sumCnt;
            eatNum++;
            fishNum--;
            map[Shark[0]][Shark[1]] = 0;
            if(eatNum == curSize) {
                eatNum = 0;
                curSize++;
            }
            
        }
    
        System.out.println(endTime);
    }
    
    public static int BFS(int[] location) {
        int cnt= 0;
        int y = location[0];
        int x = location[1];
        boolean check[][] = new boolean[N][N];
        
        Queue<Pair> q = new LinkedList<>();
        
        q.add(new Pair(y,x,0));
        check[y][x] = true;
        while(!q.isEmpty()) {
            Pair cur = q.poll();
            if(map[cur.y][cur.x] != 0 && map[cur.y][cur.x] < curSize) {
                Pair tmp;
                location[0] = cur.y;
                location[1] = cur.x;
                
                while(!q.isEmpty()) {
                    tmp = q.poll();
                    
                    if(tmp.cnt > cur.cnt) {
                        return cur.cnt;
                    }
                    
                    if(map[tmp.y][tmp.x] == 0|| map[tmp.y][tmp.x] >=curSize)continue;
                    
                    if(location[0] > tmp.y) {
                        location[0] = tmp.y;
                        location[1] = tmp.x;
                    }else if(location[0] == tmp.y) {
                        if(location[1]>tmp.x) {
                            location[1] = tmp.x;
                        }
                    }
                }
 
                return cur.cnt;
            }
            
            
            
            //네방향 탐색
            for(int d=0;d<4;d++) {
                int ny = cur.y +dy[d];
                int nx = cur.x +dx[d];
                if(ny<0||nx<0||ny>=N||nx>=N) continue;
                if(map[ny][nx] > curSize) continue;
                if(check[ny][nx] == true) continue;
                //push 하기전에 마킹을하고 BFS에 넣는다.
                //이렇게 pop한다음에 하면 중복된 case가 많아서 당연히 타임 오버가 발생.
                check[ny][nx] = true;
                q.add(new Pair(ny,nx,cur.cnt+1));
            }
            
        }
        
        //먹지못햇을 경우.
        return -1;
    }
}