[코딩 테스트] BFS

유민국·2023년 6월 25일

코테

BFS

BFS의 목적은 임의의 정점에서 시작해서, 모든 정점을 한 번씩 방문하는 것이다.
모든 가중치가 1일 때, 최단 거리를 구하는 알고리즘이다.
문제를 그래프로 바꿔서 푼다
queue, deque를 사용해서 푼다.

visit[], dist[]

visit

BFS는 모든 정점을 한 번만 방문 하는 알고리즘으로 visit 배열 변수를 선언해 방문 여부를 확인한다.
dist는 해당 정점을 몇 번만에 방문했는지 기록한다.

거리는 항상 1 이상이기 때문에 -1일 경우 방문을 하지 않은걸로 처리하면 두 배열을 합쳐서 표현이 가능하다.

시간 복잡도

O(V+E)
v: 정점
E: 간선

역추적 문제

from[정점] : 어디에서 왔는지
N에서 K를 간다고 한다면
N 부터 from을 통해서 N까지 가야한다.
즉, 역순으로 저장되기 때문에, 다시 역순으로 구하는 것이 필요하다.

방법 1. 재귀 함수를 구현해서 from을 역추적한다.
방법 2. 반복문을 사용하여 k->n 으로 갈 때까지 반복시킨다.(스택 사용)

정점을 나누는 문제

이동할 수 있는 방법이 다른 경우에는 같은 정점이라도 다른 정점이다.
ex. A->B 로 가지만 간선이 2개이며 위로 가거나 밑으로 갈 수 있을 경우

BFS를 이용해 해결할 수 있는 문제

최소 비용 문제이어야 한다
간선의 가중치가 1이어야 한다
정점과 간선의 개수가 적어야 한다. (적다는 것은 문제의 조건에 맞춰서 해결할 수 있다는 것을
의미한다)

간선의 가중치가 문제에서 구하라고 하는 최소 비용과 의미가 일치해야 한다
즉, 거리의 최소값을 구하는 문제라면 가중치는 거리를 의미해야 하고, 시간의 최소값을 구하는
문제라면 가중치는 시간을 의미해야 한다

덱 사용하기

BFS는 가중치가 1일 때 해결할 수 있지만, 덱을 사용하면 0,1일 때 사용할 수 있다.

현재 큐에 넣는 것을 덱의 앞에 다음 큐에 넣는 것의 뒤에 방법을 사용하여 가중치가 0과1인 것을 해결할 수 있다.

예시 1(기본)

val br = BufferedReader(InputStreamReader(System.`in`))
val q = ArrayDeque<Int>()
val token = StringTokenizer(br.readLine())
val n = token.nextToken().toInt()
val k = token.nextToken().toInt()
val d = Array<Int>(2*maxOf(n,k,10)){
    -1
}
val MAX = 2*k
q.add(n)
d[n] = 0
while(!q.isEmpty()){
    val now = q.removeFirst()
    if(now + 1 < MAX){
        if(d[now+1] == -1) {
            q.add(now + 1)
            d[now + 1] = d[now] + 1
        }
    }

    if(now - 1 >= 0){
        if(d[now-1] == -1) {
            q.add(now - 1)
            d[now - 1] = d[now] + 1
        }
    }

    if(now * 2 < MAX){
        if(d[now*2] == -1) {
            q.add(now*2)
            d[now*2] = d[now] + 1
        }
    }
}

print(d[k])

예시 2(역추적)

val br = BufferedReader(InputStreamReader(System.`in`))
val q = ArrayDeque<Int>()
val token = StringTokenizer(br.readLine())
val n = token.nextToken().toInt()
val k = token.nextToken().toInt()
val d = Array<Int>(2*maxOf(n,k,10)){
    -1
}
val from = Array<Int>(2*maxOf(n,k,10)){
    0
}
val MAX = 2*k
q.add(n)
d[n] = 0
while(!q.isEmpty()){
    val now = q.removeFirst()
    if(now + 1 < MAX){
        if(d[now+1] == -1) {
            q.add(now + 1)
            d[now + 1] = d[now] + 1
            from[now + 1] = now
        }
    }

    if(now - 1 >= 0){
        if(d[now-1] == -1) {
            q.add(now - 1)
            d[now - 1] = d[now] + 1
            from[now-1] = now
        }
    }

    if(now * 2 < MAX){
        if(d[now*2] == -1) {
            q.add(now*2)
            d[now*2] = d[now] + 1
            from[now*2] = now
        }
    }
}

val stc = Stack<Int>()
println(d[k])
var temp:Int = k
stc.push(k)
repeat(d[k]){
    temp = from[temp]
    stc.push(temp)
}
while(!stc.isEmpty()){
    print("${stc.pop()} ")
}

예시 3 (덱 사용)

val br = BufferedReader(InputStreamReader(System.`in`))
val token = StringTokenizer(br.readLine())
val n = token.nextToken().toInt()
val k = token.nextToken().toInt()
val d = Array(200001){
    -1
}
d[n] = 0
val q = ArrayDeque<Int>()
val MAX = 200001
q.add(n)
while(!q.isEmpty()){
    val now = q.removeFirst()
    // 0초 걸리는걸 우선으로 방문해야함
    // *2 칸
    if(now*2 < MAX) {
        if (d[now * 2] == -1) {
            d[now * 2] = d[now]
            q.addFirst(now * 2)
        }
    }
    // -1 칸
    if(now - 1 >= 0){
        if(d[now-1] == -1){
            d[now-1] = d[now] + 1
            q.add(now-1)
        }
    }
    // 1 칸
    if(now + 1 < MAX){
        if(d[now+1] == -1){
            d[now+1] = d[now] + 1
            q.add(now+1)
        }
    }
}

print(d[k])