문제 바로가기
문제 풀이
그래프는 노드와 간선으로 이루어져있으며 서로 연결된 노드의 그룹 수를 출력하는 문제.
개념 자체가 어려워서 찾아보면서 문제 풀이 진행
dfs와 bfs 중 bfs의 개념 이해 (한 노드에 연결된 노드를 우선적으로 탐색)
visited와 link list를 잘 활용할 줄 알아야함.
시간 초과 문제가 있을 수 있기 때문에 import sys, deque를 import해서 input(), popleft()를 사용 -> 시간을 단축시킬 수 있다.
정답 코드
"""
https://www.acmicpc.net/problem/11724
"""
from collections import deque
import sys # 시간초과 발생
input = sys.stdin.readline
def bfs(start, edges, visited): # bfs 정의
q = deque([start])
visited[start] = True
while q: # q가 존재하지 않으면 탐색이 완료된 것으로 반복문 종료
now = q.popleft()
for e in edges[now]: # e와 연결된 node는 모두 탐색
if not visited[e]:
q.append(e) # 방문하지 않았던 곳이면 해당 node와 연결된 다른 node도 순회하기 위해 q에 append
visited[e] = True
N,M = map(int, input().split())
edges = [[] for _ in range(N + 1)] # n+1개의 빈 list 정의 (node번호와 idx를 같게하기위해 N+1까지 반복)
for _ in range(M): # node와 연결된 node를 정리한 list
node1, node2 = map(int, input().split())
edges[node1].append(node2)
edges[node2].append(node1)
# node1와 node2는 서로 연결되어 있음을 의미
result = 0
visited = [False] * (N + 1) # 방문 여부를 확인하는 list 생성
for i in range(1, N + 1):
if not visited[i]: # 서로 연결되지 않은 node의 수를 찾는다.
result += 1 # 연결되지 않았을 때 1씩 추가
bfs(i, edges, visited)
print(result)추가적인 개념 (optional)
자료구조의 그래프
단순히 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료 구조로 그래프 중 일부에 트리가 속한다.
정점(node) : 위치라는 개념
간선(edge) : 노드 간의 관계. 노드를 연결하는 선 (link라고도 부름)
노드와 간선 참고
트리 구조 탐색 시 DFS, BFS의 개념을 이해하고, 이를 구현할 줄 알아야 함.
n, m = map(int, input().split()) edges = [[] for _ in range(n + 1)] # 간선을 의미 visited = [False] * (n + 1) # 방문 여부 확인 def bfs(v, edges, visited): q = deque([v]) visited[v] = True while q: # q가 존재할 때만 now = q.popleft() # 왼쪽부터 차례로 방문 for e in edges[now]: # 여기가 이해가 안가네 if not visited[e]: # False라면 q.append(e) visited[e] = True # 방문처리
dfs 개념 추가할 것
