[Algorithm] 백준 BOJ 2606 바이러스 python 파이썬 그래프 실버 3

Private 난이도 : ♥♥♥♡♡

2606번: 바이러스

import sys

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

graph = dict()
for i in range(n):
    graph[i+1]=[]
for i in range(m):
    a,b=map(int, sys.stdin.readline().strip().split())
    graph[a].append(b)
    graph[b].append(a)

print(graph)
visited = [False] * (n+1)
result = 0

def dfs(v, visited):
    global result
    print('dfs',v,'시작')
    if visited[v] == True:
        return
    visited[v] = True

    for i in graph[v]:
        print('i',i)
        if visited[i]==False:
            result +=1
            dfs(i, visited)
    print('dfs', v, '끝')

dfs(1, visited)
print(result)

설명이 추가된 것이다. 원래 버전은 여기있다.

 

설명

• 첫 DFS 문제여서 좀 시간이 오래걸렸다.
• graph를 리스트로 두면 큰 수를 가진 노드에서  거꾸로 올 때 자꾸 에러가 나서 dict형으로 만들었다. 그 전에 [1,2]가 들어오면 [2,1]도 추가되도록 만들었는데 그렇게 하니까 n이 달라지고 커져서 하지않았다.
• 노드 안의 수를 그대로 쓰기 위해서 0을 사용하지 않았다. graph도 마찬가지이다.
• result 변수를 함수의 인자로 넣지 않고 싶어서 global을 사용했는데 이럴 때 쓰는게 맞는지 잘 모르겠다.
• dfs함수의 맨 처음에 탈출 조건 적는게 국룰인 것 같다.

배운 점

• visited=[]로 방문시마다 append해도 되지만 그렇게 되면 있는지 확인할 때 is in을 사용하는게 O(n)시간이 추가되어서 True,False로 확인하는 것이 낫다고 한다.