11724번 연결 요소의 개수 - https://www.acmicpc.net/problem/11724
Python으로 제출하면 시간 초과 / PyPy3로 제출하면 통과 (메모리 197904KB / 시간 868ms)
접근 방법
- BFS로 품 ( queue 사용)
- 2644번 촌수계산 문제와 마찬가지로 중첩 리스트로 graph를 만들어주고 visited list를 활용하여 queue에 넣어준다.
- sum(visited list) 가 N이 되면 모두 방문했다는 뜻으로 멈춰준다.
from collections import deque
def bfs(graph, N):
visited = [0] * N
count = 0
while sum(visited) != N:
queue = deque([visited.index(0)+1])
visited[visited.index(0)] = 1
while queue:
node = queue.popleft()
for i in graph[node]:
if visited[i-1] == 0:
queue.append(i)
visited[i-1] = 1
count+=1
return count
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for i in range(M):
node1, node2 = map(int, input().split())
graph[node1].append(node2)
graph[node2].append(node1)
print(bfs(graph, N))
다른 사람의 풀이
- 시간초과를 없애기 위해서 input() 함수 대신 readline을 사용 가능
- visited list를 함수에서 선언하지 않고 미리 선언한 후에 반복문을 돌면서 방문하지 않았다면
bfs 함수를 돌리는 방법도 있음
for i in range(1, N+1): if visited[i] == 1: bfs(i) cnt += 1
'study > 알고리즘' 카테고리의 다른 글
[알고리즘/프로그래머스] 튜플 (0) | 2021.12.16 |
---|---|
[알고리즘/프로그래머스] 숫자 문자열과 영단어 (0) | 2021.12.13 |
[알고리즘/백준] 2644번 촌수계산 (0) | 2021.12.09 |
[알고리즘] 다이나믹 프로그래밍(LIS) - 병사 배치하기 (0) | 2021.12.08 |
[알고리즘] 다이나믹 프로그래밍(동적 계획법) - 2 (0) | 2021.12.07 |