[백준 11724번] 연결 요소의 개수 - python

문제 링크

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

11724번: 연결 요소의 개수

풀이

- bfs 문제는 간선이 주어진 유형과 그래프가 주어진 유형으로 구분할 수 있는데 

간선이 주어진 경우에는 본 문제처럼 0부터 n-1 까지 자기 자신과 연결된 노드를 찾는다.

from collections import deque 
import sys
input = sys.stdin.readline 

q = deque()

def bfs(i):
  visited[i] = True

  q.append(i)

  while q:
    x = q.popleft()
    
    # 0부터 n까지의 정점 중 자신과 연결되어 있고 방문하지 않았으면 방문표시를 하고 큐에 추가 
    for k in range(n):
      if graph[x][k] == 1 and not visited[k] :
        visited[k] = True
        q.append(k)
    
n, m = map(int,input().split())

graph = [ [0] * n for _ in range(n)]

# 연결 표시 
for _ in range(m):
  a, b = map(int,input().split())
  graph[a-1][b-1] = 1
  graph[b-1][a-1] = 1 

# 방문 했는지 표시 
visited = [False] * n
# 간선의 개수 
cnt = 0 

# 모든 정점에 대해 
for i in range(n):
  # 방문하지 않았으면 bfs 실행하여 연결된 노드를 찾아 방문 표시를 한다. 
  if not visited[i] :
    bfs(i)
    cnt += 1 

print(cnt)

그래프가 주어진 경우에는 nx = [ 1, -1 , 0, 0 ] ny = [ 0, 0, 1, -1 ] 과 같이 이동할 수 있는 방향을 저장해주고 각 방향에 대해 이동해가면서 연결된 노드를 찾는다. 

대표적인 문제를 아래와 같다. 

https://zzion2.tistory.com/145

[백준 1012번] 유기농 배추 - python