DFS/BFS: 백준 2606 파이썬

문제:

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

2606번: 바이러스

풀이:

DFS

com = int(input())
vertex = int(input())

array = [[] for _ in range(com+1)]
result = 0
visited = [False]*(com+1)

for _ in range(vertex):
    x, y = map(int, input().split())
    array[x].append(y)
    array[y].append(x)


def dfs(i):
    global result
    result += 1
    # 현재 노드를 방문처리
    visited[i] = True
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for j in array[i]:
        if not visited[j]:
            dfs(j)


# 정의된 DFS 함수 호출
dfs(1)
print(result-1)

 

BFS

from collections import deque

com = int(input())
vertex = int(input())

array = [[] for _ in range(com+1)]
result = 0
visited = [False] * (com+1)

for i in range(vertex):
    x, y = map(int, input().split())
    array[x].append(y)
    array[y].append(x)


def bfs(i):
    global result
    queue = deque([i])
    visited[i] = True
    while queue:
        v = queue.popleft()
        for i in array[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                result += 1


bfs(1)
print(result)

 

반성:

아쉽게도 이 문제도 이틀 정도의 시간 동안 해결하지 못해 구글링을 했다. 구글링을 통해 얻는 정보는 입력받은 숫자 

쌍을 노드가 연결된 정보를 나타내는 리스트로 바꾸어주는 방법이다. 이렇게 바꾸어 주면 DFS와 BFS를 사용하기에 아주 쉬웠다. 이번에 알게 된 방법을 잘 숙지해서 다른 문제 해결에 사용하도록 해야겠다.