BOJ_1260 DFS와 BFS

TOC {:toc}

이 글은 백준 온라인 저지의 1260번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.05.07 (Python)

메모리	시간	코드 길이
33292 KB	268 ms	1041 B

단계	시작 시각	끝난 시각
문제 이해	20:26:12	20:27:07
풀이 생각	20:27:09	20:31:38
코딩	20:32:05	21:56:32

import sys
from collections import deque
input = sys.stdin.readline

def dfs(root):
    visited = []
    stack = [root]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            if n in edge:
                temp = list(set(edge[n]) - set(visited))
                temp.sort(reverse=True)
                stack += temp
    return " ".join(map(str, visited))

def bfs(root):
    visited = []
    queue = deque([root])

    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            if n in edge:
                temp = list(set(edge[n]) - set(visited))
                temp.sort()
                queue += temp
    return " ".join(map(str, visited))

N, M, V = map(int, input().split())

edge = {}
for _ in range(M):
    a, b = map(int, input().split())
    if a in edge:
        edge[a].append(b)
    else:
        edge[a] = [b]
    if b in edge:
        edge[b].append(a)
    else:
        edge[b] = [a]

print(dfs(V))
print(bfs(V))

아이디어 & 풀이

방문해야 하는 인접 노드를 추가하면서 방문한 노드 순서대로 리스트(i.e., visited)를 만들어 간다.

방문해야 하는 노드를 추가하는데 dfs는 스택을, bfs는 큐를 이용한다.

우선 노드 사이의 인접 관계를 나타내는 edge 딕셔너리를 만든다.

{현재 노드 : [인접한 노드의 리스트]} 꼴로 작성한다.
방문해야 하는 인접 노드를 파악하는 데 사용된다.

그래프를 탐색하는 과정은 다음과 같다.

스택이나 큐에서 원소를 pop 한다. 해당 원소가 다음에 방문해야 할 노드이다.
- 처음에도 스택이나 큐에 pop 할 값이 있어야 하므로 스택과 큐는 [루트 노드]로 초기화하면 된다.
해당 노드를 이전에 방문했는지 확인한다. 방문한 노드인 visited에 해당 값이 존재하는지를 확인하면 된다.
방문하지 않았으면 해당 노드를 이동한다. visited에 원소를 추가하면 된다.

새로 방문한 노드의 인접한 노드에 방문할 수 있게 되었으므로 스택이나 큐에 추가한다.

현재 노드에 인접한 노드의 리스트가 edge[현재 노드]이므로 이를 스택이나 큐에 추가하면 된다.
이미 방문한 곳은 제외해야 하므로 edge[현재 노드]에서 visited에 존재하는 원소들은 제외한다.
인접한 노드는 숫자가 작은 순서대로 방문해야 하므로 스택이나 큐에 추가하기 전에 정렬해준다.
- 스택과 큐에서 pop 되는 위치가 다르기 때문에 정렬 순서를 다르게 해주어야 한다.
- 마지막 숫자부터 pop 하는 ‘스택’은 마지막에 가장 작은 수가 와야 하므로 내림차순으로 정렬한다.
- 첫 번째 숫자부터 pop 하는 ‘큐’는 처음에 가장 작은 수가 와야 하므로 오름차순으로 정렬한다.

피드백

dfs를 재귀로 구현하기도 해서 bfs도 재귀로 구현해보려고 했는데 재귀로 구현이 불가능한 것 같다.

2022.04.05 (JS)

메모리	시간	코드 길이
16112 KB	276 ms	1349 B

단계	시작 시각	끝난 시각
문제 이해	16:51:41	16:52:34
풀이 생각	16:52:35	16:53:18
코딩	16:53:19	17:42:32
디버깅 1	17:43:04	18:02:11
디버깅 2	20:20:59	20:51:00

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

function dfs() {
    const visited = new Array(N + 1).fill(false);
    const stack = [V];
    const res = [];

    while (stack.length) {
        const n = stack.pop();

        if (!visited[n]) {
            visited[n] = true;
            res.push(n);

            if (graph[n].length) stack.push(...[...graph[n]].reverse());
            else stack.push(...graph[n]);
        }
    }

    console.log(res.join(" "));
}

function bfs() {
    const visited = new Array(N + 1).fill(false);
    const queue = [V];
    const res = [];

    while (queue.length) {
        const n = queue.shift();

        if (!visited[n]) {
            visited[n] = true;
            res.push(n);
            queue.push(...graph[n]);
        }
    }

    console.log(res.join(" "));
}

const [NMV, ...lines] = input;
const [N, M, V] = NMV.split(" ").map((n) => parseInt(n));
const edges = lines.map((edge) => edge.split(" ").map((n) => parseInt(n)));
const graph = Array(N + 1)
    .fill()
    .map((i) => []);

edges.forEach((edge) => {
    const [A, B] = edge;
    if (!graph[A]) graph[A] = [B];
    else graph[A].push(B);
    if (!graph[B]) graph[B] = [A];
    else graph[B].push(A);
});

graph.forEach((edge) => {
    edge.sort((a, b) => a - b);
});

dfs();
bfs();

디버그

graph를 구성할 때 sort를 안해서 틀렸었다.
dfs를 재귀를 이용하지 않고 stack를 이용해서 풀었는데 연결 노드를 추가할 때 sort 되어있는 역순으로 추가해야 해서 애먹었다.
- reverse() 함수는 원본을 변경시켜서 복사해서 해야 하는데 복사하는 과정에서 문제가 있는지 계속 런타임 에러가 발생했다.
```
    // 에러가 발생한 부분
    let reverse = [...graph[n]];
    if (graph[n].length > 1) reverse.reverse();
    stack.push(...reverse);
```
- 아마 graph[n]의 원소가 없을 때 이를 spread 연산으로 복사하는 과정에서 오류가 발생했을 것 같다. 그래서 graph[n]의 원소가 존재할 때만 reverse를 하도록 변경.

참고 답안

import sys
input = sys.stdin.readline

def dfs(root):
    stack = [root]
    visited = []
    checked = [0 for _ in range(N + 1)]

    while stack:
        n = stack.pop()
        if not checked[n]:
            checked[n] = 1
            visited.append(n)
            stack += edge[n]

    return visited


def bfs(root):
    queue = [root]
    visited = []
    checked = [0 for _ in range(N + 1)]
    checked[V] = 1

    while queue:
        n = queue.pop()
        visited.append(n)
        for i in reversed(edge[n]):
            if not checked[i]:
                checked[i] = 1
                queue = [i] + queue

      # 일관성을 위해서는 다음과 같이 작성할 수도 있다.
      # 실행 속도는 위의 코드가 더 빠르다.
      # n = queue.pop()
      # if not checked[n]:
      #     checked[n] = 1
      #     visited.append(n)
      #     queue = edge[n] + queue

    return visited

N, M, V = map(int, input().split())
edge = [[] for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)

for e in edge:
    e.sort(reverse=True)

print(" ".join(map(str, dfs(V))))
print(" ".join(map(str, bfs(V))))

아이디어 & 풀이

진행은 위의 풀이와 동일하다.

edge를 생성할 때 딕셔너리가 아니라 미리 초기화한 이차원 리스트를 사용해서 값을 집어넣는 과정을 간소화했다.

스택이나 큐에 인접 노드(edge[n])를 추가할 때 과정이 조금 다르다.

인접 노드가 정렬되어있어야 하는데
- 위의 풀이에서는 추가할 때마다 추가할 인접 노드를 정렬했고,
- 해당 풀이에서는 edge 입력을 받자마자 edge의 모든 원소를 순회하면서 리스트를 정렬했다.
이미 방문한 인접 노드는 다시 방문하지 않아야 하므로 visited에 추가하지 않고 거르는 장치가 필요하다.
- 위의 풀이에서는 추가하기 전에 인접 노드 후보(temp)에서 visited 안에 있는 원소를 제외해 애초에 스택이나 큐에 추가되지 않게 했고
- 해당 풀이에서는 스택에는 그대로 추가하되 스택에서 pop 한 원소를 visited에 추가하기 전에 방문했는지(checked)를 검사한다.
  - bfs에서는 동일하게 큐에 추가하기 전에 검사했다.

큐에서 pop 할 때, 가장 앞의 원소를 pop 해야 하기 때문에 시간이 오래 걸리는데 큐를 역순으로 유지해 이를 방지했다.

큐를 역순으로 유지해 pop(0)나 popleft()를 사용하지 않고 pop()으로 원하는 원소를 pop 한다.
큐에 원소를 집어넣을 때는 appendleft를 사용하지 않고 해당 원소(i.e., i)를 리스트로 만들어 리스트의 덧셈([i] + queue)을 이용했다.
pop 되는 수가 작은 수부터 나오게 하기 위해서는 edge[n]의 값을 오름차순으로 순회하면서 queue 앞에 더해가야 하는데 현재 edge[n]는 오름차순으로 정렬되어있어 edge[n]을 역순으로 순회한다.

참고로 popleft를 사용하면 속도는 좀 느려지지만 코드는 dfs와 가장 유사하게 작성할 수 있다.

def dfs(root):
    stack = [root]
    visited = []
    checked = [0 for _ in range(N + 1)]

    while stack:
        n = stack.pop()
        if not checked[n]:
            checked[n] = 1
            visited.append(n)
            stack += edge[n]
            
    return visited


def bfs(root):
    queue = deque([root])
    visited = []
    checked = [0 for _ in range(N + 1)]

    while queue:
        n = queue.popleft()
        if not checked[n]:
            checked[n] = 1
            visited.append(n)
            queue += reversed(edge[n])

    return visited