[CodingTest] 백준 2606번 바이러스

문제

내 풀이

num_com = int(input())
num_direct = int(input())

connect_ls = []
for i in range(num_direct):
    a = input().split()
    a[0] = int(a[0])
    a[1] = int(a[1])
    connect_ls.append(a)
    
adjacency_ls = [[] for i in range(num_com+1)]

for i in range(1, len(connect_ls)+1, 1):
    for j in connect_ls:
        if j[1] not in adjacency_ls[j[0]]:
            adjacency_ls[j[0]].append(j[1])
        
        if j[0] not in adjacency_ls[j[1]]:
            adjacency_ls[j[1]].append(j[0])
            
            
stack = [1]
visited_com = []

while stack:
    current = stack.pop()
    for neighbor in adjacency_ls[current]:
        if not neighbor in visited_com and not neighbor in stack:
            stack.append(neighbor)
    visited_com.append(current)

print(len(visited_com) - 1)

dfs를 활용해 풀어본 첫번째 문제이다. 공부했던 graph는 cycle이 없는 구조였는데, cycle이 있는 그래프 문제라 당황했다. stack에 넣어줄 때 이미 stack에 있으면 넣지 않는다라는 조건(=not neighbor in stack)을 추가해서 해결했다. 그 과정에서 dfs를 이용해서 그래프에 cycle이 있는지도 발견할 수 있다는 점을 알게 되었다.