[백준] 2606 - 바이러스

from collections import deque

n = int(input())
m = int(input())
com = {i:[] for i in range(1, n+1)}

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

def bfs(x):
    visit=[]
    que = deque()
    que.append(x)
    while que:
        x = que.popleft()
        visit.append(x)
        for i in com[x]:
            if i in visit:
                continue
            if i in que:
                continue
            que.append(i)
    print (len(visit)-1)

bfs(1)

• 풀이 평가 : 30분 넘게 소요해서 풀이 완료!
• 풀이 핵심 아이디어 :
  • 딕셔너리 사용해서 각 노드의 연결부를 모두 표시
    ⇒ com = {i:[] for i in range(1, n+1)} → com[x].append(y), com[y].append(x)
  • visit 함수로 방문기록 표시
• 풀면서 헷갈렸던 점 :
  • while 안에 for문 내부에서 (if 동반한) continue사용시 for문 내에서 무시되는지??
    ⇒ YES! for위 i가 continue되면 그 다음 i로 for문 내의 처음 문장으로 돌아감!
  • visit에도 없고 que에도 없는 놈들만 que에 넣어야 한다! 둘 다 if로 체크하기!