[백준/2606] 바이러스 | 양방향 그래프 정의 | DFS

바이러스

Baekjoon Online Judge

 

 

---

알고리즘

입력에서 직접 연결되어 있는 쌍이 주어진다.

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

 

1번 노드는 2번 노드와, 2번 노드는 3번 노드와 1번 노드는 5번 노드와 ∙∙∙ 연결되어있다는 뜻이다.

이렇게 정의하는 그래프를 양방향 그래프라고 하고, 다음과 같이 코드로 구현할 수 있다.

 

• 양방향 그래프를 2차원 리스트로 정의

graph = [[] for _ in range(n+1)]

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

 

 

• 인접노드를 방문할 때마다(재귀의 한 사이클이 끊기지 않을 때) 카운팅 하기
  • 카운팅 횟수를 재귀함수 호출 및 반환 마다 공유 하면서 값이 연결되도록 해야 한다.
  • 즉, 재귀가 return될 때마다 카운트 횟수를 쌓아줘야 함 return cnt,
  • 호출 누적을 위한 cnt = dfs(i, cnt+1)

def dfs(x, cnt):
    visited[x] = True
    for i in graph[x]:
        if not visited[i]:
            cnt = dfs(i, cnt+1)
    return cnt

 

---

전체 코드

import sys;input=sys.stdin.readline
sys.setrecursionlimit(2000)

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

visited = [False for _ in range(n+1)]
graph = [[] for _ in range(n+1)]
cnt = 0

for _ in range(m):
    x, y = map(int, input().rsplit())
    graph[x].append(y)
    graph[y].append(x)

# 인접 노드 방문
def dfs(x, cnt):
    visited[x] = True
    for i in graph[x]:
        if not visited[i]:
            cnt = dfs(i, cnt+1)
    return cnt

print(dfs(1, 0))