[백준] 16236. 아기상어

<서론>

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

16236번: 아기 상어

예전에 풀었던 문제! 링크는 위에.. 코드는 결론에.

처음에는 막막하기만 했었는데, 조금 하다보니 감이 왔다. 물론 감이 오고 나서도 시간이 오래 걸렸다. 음, 풀고 나니 별거 아닌 문제였지만 풀 당시에는 너무 어려웠던 문제. 문제 풀었던 기억이 더 희미해지기 전에 빠르게 포스팅 해본다.

---

 

 

<본론>

이 문제를 풀 때, DFS나 재귀는 괜찮았지만 BFS로는 문제를 거의 풀어보지 못했다. 최단 경로 문제는 BFS로 풀어야한다고 어디서 주워들은 건 있어서 이 문제를 BFS로 풀려고 했다. BFS에 대한 감이 별로 없던 상태에서 무턱대고 BFS로 풀려 했으니, 삽질을 꽤 많이 했다.

그래도 이 문제 덕분에 나름 BFS로 문제를 푸는 감도 익힌 것 같다.

 

탐색했을 때 그 먹이까지의 거리가(여기서는 시간이) depth이기때문에 가지고 거리를 판단했다.

거리가 같을 때 우선순위는 더 위에 있거나 y축 값도 같다면 왼쪽에 있는 걸 먹도록 분기처리도 하였다.

탐색은 현재 위치를 기준으로 상하좌우 4방향을 탐색했고,

 

1. 해당 방향의 위치가 탐색한 곳이 아닌 경우

2. 자기 자신(상어)보다 숫자가 작거나 같은 수인 경우

 

위 두가지 경우에만 탐색을 진행했다.

 

위 두가지에 해당하는 곳은 visited 배열에서 true 값으로 바꿔주었고

먹이인 경우(0이 아니면서 자기보다 작은 경우)와 길인 경우(자기 자신과 숫자가 같은 경우)로 나누었다.

먹이인 경우에는 food 객체에 값을 넣었고, 길인 경우에는 que에 해당 좌표를 넣었다.

 

탐색이 다 끝나면 먹이를 향해 이동했고(먹이가 없는 경우에는 프로그램 종료), 먹이를 먹고 성장할지 안할지도 판단했다.

 

이제와서 보니 비효율적으로 짜여진 곳이 많은데, 저 문제를 풀 당시에는 문제를 푸는 것만으로도 너무 버거워서 일단 답을 뱉어내는 코드를 만들었다.

그래도 이 문제 덕분에 BFS 풀이에 대해 조금 알 수 있게 된 것 같다.

---

 

 

<결론>

요약

1. 먹이 or 탐색위치를 담을 Class 생성.(필드로는 x,y 좌표, 거리)

2. 탐색 조건(자신보다 작은 수, 방문하지 않았던 곳)에 맞는 곳을 BFS로 탐색

3. 먹이를 발견했을 경우, que에 넣지 않고 따로 food 객체에만 저장

4. 같은 depth에서 다른 먹이 발견 시, 우선 순위(1. y값이 더 아래, 2.x값이 더 아래)에 맞게 food 저장값 변경

5. 먹이로 이동 후 성장할 지 확인.

6. 더이상 이동할 수 없을때까지 반복.

import java.util.ArrayList;
import java.util.Scanner;
 
public class SS_16236 {
    
    static boolean[][] visited;
    static boolean finished = false;    // 더 이상 남은 먹이가 없을때..
    static int N;
    static int ans = 0;
    static int size = 2;                // 생선 크기
    static int count = 2;                // 먹어야 하는 회수
    
    static int[] dx = {0,-1,0,1};
    static int[] dy = {1,0,-1,0};
 
    public static void main(String[] args) {
        
        /*
         * 다시 작성하는 플랜
         * 무조건 bfs로 푼다.
         * 같은 dept면 길이도 같다
         * 방문한 곳은 true 처리해서 재방문 방지
         * 전체 스캔할 필요 없이 뎁스 내에서 같으면 된다
         * 최소 뎁스에서 위 또는 좌측 값을 넣자.. 그것이 최소값!
         * 
         * 먹고 바로 사이즈 확인
         * 현재 위치에서 다시 시작
         */
        
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        int iniX=0, iniY=0;
        visited = new boolean[N+2][N+2];
        int[][] map = new int[N+2][N+2];
        for(int i=0; i<N+2; i++) {
            for(int j=0; j<N+2; j++) {
                if(i==0||j==0||i==N+1||j==N+1) {
                    map[i][j]=9999;
                } else {
                    map[i][j] = sc.nextInt();
                    if(map[i][j]==9) {
                        iniX = j;
                        iniY = i;
                        visited[i][j] = true;
                    }
                }
            }
        }
        
        ArrayList<Cord> que = new ArrayList<>();
        Cord c = new Cord(iniX, iniY, 0);
        que.add(c);
        while(!finished) {
            Cord food = new Cord(1000,1000,1000);
            while(!que.isEmpty()) {
                Cord cd = que.get(0);
                que.remove(0);                    // 큐 하나 빼기
                int nowX = cd.getX();
                int nowY = cd.getY();
                int dept = cd.getDept();
                for(int i=0; i<4; i++) {
                    move(nowX, nowY, map, i, que, dept+1, food);
                    // depth는 하나 더해서
                }
            }
            if(food.getDept()!=1000) {
                // food 초기값에서 변동이 없으면.. 즉 먹이가 없었을 경우
                eating();
                ans += food.getDept();
                que.clear();
                que.add(new Cord(food.getX(), food.getY(), 0));    // que empty 방지
                map[iniY][iniX] = 0;                            // 상어 이동 전 위치를 0으로
                iniX = food.getX();
                iniY = food.getY();
                map[food.getY()][food.getX()] = 9;                // 상어 이동 후 위치를 9로
                visited[iniY][iniX] = true;                        // 이동한 위치 방문처리
            } else finished = true;                                // 먹이가 없었을 경우 프로그램 종료를 위해..
        }
        
        System.out.println(ans);
        
        sc.close();
    }
    
    static void move(int x, int y, int[][] map, int dir, ArrayList<Cord> que, int dept, Cord food) {
        if(map[y+dy[dir]][x+dx[dir]]<=size && !visited[y+dy[dir]][x+dx[dir]]) {
            // 작거나 같고(이동 통로), 방문 안한 곳
            visited[y+dy[dir]][x+dx[dir]] = true;
            if(map[y+dy[dir]][x+dx[dir]]<size && map[y+dy[dir]][x+dx[dir]]!=0 && food.getDept()>=dept) {
                // 작은 경우(먹이), 0이 아닌 곳, dept가 작은 곳.
                if((food.getY()>y+dy[dir]) || (food.getY()==y+dy[dir]&&food.getX()>x+dx[dir])) {
                    // 먹이가 위에 있으면 or 같은 y 값일때 왼쪽에 있으면 먹이 교체
                    food.setX(x+dx[dir]);
                    food.setY(y+dy[dir]);
                    food.setDept(dept);
                }
            } else {
                Cord cord = new Cord(x+dx[dir], y+dy[dir], dept);
                que.add(cord);
            }
        }
    }
    
    static void eating() {        // 먹고 성장할지 판단
        if(--count==0) {
            size++;
            count = size;
        }
        visited = new boolean[N+2][N+2];    // 방문기록 초기화
    }
    
    static void show(int[][] map) {        // 이동과정 보는 메소드
        System.out.println();
        System.out.println("===============================================");
        for(int i=1; i<N+1; i++) {
            for(int j=1; j<N+1; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println("===============================================");
    }
}
 
class Cord{                // 먹이 위치때문에 클래스 만듦
    int x;
    int y;
    int dept;            // depth 가 사실 상 거리
    
    public Cord() {}
    
    public Cord(int x, int y, int dept) {
        this.x = x;
        this.y = y;
        this.dept = dept;
    }
    
    public Cord(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    public int getX() {
        return x;
    }
    public void setX(int x) {
        this.x = x;
    }
    public int getY() {
        return y;
    }
    public void setY(int y) {
        this.y = y;
    }
    public int getDept() {
        return dept;
    }
    public void setDept(int dept) {
        this.dept = dept;
    }
}