[Python] 백준, 2606(DFS/BFS)

https://www.acmicpc.net/problem/2606

2606번: 바이러스

전형적인 DFS/BFS 문제는 풀기 좀 쉽다고 들었는데, 무슨 의미인지 알 것 같다. 

 

 

 

# PYTHON CODE (1) - BFS

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

tree = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    tree[a] += [b]
    tree[b] += [a]

queue = [1]
cnt = 0
visit = [False] * (n + 1)

while queue:
    x = queue[0]
    del queue[0]

    if not visit[x]:
        visit[x] = True
        cnt += 1
        for i in tree[x]:
            queue.append(i)

print(cnt - 1)

앞에서 살펴본 두 문제와는 주어진 자료의 형태가 살짝 다른데, 오히려 트리 처음 공부할 때 봤던 자료 형태와 유사한 것 같다. 아직 몇 문제 안 풀긴 했는데, 다행히 골격 자체는 이해한 것 같아서 자료구조의 처리나 미세한 조절 같은 것들만 신경 써주면 되는 수준으로 다가온다.

 

 

# PYTHON CODE (2) 

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

tree = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    tree[a] += [b]
    tree[b] += [a]

visit = [False] * (n + 1)
cnt = 0

def dfs(x):
    global cnt
    if not visit[x]:
        visit[x] = True
        cnt += 1
        for i in tree[x]:
            dfs(i)
    return cnt

print(dfs(1) - 1)

 

 

P.S - 1일 1문제가 목표긴 한데 12시 넘어서 올리게 되면 공백이 생기는 게 좀 아쉽다는 핑계를 슬쩍 얹어본다.