[백준] 11724.연결 요소의 개수

jeongjeong2·2023년 5월 3일
0

For coding test

목록 보기
42/59

문제 바로가기

문제 풀이

그래프는 노드와 간선으로 이루어져있으며 서로 연결된 노드의 그룹 수를 출력하는 문제.
개념 자체가 어려워서 찾아보면서 문제 풀이 진행
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 개념 추가할 것

0개의 댓글