{ }codelper

배우기 › Craykon

알고리즘 · 33

너비 우선 탐색과 위상 정렬

큐로 가까운 곳부터 넓혀 가장 적은 걸음 수를 구하고, 먼저 할 일이 앞에 오게 줄을 세워요.

너비 우선 탐색(BFS)은 시작점에서 가까운 곳부터 차례로 넓혀 가고, 위상 정렬은 "이것을 끝내야 저것을 할 수 있다"는 조건을 모두 지키는 차례를 만들어요.
아래 예제는 "a를 끝내야 b를 시작할 수 있다"는 쌍을 읽어, 1번 일에서 화살표를 가장 적게 몇 번 따라가면 일마다 닿는지(닿지 않으면 -1)와, 조건을 지키며 일을 하는 차례를 찍어요.

nm = 콘솔.수들읽기();n = nm[0];m = nm[1];adj = 새목록(n + 1, []); // adj[a] = a를 끝내야 시작할 수 있는 일들need = 새목록(n + 1, 0); // need[b] = b보다 먼저 해야 하는데 아직 안 끝난 일의 수반복 (i = 0; i < m; i++){    ab = 콘솔.수들읽기();    a = ab[0];    b = ab[1];    adj[a].넣기(b);    need[b]++;} // 너비 우선 탐색: 1번 일에서 화살표를 가장 적게 몇 번 따라가면 닿는지dist = 새목록(n + 1, -1); // -1이면 아직 안 간 곳dist[1] = 0;queue = [1];head = 0; // 큐의 맨 앞 자리. 꺼낼 때마다 한 칸씩 뒤로 가요동안 (head < queue.개수){    v = queue[head];    head++;    각각 (w 에서 adj[v])    {        만약 (dist[w] == -1)        {            dist[w] = dist[v] + 1; // 큐에 넣을 때 바로 적어요            queue.넣기(w);        }    }}콘솔.쓰기(dist.부분목록(1, n).잇기(" ")); // 위상 정렬: 먼저 할 일이 남지 않은 일부터 꺼내요order = [];queue = [];head = 0;반복 (v = 1; v <= n; v++){    만약 (need[v] == 0)    {        queue.넣기(v);    }}동안 (head < queue.개수){    v = queue[head];    head++;    order.넣기(v);    각각 (w 에서 adj[v])    {        need[w]--; // v가 끝났으니 w가 기다리는 일이 하나 줄어요        만약 (need[w] == 0)        {            queue.넣기(w);        }    }}콘솔.쓰기(order.잇기(" "));
stdin
6 6
1 2
2 3
3 4
1 4
4 5
6 3
stdout
0 1 2 1 2 -1
1 6 2 3 4 5

핵심

  • BFS는 큐에 "찾았지만 아직 이웃을 보지 않은 곳"을 넣어 둬요.
    시작점을 걸음 수 0으로 넣고, 맨 앞을 꺼내 아직 안 간 이웃마다 dist[w] = dist[v] + 1을 적고 큐 뒤에 넣는 일을 큐가 빌 때까지 되풀이해요.
  • 큐는 먼저 넣은 것이 먼저 나오니까 0걸음인 곳, 1걸음인 곳, 2걸음인 곳 차례로 나와요.
    그래서 어떤 곳을 처음 찾았을 때의 걸음 수가 가장 적은 걸음 수예요.
    예제에서 4번은 1 → 2 → 3 → 4로도 닿지만, 1 → 4로 먼저 찾아서 1이에요.
  • 표시는 큐에 넣을 때 해요.
    예제는 dist가 -1이 아니면 이미 찾은 곳으로 쳐서, 표시와 걸음 수를 한 번에 적어요.
  • 격자에서도 똑같아요.
    칸 하나가 점이고 위·아래·왼쪽·오른쪽 칸이 이웃이에요.
    이웃 목록을 만드는 대신 2차원 목록 단원의 방향 목록(di, dj)으로 이웃 칸을 구하고, 격자 밖과 벽을 걸러요.
  • 위상 정렬은 BFS가 끝난 뒤 큐를 비운 채로 처음부터 따로 한 번 더 도는 일이에요(둘째 줄 출력).
    같은 adj를 쓰지만 dist는 쓰지 않아요.
    일마다 아직 끝나지 않은 먼저 할 일의 수 need를 세어 둬요.
    need가 0인 일을 큐에 넣고, 하나 꺼내 차례에 적은 다음, 그 일을 기다리던 일들의 need를 1씩 줄여요.
    0이 된 일은 이제 할 수 있으니 큐에 넣어요.
  • 조건을 지키는 차례는 여러 개일 수 있어요(예제는 1 6 2 3 4 5도 6 1 2 3 4 5도 맞아요).
    조건이 고리를 이루면(2 → 3 → 2) 고리 안의 일은 need가 끝내 0이 되지 않아 차례에서 빠져요.
    그래서 차례의 길이가 n보다 짧으면 고리가 있다는 뜻이에요.

언어별로 쓰는 법

Pythonfrom collections import deque — queue.append(w)로 넣고 queue.popleft()로 맨 앞을 꺼내요.
처음 값은 deque([1])처럼 넣어요
JavaScript큐가 따로 없어요.
배열에 push로 넣고, 맨 앞 자리 head를 두어 queue[head++]로 꺼내요.
queue.shift()도 맨 앞을 꺼내지만 남은 값을 모두 한 칸씩 당겨서, 스택과 큐 단원에서 본 것처럼 값이 많으면 느려요
TypeScriptJavaScript와 같아요.
타입은 number[]
JavaArrayDeque<Integer> — queue.add(w)로 넣고 queue.poll()로 맨 앞을 꺼내요.
새 int[]는 0으로 채워지니 Arrays.fill(dist, -1)로 바꿔요
C#Queue<int> — Enqueue(w)로 넣고 Dequeue()로 맨 앞을 꺼내요.
-1로 채운 배열은 Enumerable.Repeat(-1, n + 1).ToArray()
C++std::queue<int> — push(w)로 넣어요.
front()로 맨 앞을 읽고 pop()으로 빼요(pop()은 값을 돌려주지 않아요).
-1로 채운 벡터는 std::vector<int> dist(n + 1, -1)
C큐가 없어서 배열과 번호 두 개로 만들어요.
queue[tail++] = w로 넣고 queue[head++]로 꺼내요.
head < tail이면 아직 남은 거예요
Craykon목록 끝에 queue.넣기(w)로 넣고, 맨 앞 자리 head를 두어 queue[head]를 읽은 뒤 head++해요.
동안 (head < queue.개수)이면 아직 남은 거예요.
-1로 채운 목록은 새목록(n + 1, -1)

자주 하는 실수

큐에서 꺼낼 때 표시했어요

int v = queue.front();
queue.pop();
seen[v] = true; // 꺼낼 때 표시
for (int w : adj[v]) {
    if (!seen[w]) {
        dist[w] = dist[v] + 1;
        queue.push(w);
    }
}

→ 1 → 2, 1 → 3, 2 → 3에서 0 1 2가 나와요(맞는 답은 0 1 1). 3번이 큐에서 기다리는 동안 2번이 3번을 또 넣으면서 걸음 수를 2로 덮어써요

큐에 넣는 바로 그 자리에서 표시해요.
그러면 한 곳은 큐에 한 번만 들어가요.

차례의 길이를 확인하지 않았어요

// 1 → 2, 2 → 3, 3 → 2
while (!queue.isEmpty()) {
    int v = queue.poll();
    order.add(v);
    for (int w : adj.get(v)) {
        need[w]--;
        if (need[w] == 0) queue.add(w);
    }
}
System.out.println(order);

→ [1] — 오류 없이 끝나지만 2번과 3번이 빠졌어요. 서로를 기다려서 need가 0이 되지 않아요

끝난 뒤 차례에 든 일이 n개인지 확인해요: if (order.size() < n).
모자라면 고리가 있어서 모두 할 수는 없는 거예요.

맨 앞이 아니라 맨 뒤에서 꺼냈어요Python · JavaScript · TypeScript

adj = [[], [2, 3], [5], [4], [5], []]
dist = [-1] * 6
dist[1] = 0
queue = [1]
while queue:
    v = queue.pop()
    for w in adj[v]:
        if dist[w] == -1:
            dist[w] = dist[v] + 1
            queue.append(w)
print(*dist[1:])

→ 0 1 1 2 3 — 맞는 답은 0 1 1 2 2예요. pop()은 가장 나중에 넣은 것을 꺼내서 큐가 아니라 스택이 되고, 먼 곳부터 파고들어요. JavaScript 배열의 pop()도 같아요

deque의 popleft()로 맨 앞을 꺼내요.
JavaScript는 head 번호를 두고 queue[head++]로 꺼내요.

언어마다 다른 점
BFS가 가장 적은 걸음 수를 주는 것은 모든 화살표가 똑같이 한 걸음일 때예요.
그리고 위상 정렬에서 쌍 "a b"가 "a 먼저"라는 뜻이면, adj[a]에 b를 넣고 need[b]를 올려요.
화살표가 들어오는 쪽의 수를 세는 거예요.

연습 문제

  1. 난로 온기가 퍼지는 교실8P0378
  2. 단서만으로 정해지는 등수8P0381
  3. 문이 하나씩 잠기는 박물관8P0291
  4. 선수 과목을 지키는 학기 계획8P0197
  5. 낡은 파일만 다시 만들기8P0326
  6. 두 물통으로 딱 맞게 재는 순서8P0210
  7. 축제 준비 일의 여유 시간8P0303
  8. 섬 지도8P0072