Breadth First Search
- 인접한 노드를 먼저 탐색하는 방법
- 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘
- 최단 경로, 임의의 경로를 찾고 싶을 때 사용한다
- 큐를 이용하여 구현할 수 있다
1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다
2. 큐에서 원소를 꺼내어 그 칸에 인접한 칸(상,하,좌,우)에 대해 3번을 진행한다
3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입한다
4. 큐가 빌 때까지 2번을 반복한다
모든 칸이 큐에 한번씩 들어가므로 시간복잡도는 칸이 N개일 때, O(N)이고, 행이 R개 열이 C개라면 O(RC)
->bfs를 돌 때 큐에 쌓이는 순서는 거리순이다
구현 시 주의할 점 (자주 실수하는 부분)
1. 시작점에 방문했다는 표시를 꼭 남기지 않는다
2. 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남긴다
-> 같은 칸이 큐에 여러번 들어가게 되어 시간 초과, 메모리 초과가 날 수도 있다
3. 이웃한 원소가 범위를 벗어났는지에 대한 체크를 잘못했다
BOJ
import java.io.*
import java.util.*
lateinit var dx: Array<Int>
lateinit var dy: Array<Int>
lateinit var canvas: Array<IntArray>
lateinit var visited: Array<BooleanArray>
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
var count = 0 // 그림의 수
var maxArea = 0 // 그림의 영역
var st = StringTokenizer(readLine())
val n = st.nextToken().toInt()
val m = st.nextToken().toInt()
dx = arrayOf(1, -1, 0, 0)
dy = arrayOf(0, 0, -1, 1)
// 2차원 배열 생성 Array(row) { IntArray(col) }
canvas = Array(n) { IntArray(m) }
visited = Array(n) { BooleanArray(m) { false } }
// 1. 배열에 도화지 데이터 담기
for (row in 0 until n) {
st = StringTokenizer(readLine())
for (col in 0 until m) {
canvas[row][col] = st.nextToken().toInt()
}
}
// 캔버스 전체를 탐색 : 1이면서 방문하지 않은 영역을 체크
for (i in 0 until n) {
for (j in 0 until m) {
if (canvas[i][j] == 0 || visited[i][j]) continue
count++
val area = bfs(i, j, n, m)
if (maxArea < area)
maxArea = area
}
}
print("$count\n$maxArea")
}
// return area
fun bfs(startRow: Int, startCol: Int, n: Int, m: Int): Int {
// 배열을 탐색할 큐 (row, col)을 저장할 수 있도록 Pair 를 사용한다
val queue: Queue<Pair<Int, Int>> = ArrayDeque()
// 시작하는 칸을 큐에 넣고 방문했다고 표시한다
visited[startRow][startCol] = true
queue.add(Pair(startRow, startCol))
var area = 1 // 그림 영역
while (queue.isNotEmpty()) {
val current = queue.remove()
// 인접한(상하좌우)칸을 탐색한다
for (i in 0 until 4) {
val nx = current.first + dx[i]
val ny = current.second + dy[i]
// 방문한 칸이 0이 아니고 최초 방문일 경우에 방문했다는 표시를 하고 큐에 넣는다
// 범위를 초과하지 않았는지 확인 필수
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue
if (canvas[nx][ny] == 0 || visited[nx][ny]) continue
visited[nx][ny] = true
queue.add(Pair(nx, ny))
area++
}
}
return area
}
1 | 1 | 0 |
1 | 1 | 1 |
1 | 0 | 1 |
1 | 2 | 0 |
2 | 1 | 1 |
1 | 0 | 1 |
1 | 2 | 0 |
2 | 3 | 1 |
3 | 0 | 1 |
1 | 2 | 0 |
2 | 3 | 4 |
3 | 0 | 1 |
1 | 2 | 0 |
2 | 3 | 4 |
3 | 0 | 5 |
현재 위치에서 인접한 위치에 있는 칸들은 현재 위치보다 거리가 1만큼 크다
따라서 탐색하는 과정에서 방문 시 위치 값을 현재보다 1 크게 설정해준 후 저장해주어야 한다
import java.io.*
import java.util.*
lateinit var graph: Array<IntArray>
lateinit var distance: Array<IntArray>
lateinit var dx: Array<Int>
lateinit var dy: Array<Int>
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
var st = StringTokenizer(readLine())
val n = st.nextToken().toInt()
val m = st.nextToken().toInt()
graph = Array(n) { IntArray(m) }
distance = Array(n) { IntArray(m) { -1 } }
dx = arrayOf(1, -1, 0, 0)
dy = arrayOf(0, 0, -1, 1)
for (row in 0 until n) {
st = StringTokenizer(readLine())
val list = st.nextToken()
for (col in 0 until m) {
graph[row][col] = list[col].digitToInt()
}
}
for (i in 0 until n) {
for (j in 0 until m) {
if (distance[i][j] != -1 || graph[i][j] == 0) continue
bfs(i, j, n, m)
}
}
print(distance[n-1][m-1])
}
fun bfs(startRowIdx: Int, startColIdx: Int, n: Int, m: Int) {
// 좌표 저장할 큐
val queue = ArrayDeque<Pair<Int, Int>>()
// 시작칸 방문했다는 표시 남기기
distance[startRowIdx][startColIdx] = 1
queue.add(Pair(startRowIdx, startColIdx))
while (queue.isNotEmpty()) {
val current = queue.remove()
for (i in 0 until 4) {
val nx = current.first + dx[i]
val ny = current.second + dy[i]
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue
if (graph[nx][ny] == 0 || distance[nx][ny] != -1) continue
// 상하좌우 위치는 현재 위치보다 1만큼 더 거리가 늘어남
distance[nx][ny] = distance[current.first][current.second] + 1
queue.add(Pair(nx, ny))
}
}
}
7576. 토마토 시작점이 여러개일 때 거리 구하기
토마토 상자 안에서 익은 토마토의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다
토마토가 익을 때까지의 최소 날짜를 출력하라 (모든 토마토가 익어있을 경우 0, 토마토가 익지 못하는 상황 -1)
1: 익은 토마토, 0 : 익지 않은 토마토, -1: 토마토가 없는 칸
이 문제에서 중요하게 볼 조건은 익은 토마토가 여러개일 경우다
1. 주어진 배열에서 익은 토마토가 있는 위치를 모두 찾아 큐에 저장한다
2. 익은 토마토가 있는 부분에서부터 bfs를 시작한다
- 익지 않은 토마토는 주변에 익은 토마토가 있을 경우 하루 뒤에 익기 때문에, 현재 위치 토마토가 익은 날짜에 +1을 해주면 된다
import java.io.*
import java.util.*
lateinit var box: Array<IntArray>
lateinit var tomato: Queue<Pair<Int, Int>>
lateinit var days: Array<IntArray>
lateinit var dx: Array<Int>
lateinit var dy: Array<Int>
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
var st = StringTokenizer(readLine())
val m = st.nextToken().toInt() // 가로
val n = st.nextToken().toInt() // 세로
var status = 0
box = Array(n) { IntArray(m) }
tomato = ArrayDeque()
days = Array(n) { IntArray(m) { -1 } }
dx = arrayOf(1, -1, 0, 0)
dy = arrayOf(0, 0, -1, 1)
// 담기
for (i in 0 until n) {
st = StringTokenizer(readLine())
for (j in 0 until m) {
val cur = st.nextToken().toInt()
box[i][j] = cur
if (cur == 1) { // 익은 토마토
tomato.add(Pair(i, j))
days[i][j] = 0
}
if (cur == -1) { // 비어 있을 경우
days[i][j] = -100
}
}
}
// bfs : 이미 익은 토마토를 제외한 남은 토마토들이 익는데까지 걸리는 시간 구하기
while (tomato.isNotEmpty()) {
val current = tomato.remove()
for (i in 0 until 4) {
val nx = current.first + dx[i]
val ny = current.second + dy[i]
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue
if (box[nx][ny] == -1 || days[nx][ny] != -1) continue
tomato.add(Pair(nx, ny))
days[nx][ny] = days[current.first][current.second] + 1
status = days[current.first][current.second] + 1
}
}
for (i in 0 until n) {
for (j in 0 until m) {
if (days[i][j] == -1) {
status = -1
break
}
}
}
print(status)
}
4179 불 : 시작지점이 여러개일 경우2
불이 도달하기 전에 지날 수 있는지를 판별해야 한다
그래서 먼저 불이 각 지점에 도달하는데 걸리는 시간을 구하고,
지훈이가 해당 지점을 지날 때 불이 도달하는지 확인한다
지훈이는 미로의 가장자리에서 탈출할 수 있기 때문에 미로 범위를 넘어설 시에 탈출이라고 본다
if (nx < 0 || nx >= r || ny < 0 || ny >= c) {
bw.write("${jDist[current.first][current.second] + 1}")
}
근데 계속 틀렸다고 나와서 반례를 확인해보니, 지훈이가 있는곳에 불이 하나도 도달하지 않는 경우를 발견했다
예를 들면 이런 경우 불은 지훈이에게 도달하지 못한다
5 4
F###
#...
#.##
#.J#
####
틀린과정:
불이 지나가는 시간에 대한 배열의 초기값 설정을 -1로 해서 불에 대한 bfs 실행 후에 이런 결과값이 나오는데
불 bfs 실행 후 결과값
0 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
지훈이가 이동하는 시간보다 불이 난 시간이 더 빠를 경우 지나가지 못하는 길로 조건을 설정해뒀는데
위 같은 경우에는 지훈이 이동시간이 -1보다는 무조건 크게 되어서 결과값으로 IMPOSSIBLE 이 나오게 된다
따라서 지훈이 bfs를 돌때 조건을 아래와 같이 설정해주어야 한다
// 벽이거나 지훈이가 지나갔던 길일 경우
if (graph[nx][ny] == '#' || jDist[nx][ny] >= 0) continue
// 해당 위치가 불이 지나간 길이고 불의 지훈이보다 먼저 도달했을 경우
if (fDist[nx][ny] != -1 && fDist[nx][ny] <= jDist[current.first][current.second] + 1) continue
풀이:
import java.io.*
import java.util.*
import kotlin.system.exitProcess
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
var st = StringTokenizer(readLine())
val r = st.nextToken().toInt()
val c = st.nextToken().toInt()
val graph: Array<CharArray> = Array(r) { CharArray(c) }
val fDist: Array<IntArray> = Array(r) { IntArray(c) { -1 } }
val jDist: Array<IntArray> = Array(r) { IntArray(c) { -1 } }
val dx = arrayOf(1, -1, 0, 0)
val dy = arrayOf(0, 0, -1 ,1)
val fire: Queue<Pair<Int, Int>> = ArrayDeque()
val jh: Queue<Pair<Int, Int>> = ArrayDeque()
for (i in 0 until r) {
st = StringTokenizer(readLine())
val list = st.nextToken()
for (j in 0 until c) {
graph[i][j] = list[j]
if (list[j] == 'F') {
fire.add(Pair(i, j))
fDist[i][j] = 0
}
if (list[j] == 'J') {
jh.add(Pair(i, j))
jDist[i][j] = 0
}
}
}
// fire bfs
while (fire.isNotEmpty()) {
val current = fire.remove()
for (i in 0 until 4) {
val nx = current.first + dx[i]
val ny = current.second + dy[i]
// 영역 벗어남
if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue
// 지나갈 수 없거나 이미 지나간 길
if (graph[nx][ny] == '#' || fDist[nx][ny] >= 0) continue
fDist[nx][ny] = fDist[current.first][current.second] + 1
fire.add(Pair(nx, ny))
}
}
val bw = BufferedWriter(OutputStreamWriter(System.out))
// JH bfs
while (jh.isNotEmpty()) {
val current = jh.remove()
for (i in 0 until 4) {
val nx = current.first + dx[i]
val ny = current.second + dy[i]
if (nx < 0 || nx >= r || ny < 0 || ny >= c) {
bw.write("${jDist[current.first][current.second] + 1}")
bw.close()
exitProcess(0)
}
if (graph[nx][ny] == '#' || jDist[nx][ny] >= 0) continue
if (fDist[nx][ny] != -1 && fDist[nx][ny] <= jDist[current.first][current.second] + 1) continue
jh.add(Pair(nx, ny))
jDist[nx][ny] = jDist[current.first][current.second] + 1
}
}
bw.write("IMPOSSIBLE\n")
bw.close()
}
위에 토마토 문제도 그렇고 다른 풀이랑 비교해보니 내 풀이는 꽤 느린편인데
반복문 구조는 똑같은데, Pair를 써서 그런건지 아니면 exitProcess를 써서 그런건지 정확한 이유는 잘 모르겠따
나중에 다시 풀때 개선해봐야겠다
이 문제는 불이 지훈이의 경로에 영향을 줘서 불 bfs -> 지훈 bfs 로 해주면 풀리지만
만약에 서로 영향을 줄 경우 bfs로는 풀 수 없다는 점을 기억하자
얼핏 보았을 때는 이것도 bfs로 푸나? 했는데 이동할 수 있는 위치가 상하좌우가 아닐 뿐,
일정 시간마다 어떤 위치로 이동할 수 있다는 점, 그에 따라 걸리는 시간을 구한다는 것이 bfs문제들과 같았다
import java.io.*
import java.util.*
lateinit var queue: Queue<Int>
lateinit var dist: IntArray
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val (n, k) = readLine().split(" ").map { it.toInt() }
queue = ArrayDeque()
dist = IntArray(100001) { -1 }
dist[n] = 0
queue.add(n)
if (n == k) {
print("0")
} else {
print("${bfs(k)}")
}
}
fun move(x: Int) = arrayOf(x - 1, x + 1, 2 * x)
fun bfs(k: Int):Int {
while (queue.isNotEmpty()) {
val current = queue.remove()
val locations = move(current)
for (i in locations.indices) {
val number = locations[i]
// 동생이 있는 위치
if (number == k) return dist[current] + 1
// 범위 밖
if (number < 0 || number > 100000) continue
// 이미 방문한 적 있음
if (dist[number] != -1) continue
dist[number] = dist[current] + 1
queue.add(number)
}
}
return -1
}
참고
https://www.youtube.com/watch?v=ftOmGdm95XI
'알고리즘&자료구조' 카테고리의 다른 글
BFS 응용문제 풀기 (0) | 2022.12.06 |
---|---|
BFS 기본 문제 (0) | 2022.12.02 |
스택의 활용 : 수식의 괄호쌍 (0) | 2022.11.25 |
덱 : Deque (1) | 2022.11.23 |
Stack (0) | 2022.11.22 |