[Algorithm] SW 기출문제 - 아기 상어(16236) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 

이번 포스팅은 백준 SW 기출문제 - 아기 상어 자바 풀이를 진행하도록 하겠습니다.

해당 문제는 메모리 초과가 여러 번 발생하여, 여러 시도 끝에 해결할 수 있었던 문제입니다.

 

문제 출처: https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        
        BabyShark shark = new BabyShark(n);
        
        for (int row = 0; row < n; row++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int col = 0; col < n; col++)
                shark.setMap(row, col, parseInt(st.nextToken()));
        }
        
        shark.eat();
        System.out.println(shark.getTime());
    }
}

class BabyShark {
    
    static final int[] DR = {-1, 0, 0, 1};
    static final int[] DC = {0, -1, 1, 0};
    
    int n;
    int[][] map;
    int visitedCount;
    int[][] visited;
    int time;
    Shark shark;
    
    BabyShark(int n) {
        this.n = n;
        map = new int[n][n]; // n by n;
        visited = new int[n][n]; // 방문 여부를 int type으로 처리 참조 #1
    }
    
    void setMap(int row, int col, int value) {      
        if (value == 9) shark = new Shark(row, col, 2, 0);
        else if (value != 0) {
            map[row][col] = value;
        }
    }
    
    void eat() {

        while (true) {
            Queue<Point> queue = new ArrayDeque<>(); // queue는 point를 입력하여 가장 가까운 거리를 찾기 위한 용도
            queue.add(new Point(shark.row, shark.col, 0)); // 현재 위치한 상어 위치 설정
            Point fish = null; // 물고기 위치 초기화

            int minTime = Integer.MAX_VALUE; // 최소 시간 최대치로 초기화
            visitedCount++; // 방문한 개수 ++
            visited[shark.row][shark.col] = visitedCount; // 방문처리 (매번 boolean[][]을 생성하거나 false로 초기화 하는 것을 방지 )

            while(!queue.isEmpty()) {
                Point point = queue.poll();

                int row = point.row; 
                int col = point.col;

                if (minTime < point.time) break; // 만약 최소 시간보다 큰 순간부터는 큐의 성질에 의해 time은 현재 타임과 같거나 크게 됨 따라서 종료
                
                if (map[row][col] != 0 && map[row][col] < shark.level) { // 0이 아니면서 상어가 먹을 수 있는 물고기 존재
                    if (fish == null) { // fish에 값이 없다면
                        fish = point;
                        minTime = Math.abs(fish.row - shark.row) + Math.abs(fish.col - shark.col);
                    } else { // fish에 값이 있다면 업데이트 가능 여부 판단
                      if (fish.row > point.row || fish.row == point.row && fish.col > point.col) { // 더 행이 높은 곳에 있거나 (row가 더 작은 것 ), 두 행의 높이가 같다면 더 왼쪽에 가까운  것(col이 더 작은 것)
                          fish = point;
                      }
                    }
                }

                for (int k = 0; k < 4; k++) {
                    int nextR = row + DR[k];
                    int nextC = col + DC[k];

                    if (!isValid(nextR, nextC)) continue; // 유효한 인덱스 X, 물고기가 더 클 때,  visitedCount 같다면 continue
                    queue.add(new Point(nextR, nextC, point.time + 1));
                    visited[nextR][nextC] = visitedCount; // 방문 여부를 visitedCount로 설정함으로써, 방문 여부를 체크하는 것
                }
            }
            
            if (fish == null) break; // 만약 더 이상 물고기가 없다면 종료

            time += fish.time; // 물고기 찾는데 걸린 시간 추가하기
            shark.eatenCnt++; // 상어가 먹은 개수 업데이트
            map[fish.row][fish.col] = 0; // 먹은 물고기 없애기

            shark.row = fish.row; // 물고기 위치로 상어 업데이트
            shark.col = fish.col;
            
            if (shark.eatenCnt == shark.level) { // 만약 먹은 개수와 상어 레벨이 같다면
                shark.level++; // 상어 레벨 업데이트
                shark.eatenCnt = 0; // 먹은 개수 0 초기화
            }
        }

    }
    
    // 유효한 범위 && 물고기가 상어보다 작고 방문 안한 경우 (인트 값이 다른 경우)
    boolean isValid(int row, int col) {
        return row >= 0 && row < n && col >= 0 && col < n
            && map[row][col] <= shark.level && visited[row][col] != visitedCount;
    }
    
    int getTime() {
        return time;
    }
    
    static class Shark {
        int row;
        int col;
        int level;
        int eatenCnt;
        
        Shark (int row, int col, int level, int eatenCnt) {
            this.row = row;
            this.col = col;
            this.level = level;
            this.eatenCnt = eatenCnt;
        }
    }
    
    static class Point {
        int row;
        int col;
        int time;

        Point(int row, int col, int time) {
            this.row = row;
            this.col = col;
            this.time = time;
        }
    }
}

 

2. 풀이 중점 사항 

 

시간 복잡도 측면에서, n은 최대 20입니다.

n by n 행렬이므로 20 ^ 2 입니다.

 

BFS의 시간 복잡도는 O(v + e) (v 정점, e 간선)의 개수이므로n^2 + 4(상하좌우) * n^2 (정점의 개수) -> O(n^2)이 처리되게 됩니다.

 

일반적인 BFS에, 물고기가 있는 위치에 가서 물고기를 먹고 다시 물고기를 탐색해야하므로, 물고기의 개수  n*n개를 추가로 곱하면  O(n^4) 입니다. n = 20이므로 16만입니다.

 

약 1초당 1억번 연산이 가능하다고 하므로, 안정적으로 시간 복잡도는 통과할 수 있었습니다.

 

참고 #1

 

처음에 저는 방문 여부를 true로 표시하고, queue가 종료되어 다시 while 루프를 돌아야 할 때,
visited를 false로 초기화하는 코드를 작성하였습니다.

하지만, 그 결과 계속 메모리 초과가 발생하여, int형으로 수정한 후 방문 개수를 업데이트하여 boolean의 2차원 배열을 
생성하거나 혹은 초기화하는 작업을 제거할 수 있었습니다.

 

이를 통해 메모리 초과 문제를 해결할 수 있었습니다.

 

visitedCount 원리는 true와 비슷하게, 만약 현재 방문한 곳이 visitedCount값이 아니라면, 방문하지 않은 것이므로
visitedCount로 업데이트하고 큐에 넣어주는 것입니다. 이를 통해 방문 처리를 간소화할 수 있습니다.

 

참고 #2

 

테스트의 예제 입력 6에서 60이 아닌 56이 계속 나와서 디버깅을 찍고 위치가 이동하는 것을 파악하였습니다.

너무 단순하게 당연히 행이 높은 것, 가장 왼쪽인 것 부터 순회하도록 DR, DC를 작성하였기 때문에 먼저 가장 빠르게 물고기를 찾는다면 while(! queue.isEmpty())를 break 하였습니다.

 

static final int[] DR = {-1, 0, 0, 1};
static final int[] DC = {0, -1, 1, 0};

 

하지만, 이것은 엄청난 큰 실수로 다음의 반례를 생각해볼 수 있었습니다.

0 0 0 0 9 0 0 1
0 0 1 0 0 0 0 0

 

원래의 정답이라면 (0, 7)에 있는 물고기를 먼저 먹어야 하지만,

DR, DC로 순회하여 단순하게 먼저 찾는 로직을 구성하도록 작성한다면

왼쪽이 오른쪽보다 더 우선순위가 있으므로 큐는 (1, 2)의 물고기가 먼저 poll 되게 됩니다.

따라서, 오답이 되게 됩니다.

 

이 문제를 해결하기 위해서는 물고기를 찾는 minTime을 설정하고 minTime보다 크게 되는 순간은 
큐 성질에 의해 time보다 큰 성질을 유지하게 되므로, 종료 시킵니다.

 

만약 같은 경우에는 행이 더 높은지 (row가 0에 가까운지) , 만약 동일하다면 왼쪽에 있는지(col이 0에 가까운지)를 판단하여 문제를 해결해야 했습니다.

 

한 순간에 착각이 큰 문제가 될 수 있었습니다.

 

이상으로 아기 상어 자바 풀이를 마치겠습니다. 감사합니다.!!!