개발해요

https://programmers.co.kr/learn/courses/30/lessons/87694

처음에 어떻게 풀어야 할지 감이 안 와서 고민해보다가 다른 분들의 힌트를 봤다. 생활 패턴 고친다고 밤을 새워서 그런지(핑계 맞음ㅎㅎ) 봐도 무슨 말인지 모르겠더라. 짐 싸서 집 가는 길에 백준에서 비슷한 문제를 풀었던 기억이 갑자기 떠올랐다ㅋㅋ. 신기하게도 샤워하거나 산책하면 아이디어가 잘 떠오르는데, 이유는 뭘까?

아무튼 DFS나 BFS로 풀 수 있다는 것까진 알았는데, 이번엔 어떻게 테두리만 표시할지 떠오르지 않았다. 결국 다른 분의 풀이를 봤는데, 대단한 사고력이 필요하진 않았고 오히려 방법이 단순했다. 최근에 코테 실력이 많이 는 것 같아서 "나 이제 코테 좀 치나?ㅋㅋ" 싶었는데, 반성했다.

결론적으론 나에게 어려운 문제였다.

요약

1. 좌표 및 사각형 영역을 2배로 늘린다
2. 그래프에 모든 사각형의 테두리를 표시한다. (1 vs 0 or true vs false)
3. 사각형의 테두리를 제외한 안쪽 영역(너비)을 빈공간으로 표시한다.
4. 테두리 전체 길이(S)와 시작점에서 도착점(src- dst)까지의 길이를 각각 구한다.
5. 정답: min(S - (src - dst), src - dst)

풀이

1. DFS/BFS로 해결할 수 있다

그래프를 점과 빈공간으로 표시할 때, 테두리만을 나타낼 수 있으면 시작점에서 도착점까지 얼마나 이동했는지를 DFS/BFS로 알 수 있다.

2. 좌표를 늘린다!

테두리를 따라가려면 인접한 1을 탐색하면 된다. 하지만 테두리간 거리가 1이면 위와 같은 상황에서 테두리를 잘못 따라갈 수 있다. 따라서, 좌표를 모두 2배로 늘려서 위와 같은 문제를 예방한다.

3. 어떻게 바깥의 테두리만 표시할 수 있을까?

1. 우선 모든 사각형의 테두리를 표시한다.

2. 테두리 안쪽 영역을 빈공간으로 표시한다. 그럼 사각형에 포함되어 있던 테두리가 제거된다.

코드

class Solution {
    static final int SIZE = 101;
    static boolean[][] board = new boolean[SIZE][SIZE]; // true: 점 

    int[] dR = new int[]{-1, 1, 0, 0};
    int[] dC = new int[]{0, 0, -1, 1};

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        // 좌표 2배로 늘리기
        int srcRow = characterY * 2;
        int srcCol = characterX * 2;
        int dstRow = itemY * 2;
        int dstCol = itemX * 2;

        markRect(rectangle); // 그래프에 사각형 테두리만 표시
        
        // + 1: 마지막 위치에서 시작점으로 돌아온 거리
        int totalDistance = findDistance(srcRow, srcCol, srcRow, srcCol, new boolean[SIZE][SIZE], 0) + 1; 
        int distance = findDistance(srcRow, srcCol, dstRow, dstCol, new boolean[SIZE][SIZE], 0);

        return Math.min(distance, totalDistance - distance) / 2;
    }

    private void markRect(int[][] rectangles) {
        for (int[] rect: rectangles) {
            int firstRow = 2* rect[1];
            int firstCol = 2* rect[0];
            int secondRow = 2* rect[3];
            int secondCol = 2* rect[2];

            markEdge(firstRow, firstCol, secondRow, secondCol);
        }

        for (int[] rect: rectangles) {
            int firstRow = 2* rect[1];
            int firstCol = 2* rect[0];
            int secondRow = 2* rect[3];
            int secondCol = 2* rect[2];

            markSpace(firstRow, firstCol, secondRow, secondCol);
        }
    }

    // 그래프에 테두리 모두 표시
    private void markEdge(int firstRow, int firstCol, int secondRow, int secondCol) {
        for(int row = firstRow; row <= secondRow; row++) {
            board[row][firstCol] = true;
        }
        for(int col = firstCol + 1; col <= secondCol; col++) {
            board[secondRow][col] = true;
        }
        for(int row = secondRow - 1; row >= firstRow; row--) {
            board[row][secondCol] = true;
        }
        for (int col = secondCol - 1; col > firstCol; col--) {
            board[firstRow][col] = true;
        }
    }

    // 테두리를 제외한 사각형 너비 영역을 모두 빈공간으로 표시한다
    private void markSpace(int firstRow, int firstCol, int secondRow, int secondCol) {
        for (int row = firstRow + 1; row < secondRow; row++) {
            for (int col = firstCol + 1; col < secondCol; col++) {
                board[row][col] = false;
            }
        }
    }

    // DFS
    private int findDistance(int row, int col, final int dstRow, final int dstCol, final boolean[][] visited, int count) {
        if (count > 0 && row == dstRow && col == dstCol) {
            return count;
        }

        visited[row][col] = true;

        for (int i = 0; i < 4; i++) {
            int newRow = row + dR[i];
            int newCol = col + dC[i];

            if (newRow >= 0 && newRow < SIZE && newCol >= 0 && newCol < SIZE && board[newRow][newCol] && !visited[newRow][newCol]) {
                return findDistance(newRow, newCol, dstRow, dstCol, visited, count+1);
            }
        }

        return count;
    }
}

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

안녕하세요, 이륙사입니다.

풀이

이번 문제는 Union-Find 혹은 BFS, DFS를 사용해서 해결할 수 있는 문제였습니다. 그중에서 이번엔 BFS를 사용해서 포스팅해보려고 합니다.

먼저, 예시들을 통해 PU의 개수는 직사각형의 수와 관련이 있다는 걸 알 수 있습니다. 그리고 만약 한점 이상에서 만나는 직사각형들이 있다면 그 직사각형들은 연필을 떼지 않고 한번에 그릴 수 있습니다. 즉, 몇 번의 한붓 그리기로 모든 직사각형들을 그릴 수 있는지 묻고 있으며, 직사각형 집합의 개수를 구하는 문제로도 생각할 수 있습니다. (참고로 직사각형만 그릴 수 있기 때문에, 2, 3번 명령어는 고려하지 않아도 됩니다.)

따라서 집합의 수를 구하기 위해 Union-Find를 떠올릴 수 있으며, 겹치는 직사각형의 점들은 모두 연결되어 있기 때문에 인접한 곳을 모두 탐색하는 BFS, DFS로도 해결할 수 있게 되는 겁니다! 탐색 함수를 호출한 횟수가 집합의 개수가 됩니다. 

for (y in 0 until MAX_PLUS_ONE) {
        for (x in 0 until MAX_PLUS_ONE) {
            if (graph[y][x] == 1 && visited[y][x].not()) { // 직사각형이 있고, 아직 그룹지어지지 않았다면
                answer += 1
                bfs(x, y)
            }
        }
    }

좌표 변환

단순 그래프 탐색 문제가 되었으므로, 열심히 구현해서 정답을 제출합니다. 그리고 틀립니다. 왜냐면 아래와 같이 겹치지 않는데도 인접하는 상황이 발생하기 때문입니다.

이럴 때 좌표 값을 2배 늘려주면, 거리가 1이던 점들의 거리도 2가 돼서 문제를 해결할 수 있습니다! 또한, 좌표값은 양수이어야 하므로 먼저 +500 증가시킨 후에 좌표 값을 2배 늘려줍니다.

repeat(n) {
        val st = StringTokenizer(readLine())
        drawRect(2 * (st.nextToken().toInt() + 500), // 좌표를 오른쪽으로 이동 후 2배 증가
            2 * (st.nextToken().toInt() + 500),
            2 * (st.nextToken().toInt() + 500),
            2 * (st.nextToken().toInt() + 500)
        )
    }

디버깅을 통해서나 아니면 처음부터 이런 상황을 떠올릴 수 있으면 정말 좋겠지만, 문제 경험이 풍부하지 않고선 쉽지 않을 것 같습니다ㅋㅋ

예외 처리

정말 마지막으로, 처음에 (0, 0)에서 연필을 내린 상태로 시작한다는 점도 주의해주셔야 합니다. (0, 0)과 이어진 사각형들은 처음에 연필을 올리지 않고 그릴 수 있기 때문입니다. 

// 처음에 (1000,1000)에 연필을 내린 상태에서 시작
if (graph[1000][1000] == 1) print(answer - 1)
else print(answer)

생각 과정

1. 예시를 통해 사각형 집합의 개수를 구하는 문제라는 것을 확인한다.
2. 그래프 안에서 집합의 개수를 구하는 방법을 떠올린다 -> Union-Find, DFS, BFS

코드

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

const val MAX_PLUS_ONE = 2001

val graph = Array(MAX_PLUS_ONE){
    IntArray(MAX_PLUS_ONE)
}
val visited = Array(MAX_PLUS_ONE) {
    BooleanArray(MAX_PLUS_ONE)
}
val dX = arrayOf(-1, 1, 0, 0)
val dY = arrayOf(0, 0, -1, 1)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    var puCount = 0

    repeat(n) {
        val st = StringTokenizer(readLine())
        // 좌표를 오른쪽으로 이동 후 2배 증가
        val x1 = 2 * (st.nextToken().toInt() + 500); val y1 = 2  * (st.nextToken().toInt() + 500)
        val x2 = 2 * (st.nextToken().toInt() + 500); val y2 = 2 * (st.nextToken().toInt() + 500)

        drawRectangle(x1, y1, x2, y2)
    }

    for (y in 0 until MAX_PLUS_ONE){
        for (x in 0 until MAX_PLUS_ONE) {
            // 직사각형이 있고, 아직 그룹지어지지 않았다면
            if (graph[y][x] == 1 && visited[y][x].not()) {
                bfs(x, y)
                puCount++
            }
        }
    }

    // 연필은 (1000,1000)에 내린 상태에서 시작한다
    if (graph[1000][1000] == 1) print(puCount - 1)
    else print(puCount)
}

// 직사각형 그리기
fun drawRectangle(x1: Int, y1: Int, x2: Int, y2: Int) {
    for (i in y1..y2) {
        graph[i][x1] = 1
        graph[i][x2] = 1
    }

    for (i in x1 + 1 until x2) { // 변끼리 겹치는 점 제외
        graph[y1][i] = 1
        graph[y2][i] = 1
    }
}

fun bfs(startX: Int, startY: Int) {
    val q: Queue<Pair<Int, Int>> = LinkedList()
    q.add(Pair(startX, startY))
    visited[startY][startX] = true

    while (q.isNotEmpty()) {
        val (x, y) = q.poll()

        for (i in 0 until 4) {
            val nextX = x + dX[i]
            val nextY = y + dY[i]

            if (nextX !in 0 until MAX_SIZE || nextY !in 0 until MAX_SIZE) continue

            if (graph[nextY][nextX] == 1 && visited[nextY][nextX].not()) {
                visited[nextY][nextX] = true
                q.add(Pair(nextX, nextY))
            }
        }
    }
}

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

풀이

바다와 육지로 이루어진 인접 행렬 형태의 그래프가 주어진다. 그러면 모든 섬들을 찾아서, 그 섬들을 잇는 다리 중 가장 짧은 다리를 찾는 문제이다.

1. 섬 분류)

섬을 찾기 위해, 붙어있는 육지들을 하나로 묶어서 라벨링을 할 수 있다. 육지 한 점을 시작으로 인접한 곳을 탐색해 나가면서 인접한 곳에는 모두 같은 번호를 붙인다. dfs나 bfs를 사용할 수 있다.

2. 다리 연결)

방법 1) 모든 육지에서부터 한 번씩 경로를 탐색한다

이 부분이 까다로운데, 가장 쉽게 생각할 수 있는 방법은 모든 육지를 시작 지점으로 bfs를 수행하는 것이다. 너비 우선으로 탐색하기 때문에 시작 지점과 다른 섬의 육지에 처음 방문하게 됐을 때, 그 이동 거리가 그 지점에서 다른 섬으로 가는 최단 거리가 된다. 모든 지점에서 다른 섬으로 가는 최단 거리를 구하면, 그 중 최소값이 전체에서 가장 짧은 다리가 된다.

dfs를 사용하면 어떤 방향을 우선 탐색하느냐에 따라 아래처럼 돌아가는 경로를 먼저 탐색할 수 있다. 그래서 모든 점을 방문해야 하기 때문에 bfs를 사용하는 것이 좋다.

시간복잡도는 라벨링 O(n) + 경로 탐색 O(n^3) = O(n^3)이지만, n이 100이라서 괜찮다. 

방법 2) 육지를 모두 Queue에 넣고, 한 번만 bfs를 수행한다

사실 bfs를 사용하면 O(n^2)으로도 경로 탐색을 할 수 있다. 모든 육지를 Queue에 넣고 bfs를 한 번만 수행하는 것이다.

방문된 곳은 이동 거리와 어떤 섬에서부터 방문했는지를 표시한다. 그리고 다른 섬 or 다른 섬에서 방문한 바다를 만났을 때, (자신이 이동한 거리) + (다른 섬이 이동한 거리)가 최단 거리가 된다. 모든 지점이 돌아가면서 한 칸씩만 이동하기 때문이다.

(1)방문 표시 + (2)이동 거리 + (3)어떤 섬에서 방문했는지 표시해야 하기 때문에 복잡해서 떠올리기가 어려웠던 것 같다.

나는 그림처럼 방문한 바다에는 시작 지점의 라벨을 저장해서 방문 표시와 어떤 섬에서 시작했는지를 한번에 나타냈는데, 좀 헷갈렸어서 방문 체크를 위한 배열을 따로 사용하는 것도 좋을 것 같다. 이동 거리를 저장하는 배열은 따로 선언했다. 

코드 (방법1)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.min

val dRow = arrayOf(-1, 1, 0, 0)
val dCol = arrayOf(0, 0, -1, 1)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val graph = Array(n) { // 그래프 입력 받아서 저장
        StringTokenizer(readLine()).let { st ->
            IntArray(n) { st.nextToken().toInt() }
        }
    }

    var label = 2 // 중복 방문 체크를 위해 2부터 시작
    for (i in 0 until n) {
        for (j in 0 until n) {
            if (graph[i][j] == 1) {
                graph[i][j] = label // 섬 분류
                labelingDfs(graph, i, j, label++)
            }
        }
    }

    var answer = Integer.MAX_VALUE
    for (i in 0 until n) {   // 모든 육지마다 최단 경로 탐색
        for (j in 0 until n) {
            if (graph[i][j] > 1) {
                val copiedGraph = copyGraph(graph) // bfs 수행할 때마다 그래프 복제해야 함
                answer = min(answer, bfs(copiedGraph, i, j))
            }
        }
    }
    print(answer)
}

fun labelingDfs(graph: Array<IntArray>, row: Int, col: Int, label: Int) {
    for (i in 0 until 4) {
        val newRow = row + dRow[i]
        val newCol = col + dCol[i]

        if (newRow in graph.indices && newCol in graph.indices && graph[newRow][newCol] == 1) {
            graph[newRow][newCol] = label // 방문 체크 + 섬 라벨링
            labelingDfs(graph, newRow, newCol, label)
        }
    }
}

fun copyGraph(graph: Array<IntArray>): Array<IntArray>{
    val tempGraph = Array(graph.size){IntArray(graph.size)}
    for (i in graph.indices) {
        for (j in graph.indices){
            tempGraph[i][j] = graph[i][j]
        }
    }

    return tempGraph
}

fun bfs(graph: Array<IntArray>, startRow: Int, startCol: Int): Int {
    var distance = 0
    val label = graph[startRow][startCol]
    val queue: Queue<Pair<Int, Int>> = LinkedList()
    queue.offer(Pair(startRow, startCol))

    while (queue.isNotEmpty()) {
        val size = queue.size 

        // 다리를 한 번씩 모두 늘리면 distance 증가
        repeat(size) {
            val pair = queue.poll()
            val row = pair.first
            val col = pair.second

            for (i in 0 until 4) {
                val newRow = row + dRow[i]
                val newCol = col + dCol[i]

                if (newRow in graph.indices && newCol in graph.indices) {

                    // 방문하지 않았던 바다
                    if (graph[newRow][newCol] == 0) {
                        graph[newRow][newCol] = label
                        queue.offer(Pair(newRow, newCol))
                    }

                    // 바다도 아니고 같은 섬도 아니다 -> 다른 섬에 도착
                    else if (graph[newRow][newCol] != label) {
                        return distance // 경로 이동 횟수 반환
                    }
                }
            }
        }

        distance++
    }

    return Integer.MAX_VALUE // 섬 중앙에서 시작했을 때
}

코드 (방법2)

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

val dRow = arrayOf(-1, 1, 0, 0)
val dCol = arrayOf(0, 0, -1, 1)
val queue: Queue<Pair<Int, Int>> = LinkedList()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val graph = Array(n) { // 그래프 입력 받아서 저장
        StringTokenizer(readLine()).let { st ->
            IntArray(n) { st.nextToken().toInt() }
        }
    }

    var label = 2 // 중복 방문 체크를 위해 2부터 시작
    for (i in 0 until n) {
        for (j in 0 until n) {
            if (graph[i][j] == 1) {
                graph[i][j] = label // 섬 분류
                labelingDfs(graph, i, j, label++)
            }
        }
    }

    val answer = bfs(graph) // bfs로 최단 경로 탐색
    print(answer)
}

fun labelingDfs(graph: Array<IntArray>, row: Int, col: Int, label: Int) {
    var isEdge = false // 섬의 육지 중 테두리를 찾기 위한 플래그 

    for (i in 0 until 4) {
        val newRow = row + dRow[i]
        val newCol = col + dCol[i]

        if (newRow in graph.indices && newCol in graph.indices && graph[newRow][newCol] != label) {
            if (graph[newRow][newCol] == 0) { // 주변에 바다가 있다 -> 섬의 테두리이다
                isEdge = true
                continue
            }

            graph[newRow][newCol] = label
            labelingDfs(graph, newRow, newCol, label)
        }
    }

    if (isEdge) queue.add(Pair(row, col)) // 섬의 테두리에서만 bfs 시작
}

fun bfs(graph: Array<IntArray>): Int {
    val lengthGraph = Array(graph.size) { IntArray(graph.size) } // 이동 거리 저장하는 배열

    while (queue.isNotEmpty()) {
        val pair = queue.poll()
        val row = pair.first
        val col = pair.second

        for (i in 0 until 4) {
            val newRow = row + dRow[i]
            val newCol = col + dCol[i]

            // 그래프 바깥이거나 해당 라벨에서 이미 방문했던 곳 or 같은 섬이면 건너뛴다 
            if (newRow !in graph.indices || newCol !in graph.indices || graph[newRow][newCol] == graph[row][col]) {
                continue
            }

            // 0이 아니다 -> 다른 라벨이 방문했던 곳 or 다른 라벨의 섬 -> 최단 경로 탐색 완료 
            if (graph[newRow][newCol] != 0) {
                return lengthGraph[row][col] + lengthGraph[newRow][newCol]
            }

            graph[newRow][newCol] = graph[row][col] // 시작점의 라벨로 설정
            lengthGraph[newRow][newCol] = lengthGraph[row][col] + 1 // 이동 거리
            queue.offer(Pair(newRow, newCol))
        }
    }

    return 0
}

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

풀이

인접 행렬 형태의 그래프에서 익은 토마토와 인접한, 익지 않은 토마토를 방문하는 그래프 탐색 문제이다.

인접한 네 방향을 우선으로 확인하기 때문에 BFS를 사용할 수 있다. 만약 DFS를 사용하면 아래 예시처럼 방문했던 노드를 다시 방문해야 하는 상황이 생기기 때문에 거의 O(N * M)의 시간 복잡도를 갖는다.

ex) 1과 0은 토마토의 상태, 2와 3은 (1 + 걸린 일수) 

주의할 점은, 처음에 1로 주어진 토마토가 모두 Queue에 들어가는 시작점이 된다. 지금은 당연해 보이는데, 처음에 한 점에서만 시작한다고 생각해서 한참을 해맸다..ㅋㅋ

그리고 이전 토마토에서 인접한 곳을 방문하는 데 하루가 걸리므로, 그래프에 (이전 토마토의 그래프 값 + 1)을 저장하면 중복 방문 체크와 더불어 지난 일수도 알 수 있다. 

구현 방법

1. 그래프를 입력 받는다.

2. 익은 토마토(1)의 위치를 모두 큐에 넣고, 익지 않은 토마토의 개수도 세준다.

3. 그래프 값이 모두 1이라면 0을 출력하고 종료한다.

4. BFS로 모든 1에서부터 가능한 모든 0을 방문하면서, 그래프에 자신의 값에 1을 더한 값을 저장한다. 

5. 가능한 노드를 모두 탐색했는데 익지 않은 토마토가 남아있다면 -1을, 그렇지 않으면 그래프의 (최대값 -1)을 출력한다. (1에서부터 시작했으니까)

코드 1

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

var unripeCount = 0
val dRow = listOf(-1, 1, 0, 0)
val dCol = listOf(0, 0, -1, 1)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    val n = input[1].toInt()
    val m = input[0].toInt()
    val graph = Array(n){ IntArray(m) }
    val queue: Queue<Pair<Int, Int>> = LinkedList()

    for (i in 0 until n){
        val st = StringTokenizer(readLine())

        for (j in 0 until m){
            val tomato = st.nextToken().toInt()
            graph[i][j] = tomato

            when (tomato) {
                1 -> queue.add(Pair(i, j))
                0 -> unripeCount++  // 익지 않은 토마토
            }
        }
    }

    if (unripeCount == 0){  // 처음부터 모든 토마토가 익어있으면
        print(0)
        return
    }

    val day = bfsToRipe(graph, queue)
    if (unripeCount > 0) print(-1) // 모든 위치를 방문했는데 익지 않은 토마토가 남아있으면 -1
    else print(day)
}

fun bfsToRipe(graph: Array<IntArray>, queue: Queue<Pair<Int, Int>>): Int{
    var day = 0

    while(queue.isNotEmpty()){
        val pair = queue.poll() // 한 번 주변에게 영향을 준 토마토는 더 이상 쓰이지 않는다
        val row = pair.first
        val col = pair.second
        // 그래프에는 (영향을 받은 토마토 값 + 1)을 넣어서 날짜를 저장한다
        // 처음 토마토 날짜가 1부터 시작되므로, 마지막에 (최종 날짜 - 1)을 반환한다
        day = graph[row][col]

        for (i in 0 until 4){
            val newRow = row + dRow[i]
            val newCol = col + dCol[i]

            // 그래프를 벗어나있거나, 익은 토마토이거나, 토마토가 들어있지 않은 곳이거나
            if (newRow !in graph.indices || newCol !in graph[0].indices || graph[newRow][newCol] != 0) continue

            unripeCount--
            graph[newRow][newCol] = graph[row][col] + 1 // 하루가 지났을 때 익지 않은 토마토가 영향을 받아서 익게된다
            queue.offer(Pair(newRow, newCol))
        }
    }

    return day - 1
}

코드 2

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

var unripeCount = 0
val dRow = listOf(-1, 1, 0, 0)
val dCol = listOf(0, 0, -1, 1)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    val n = input[1].toInt()
    val m = input[0].toInt()
    val graph = Array(n){ IntArray(m) }
    val queue: Queue<Pair<Int, Int>> = LinkedList()

    for (i in 0 until n){
        val st = StringTokenizer(readLine())

        for (j in 0 until m){
            val tomato = st.nextToken().toInt()
            graph[i][j] = tomato

            when (tomato) {
                1 -> queue.add(Pair(i, j))
                0 -> unripeCount++  // 익지 않은 토마토
            }
        }
    }

    if (unripeCount == 0){  // 처음부터 모든 토마토가 익어있으면
        print(0)
        return
    }

    val day = bfsToRipe(graph, queue)
    if (unripeCount > 0) print(-1) // 모든 위치를 방문했는데 익지 않은 토마토가 남아있으면 -1
    else print(day)
}

fun bfsToRipe(graph: Array<IntArray>, queue: Queue<Pair<Int, Int>>): Int{
    var day = 0

    while(queue.isNotEmpty()){
        day++
        var size = queue.size // 현재 큐에 있는 토마토의 주변을 전부 탐색할 때마다 하루가 지난다

        repeat(size){
            val pair = queue.poll() // 한 번 주변에게 영향을 준 토마토는 더 이상 쓰이지 않는다
            val row = pair.first
            val col = pair.second

            for (i in 0 until 4){
                val newRow = row + dRow[i]
                val newCol = col + dCol[i]

                // 그래프를 벗어나있거나, 익은 토마토이거나, 토마토가 들어있지 않은 곳이거나
                if (newRow !in graph.indices || newCol !in graph[0].indices || graph[newRow][newCol] != 0) continue

                unripeCount--
                graph[newRow][newCol] = 1
                queue.offer(Pair(newRow, newCol))
            }
        }

    }

    // 마지막에 남아있는 토마토를 익히고 나서
    // 마지막 토마토 주변에 익지 않은 토마토가 있는지 한번 더 확인하기 때문에 1을 빼야한다
    return day-1 
}