백준 16236(JAVA)

문제

풀이

단순 bfs만으로 상하좌우 방문의 순서를 정해준다해서 같은 거리에 가장위쪽, 가장왼쪽의 먹이를 먹는다는 보장이 없다. 이 아이디어를 떠올리지못해 단순 bfs탐색 순서만으로 (위 -> 왼쪽 -> 오른쪽 -> 아래) 고집하여 풀다보니 문제를 푸는데 삼일을 소요했다.

왜 안될까?

직관적으로는 될거같지만, 현재 같은거리의 먹이를 기준으로 하지 않고 nextX, nextY의 위치를 기준으로 위 왼쪽 오른쪽 아래를 탐색하므로 잘못되었다.
현재 current 위치를 기준으로 먹을수있는 먹이중 가장 가까우면서 가장 위에있고 가장 왼쪽에있는 한먹이를 골라야한다.

그렇게 하기 위해선 일단 현재 위치에서 Queue를 이용해 그래프를 탐색하며(BFS) 먹을수있는 먹이를 모두 List에 넣는다.
그다음 List에서 Comparator을 이용해 정렬을 한다.(정렬기준은 짧은거리 -> 가장 위쪽 -> 가장 왼쪽순으로 정렬)
정렬된 List의 가장앞에 있는 먹이를 아기상어는 먹을수 있다.
해당 위치를 기준으로 다시 반복해서 작업..

이렇게 하면 풀수있다.

BFS를 통해 그래프를 탐색하되, 현재 위치에서 먹을수 있는 먹이를 모두 저장해두었다가 조건에 맞는 먹이를 정렬을 통해 얻고 다시 그 위치에서 먹이를 탐색해나가면 된다.

풀고나니 어렵지않지만 조건도많고, 하나 실수해서 조건을 빼먹으면 꽤 오래 디버깅을 해야하는 문제이다.
구현 문제답게 문제도 장황하고 조건도 많다.

코드

package baekjoon.그래프탐색;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main16236 {
    static int N;
    static int[][] board;
    static int startX, startY;
    static boolean[][] visited;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static List<BabyShark> feedList = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        board = new int[N][N];
        visited = new boolean[N][N];

        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < N; j++){
                int value = Integer.parseInt(st.nextToken());
                if(value == 9){
                    startX = i;
                    startY = j;
                }else{
                    board[i][j] = value;
                }
            }
        }


        System.out.println(bfs(startX, startY));
    }
    static int bfs(int x, int y){
        int babySharkSize = 2;
        int eatCount = 0;
        Queue<BabyShark> q = new LinkedList<>();
        visited[x][y] = true;
        q.offer(new BabyShark(x, y, 0));
        int totalTimes = 0;

        while(true){
            while(!q.isEmpty()){
                BabyShark current = q.poll();
                for(int i = 0; i < 4; i++){
                    int nextX = current.x + dx[i];
                    int nextY = current.y + dy[i];

                    if(nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) continue;
                    if(!visited[nextX][nextY] && (board[nextX][nextY] == 0 || board[nextX][nextY] == babySharkSize)){
                        q.offer(new BabyShark(nextX, nextY, current.times + 1));
                        visited[nextX][nextY] = true;
                        continue;
                    }
                    if(!visited[nextX][nextY] && board[nextX][nextY] != 0 && board[nextX][nextY] < babySharkSize){
                        //can eat
                        feedList.add(new BabyShark(nextX, nextY, current.times + 1));
                        q.offer(new BabyShark(nextX, nextY, current.times + 1));
                        visited[nextX][nextY] = true;
                        continue;
                    }
                }
            }
            if(!feedList.isEmpty()){
                Collections.sort(feedList, (o1, o2) -> {
                    if(o1.times == o2.times){
                        if(o1.x == o2.x){
                            return o1.y - o2.y;
                        }else{
                            return o1.x - o2.x;
                        }
                    }else{
                        return o1.times - o2.times;
                    }
                });
                //먹을수있는 먹이중 가장 가까우면서 위쪽 그리고 왼쪽에있는 먹이 찾기
                BabyShark feed = feedList.get(0); //먹을 먹이

                eatCount++;
                if(eatCount == babySharkSize){
                    babySharkSize++;
                    eatCount = 0;
                }
                totalTimes += feed.times;

                feedList.clear(); //먹이 리스트 비워주기
                visited = new boolean[N][N]; // 방문 처리 초기화
                visited[feed.x][feed.y] = true; //(처음 탐색 시작지점)
                board[feed.x][feed.y] = 0; // 먹었으니 0으로 바꾸어줌
                q.offer(new BabyShark(feed.x, feed.y, 0));
            }else{
                break;
            }
        }
        return totalTimes;
    }
}

class BabyShark{
    int x;
    int y;
    int times;

    public BabyShark(int x, int y, int times) {
        this.x = x;
        this.y = y;
        this.times = times;
    }

    @Override
    public String toString() {
        return "BabyShark{" +
                "x=" + x +
                ", y=" + y +
                ", times=" + times +
                '}';
    }
}