[구름 LEVEL] 퍼져나가는 소문
문제 설명
· N명의 친구가 있고, 친구 간 M쌍의 친구 관계가 있을 때, 1번 친구와 연결된 친구의 수를 찾기
접근 방법
· N개의 노드에서 M개의 간선이 주어질 때, 1번 노드와 연결된 노드의 개수를 찾기
· 입력으로 들어오는 친구 관계를 인접 리스트로 구현한 뒤, 1번 노드와 연결된 노드 탐색
· 탐색 알고리즘은 DFS가 BFS보다 메모리를 적게 사용하므로 DFS 선택
알고리즘 설계 및 구현
N = int(input()) # 노드의 개수 입력
M = int(input()) # 간선의 개수 입력
# 그래프를 인접 리스트로 초기화
graph = [[] for _ in range(N + 1)]
# 간선 정보 입력받기
for _ in range(M):
a, b = map(int, input().split())
graph[a].append(b) # 노드 a에서 b로 가는 간선 추가
graph[b].append(a) # 노드 b에서 a로 가는 간선 추가 (양방향 그래프)
visited = set() # 방문한 노드를 저장할 집합
stack = [1] # DFS를 위한 스택, 시작 노드를 1로 설정
count = 0 # 방문한 노드의 개수
# 스택이 빌 때까지 반복
while stack:
current = stack.pop() # 스택에서 현재 노드를 꺼냄
if current not in visited: # 현재 노드가 방문되지 않았다면
count += 1 # 방문한 노드 개수 증가
visited.add(current) # 현재 노드를 방문한 것으로 표시
for c in graph[current]: # 현재 노드와 인접한 모든 노드에 대해
if c not in visited: # 인접한 노드가 방문되지 않았다면
stack.append(c) # 스택에 추가
print(count) # 방문한 노드의 총 개수 출력결과
최적화 및 개선 방안
visited = set()
visited = [False] * (N + 1)· visited를 set으로 선언하였는데, 노드의 개수가 많지 않으므로 노드 번호를 인덱스로 하고 방문 여부에 따라 Bool 형태를 가지는 형태로 변경한다면, 리스트 인덱스를 통해 접근하여 O(1)의 시간복잡도로 줄일 수 있다.
