[백준] 11724번 연결 요소의 개수 파이썬

깊이 우선 탐색 DFS 유형의 문제를 선택했다.

DFS 개념은 방향 없는 그래프를 기본으로 하여 설명되곤 하는데 본 개념을 그대로 문제로 나타낸 것이다.

정점 N개와 간선 M개가 주어지고 M개의 줄에 간선 양 끝점인 u와 v가 주어지는데 이때 연결되는 요소의 개수를 구해야 한다.

 

11724번 연결 요소의 개수 풀이

[시도1] 맞았습니다!! with 솔루션

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
cnt = 0

# graph 채우기
for _ in range(m):
  u, v = map(int, input().split())
  # 방향이 없으므로 두 개 모두 추가
  graph[u].append(v)
  graph[v].append(u)

# 방문 확인을 위한 배열
visited = [False]*(n+1)

def dfs(v):
  visited[v] = True # 현재 위치 방문으로 바꾸기
  for i in graph[v]: # 연결된 정점 확인
    if visited[i] == False: # 연결된 정점이 아직 방문 전이라면, 
      dfs(i) # 해당 정점에 연결된 다른 정점들도 확인 (재귀적)

for i in range(1, len(visited)):
  if visited[i] == False: # 방문하지 않은 정점
    dfs(i) # 탐색
    cnt += 1 

print(cnt)

graph에 m개의 입력받은 간선의 정보를 넣어줘야 한다. 간선의 양 끝 점 u와 v 값이 있는데 방향이 없는 그래프이므로 graph 배열의 u인덱스, v인덱스 모두에 연결된 점 u와 v를 넣어줘야 한다. 그리고 정점 사이에 연결이 되어 있는지를 확인하기 위한 visited 배열을 False로 초기화하여 생성한다.  graph와 visited 모두 0 인덱스는 의미를 갖지 않는다. 

dfs 함수를 사용해서 현 정점 값(v)을 입력 받으면 방문(True) 처리를 하고 gaph[v]로 연결된 정점들을 하나씩(visited[i]) 방문했었는지 하지 않았었는지 확인한다. 방문하지 않았던 정점(False)이면 해당 정점도 탐색(dfs(i))하도록 하고 연결 요소 카운트를 1 더한다.  

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수