• TOC {:toc}

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

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

2021.07.03 (Python)

메모리 시간 코드 길이
29200 KB 72 ms 394 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 14:43:43 14:45:37
풀이 생각 14:45:38 14:45:49
코딩 14:55:00 15:03:21
디버깅 15:04:32 15:13:25 
import sys
input = sys.stdin.readline

N = int(input())

net = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
count = 0

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

queue = [1]
while queue:
    n = queue.pop()
    if not visited[n]:
        visited[n] = True
        count += 1
        queue += net[n]

print(count - 1)

아이디어 & 풀이

dfs나 bfs로 그래프를 탐색하면서 count를 높인 뒤 출력한다.

  • dfs를 이용했다.

디버그

  • queue에서 원소를 pop 할 때마다 count를 올렸더니 값이 너무 크게 나왔다. net[n]에 이미 방문한 곳도 포함되어 있어서 queue는 중복 원소도 포함하기 때문에 그런 듯.
    • not visited 조건 안쪽에서 count를 증가시키고
    • 1번 컴퓨터는 개수에서 제외해야 하므로 마지막에 count - 1을 출력한다.

피드백

  • count를 따로 관리하는 대신 visited를 True/False가 아닌 0/1로 구성해 visited의 합을 구해도 된다.

2022.04.05 (JS)

메모리 시간 코드 길이
9452 KB 120 ms 792 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 22:56:08 23:00:33
풀이 생각 23:00:47 23:01:14
코딩 23:01:15 23:22:01 
const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [N, E, ...lines] = input;
const edges = Array(E + 1);

lines.forEach((line) => {
    const [A, B] = line.split(" ").map((n) => parseInt(n));
    if (!edges[A]) edges[A] = [B];
    else edges[A].push(B);
    if (!edges[B]) edges[B] = [A];
    else edges[B].push(A);
});

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

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

        edges[n].forEach((m) => {
            if (!visited[m]) {
                visited[m] = true;
                queue.push(m);
            }
        });
    }

    return visited.filter((e) => e === true).length - 1;
}

console.log(bfs());

참고 답안

import sys
input = sys.stdin.readline

def dfs(n):
    global visited

    visited.append(n)
    for x in net[n]:
        if x not in visited:
            dfs(x)


net = [[] for _ in range(int(input()) + 1)]
for _ in range(int(input())):
    a, b = map(int, input().split())
    net[a].append(b)
    net[b].append(a)

visited = []
dfs(1)

print(len(visited) - 1)

아이디어 & 풀이

위의 풀이와 동일하게 dfs를 이용했다.

  • count를 별도로 관리하지 않고 방문한 노드를 visited에 추가한 뒤 visited의 길이를 출력한다.
  • 방문 여부는 x not in visited로 확인한다.
  • queue 대신 재귀를 이용해서 dfs를 구현했다.