백준 2606 바이러스

❌ 백준 2606 바이러스

오답.

com_dict : 연결관계를 표현한 딕셔너리
visited : 방문한 노드 배열
mustgo : 방문해야하는 노드 배열

기본적인 흐름
:
방문순서 상관없이 횟수만 구하면 되기 때문에, 코드짜기는 쉬웠다.

1) 1부터 시작한다.

2) 1에 연결된 노드들을 전부 mustgo 배열에 넣는다.

3) mustgo가 바닥날 때까지 while문을 돌린다.

4) mustgo에서 노드 하나를 pop해서 방문한다.

5) result값에 1을 더해준다.

6) 방문한 노드를 visited에 넣고, 그 노드와 연결된 모든 노드를 mustgo로 넣는다.위에도 서술했지만, 방문 순서는 상관없다. pop을 하든 popleft를 하든 자유다.
(여기서 mustgo에 넣을 노드는 visited에 존재하지 않아야 한다)

처음엔 양방향을 생각못하고, 그냥 왼쪽값이 1인 경우만 고려했다. 근데 첫번째로 제출한 답이 틀려서, 반례를 찾다보니 양방향도 생각해줘야했다.

1 2
2 3
3 4
5 6
6 7
7 8
8 1

예를 들어, 이런 케이스가 들어오면 1에 연결된 8은 인식을 못했다.

양방향으로 들어오게 고치고, 중복도 제거해준 다음 제출을 했다.
또 틀렸다.

뭐가 틀린지 한참을 찾다가, 입력 예시를 넣어보니 다른 값이 나왔다.

알고보니 새로운 노드를 mustgo에 넣을 때 visited뿐만 아니라 mustgo에도 겹치는 노드가 없었어야 했다.

몇번이나 틀리긴 했지만, 이 풀이를 스스로 생각해내서 뿌듯했다.

import sys

x = int(sys.stdin.readline())
y = int(sys.stdin.readline())

com_dict = {}
visited = []
mustgo = []
result = 0

for i in range(y) :
    a,b = map(int,sys.stdin.readline().rstrip().split())
    if a in com_dict :
        if b not in com_dict[a]:
            com_dict[a].append(b)
    else :
        com_dict[a] = [b]

    if b in com_dict :
        if a not in com_dict[b]:
            com_dict[b].append(a)
    else :
        com_dict[b] = [a]


if 1 not in com_dict :
    print(0)
    quit()

for i in range(len(com_dict[1])) :
    mustgo.append(com_dict[1].pop())

visited.append(1)
del com_dict[1]

while len(mustgo) > 0 :
    nowAt = mustgo.pop()
    visited.append(nowAt)
    result += 1
    if nowAt in com_dict :
        for i in range(len(com_dict[nowAt])) :
            inNowAt = com_dict[nowAt].pop()
            if inNowAt not in visited and inNowAt not in mustgo:
                mustgo.append(inNowAt)

print(result)