[CodeTree/Python] 연결된 그래프

문제

연결된 그래프

그래프의 연결된 두 노드들이 여러 개 주어졌을 때, 1번 노드와 연결된 모든 노드의 개수를 출력하는 프로그램을 작성해보세요.

 

입력 형식

첫 번째 줄에는 노드의 총 개수 n와 연결된 노드 쌍의 개수 m이 공백을 사이에 두고 주어집니다.

두 번째 줄부터 m개의 줄에 걸쳐 연결된 두 노드의 번호가 공백을 두고 한 줄에 하나씩 주어집니다.

• 1 ≤ m ≤ n ≤ 100

출력 형식

1번 노드와 연결된 모든 노드의 개수를 출력합니다. 단, 자기 자신(1번 노드)은 제외합니다.

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

해결

 

1. 인접 리스트 생성

n, m = map(int, input().split())

# 노드의 총 개수가 n개 주어지므로, 행이 n + 1개인 인접 리스트 생성
# 노드가 1번부터 시작하므로, 계산의 용이성을 위해 1번 행부터 시작
li = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    li[a].append(b) # a번 노드와 b번 노드가 연결이므로, a번 행에 b값 추가
    li[b].append(a) # (해당 문제의 경우)양방향 연결이므로, b번 행에 a값 추가

* [[0번 노드와 연결되는 노드 전체], [1번 노드와 연결되는 노드 전체], ... , [k번 노드와 연결되는 노드 전체]] 형태의 리스트가 생성된다.

 

2-1. 스택을 사용하여 풀이하는 방법

# 방문 처리를 위한 리스트 생성(n + 1개: 노드 번호에 맞춤, default = False)
visit = [False] * (n + 1)
# 스택 생성: 1번 노드부터 시작하므로 스택에 추가
stack = [1]
count = 0 # 연결 노드 수

while stack:
    node = stack.pop() # 방문 노드(스택에서 원소를 제거하고, 그 값을 node 변수에 반환)
    if not visit[node]: 
        visit[node] = True # 방문 리스트가 False인 경우, 방문 처리
        for i in li[node]: # 방문 노드 내의 원소를 돌면서, 방문 확인
            if not visit[i]:
                # 방문 처리 안 된 노드인 경우, 스택에 해당 원소를 쌓음
                # 스택에서 노드가 다 빠질 때까지 반복문을 돌면서 방문 처리 및 확인
                stack.append(i) 
        if node != 1: # 현재 방문한 노드가 1번이 아니면, 연결 노드 수 1 추가
            count += 1 

print(count)

 

2-2. 재귀 함수를 사용하여 풀이하는 방법

# 방문 처리를 위한 리스트 생성
visit = [False] * (n + 1)

# 재귀 함수 생성
def dfs(node):
    visit[node] = True # 방문 처리
    for i in li[node]: # 노드행 내 원소(노드)를 돌면서 방문 확인
        if not visit[i]:
            dfs(i) # 미 방문 노드 시 재귀 함수 시행

dfs(1)
print(sum(visit) - 1) # 자기 자신을 제외