백준 2606 바이러스 - DFS 그래프 순회

2606번: 바이러스 (acmicpc.net)

2606번: 바이러스

두 번째 DFS 문제였다..

저번 DFS와 BFS문제를 잘 이해했어야만 풀 수 있는 문제

N = int(input())
M = int(input())
graph = [[] * N for _ in range(N + 1)]
visited = [False] * (N + 1)
for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
result = 0
def dfs(start):
    visited[start] = True
    global result
    result += 1
    for i in graph[start]:
        if not visited[i]:
            dfs(i)
            visited[start] = True
dfs(1)
print(result - 1)

사실 이 문제는 DFS와 BFS문제와 다를 것이 result += 1해주는 것밖엔 없었다. 그만큼 dfs의 기본형태를 잘 알고있다면 풀 수 있는 문제. 

우선 간선끼리 연결된 노드를 만드려면 그래프를 채우는 것이 필요하다

이 문제에 나와 있는 예제처럼

이렇게 연결된 그래프를 만드려면

  0     1    2    3      4    5      6    7

		V			V
	V		V		V
		V
							V
	V	V				V
					V
				V

이런 식으로 되어야함. 그러려면 간선의 개수 M만큼 for문을 돌리면서 graph[a], graph[b]에 b,a를 append하면서 교차해서 채워줘야 하고

DFS문을 돌리면서 graph[인덱스]문을 for문으로 돌면서 방문했던 곳을 True로 바꿔주면서 아래로 탐색해나가야 한다.

이것은 정말 기본형태의 스테레오타입인 것임. 그냥 외우자.