11724-연결 요소의 개수

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

11724번: 연결 요소의 개수

DFS와 BFS를 둘 다 연습해볼 수 있는 문제이다. 간단한게 DFS와 BFS의 풀이방식을 살펴보면

- DFS(깊이 우선 탐색): 스택 or 재귀를 사용해서 구현

- BFS(너비 우선 탐색): 큐를 사용해서 구현

 

나는 보통 DFS에서 재귀를 사용해서 구현하는데 파이썬의 경우 최대 재귀 횟수가 1000번으로 고정되어 있기 때문에 대부분의 문제를 풀때는 이 제한범위를 늘려주어야 한다. sys.setrecursionlimit() 함수를 사용해 주면 된다. (sys import는 필수!)

# DFS 버전
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, M = map(int, input().split())
field = [[False] * 1001 for _ in range(1001)]
for _ in range(M):
    x, y = map(int, input().split())
    field[x][y] = True
    field[y][x] = True

chk =  [False]* 1001

def dfs(start):
    #chk[start] = True
    for nxt in range(1, 1001):
        if field[start][nxt] and chk[nxt] == False:
            chk[nxt] = True
            dfs(nxt);

ans = 0
for i in range(1, N+1):
    if chk[i] == False:
        ans+=1
        chk[i] = True
        dfs(i)
print(ans)

 

BFS의 경우 큐를 사용해야 하는데 파이썬의 경우 일반 큐보다 덱을 사용하는게 더 빠르다. 이는 우선순위 큐 대신 heapq를 사용하는 이유와 같다.

2022.04.22 - [ALGORITHM/Data Structure] - [Python] min-hip을 이용한 Priority Queue

[Python] min-hip을 이용한 Priority Queue

빠를수록 나쁠건 없으니까 문제풀이의 경우 덱을 계속해서 사용할 예정이다.

# BFS 버전
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
field = [[False] * 1001 for _ in range(1001)]
for _ in range(M):
    x, y = map(int, input().split())
    field[x][y] = True
    field[y][x] = True

chk =  [False]* 1001

def bfs(start):
    dq = deque()
    dq.append(start)
    while dq:
        now  = dq.popleft()
        if chk[now]:
            continue
        else:
            chk[now] = True
            for nxt in range(1, 1001):
                if field[now][nxt]:
                    dq.append(nxt)
ans = 0
for i in range(1, N+1):
    if chk[i] == False:
        ans += 1
        bfs(i)

print(ans)