https://www.acmicpc.net/problem/7576
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
풀이
인접 행렬 형태의 그래프에서 익은 토마토와 인접한, 익지 않은 토마토를 방문하는 그래프 탐색 문제이다.
인접한 네 방향을 우선으로 확인하기 때문에 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
}'Problem Solving > 백준' 카테고리의 다른 글
| 백준 1167번: 트리의 지름 (0) | 2021.12.25 |
|---|---|
| 백준 2146번: 다리 만들기 (Kotlin) (0) | 2021.12.24 |
| 백준 9466번: 텀 프로젝트 (Kotlin) (0) | 2021.12.22 |
| 백준 1406번: 에디터 (Kotlin) (0) | 2021.12.16 |
| 백준 2225번: 합분해 (Kotlin) (0) | 2021.12.13 |
