[BOJ] 2606번 - 바이러스

문제는 다음과 같다.

 

🚦 문제 유형

- Graph Traversal (그래프 탐색)

- DFS/BFS

 

✏️ Solution

DFS/BFS 문제로, DFS를 이용해 풀었다.

n = int(input())
m = int(input())

# 연결된 그래프 리스트 만들기
graph = []
for i in range(n+1):
    graph.append([])

for i in range(m):
    f, s = map(int, input().split(' '))
    graph[f].append(s)
    graph[s].append(f)

visit = [False] * (n+1)

# dfs
def dfs(start, graph, visit):
    visit[start] = True
    for i in graph[start]:
        if visit[i] == False:
            dfs(i, graph, visit)
    return visit

visit = dfs(1, graph, visit)
result = visit.count(True) - 1
print(result)

 

⚙️ Review

처음엔 DFS를 되짚어보며 코드를 작성했다.

처음 푸는 백준의 DFS/BFS 문제였지만 나름 잘 기억했다. 하지만 코드에서 딱 한 줄 때문에 한번에 정답이 되진 않았다.

잊지말고 다시 한번 기억할 것!

- 그래프 리스트를 만들 때 상호 연결을 구현했는지 확인하자.

- DFS 를 구현할 때 방문했는지를 까먹지 말자.