728x90
그래프 탐색 문제로
dfs, bfs 둘다 사용이 가능하여 다양한 풀이가 가능한 문제다.
DFS: dictionary(인접리스트), 재귀 사용
n = int(input()) # 컴퓨터의 수 (1~100 정수)
m = int(input()) # 직접 연결되어있는 컴퓨터 쌍의 수
graph = {i: [] for i in range(1, 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 = [False] * (n + 1) # 방문 여부를 저장하는 배열 초기화
def dfs(graph, start, visited):
visited[start] = True # 시작 노드를 방문했음을 표시
count = 1 # 연결된 컴퓨터의 수를 세기 위한 변수 초기화
for neighbor in graph[start]: # 시작 노드와 연결된 모든 이웃 노드에 대해
if not visited[neighbor]: # 이웃 노드를 방문하지 않았다면
count += dfs(graph, neighbor, visited) # 이웃 노드로 재귀적으로 방문
return count # 현재 연결된 컴퓨터의 수 반환DFS에서 dictionary를 활용하여 구현한 코드이다.
graph를 사전 자료형으로 표현하는 경우,
각 컴퓨터 번호를 key로 가지고 연결된 다른 컴퓨터들을 value로 가지게 된다.
graph[a].append(b) # a와 b를 연결하여 그래프에 추가
graph[b].append(a) # b와 a를 연결하여 그래프에 추가
위와 같이 서로 추가해주어 두 컴퓨터 간 연결 관계를 표현할 수 있다.
728x90
