백준 1325번: 효율적인 해킹 - Python

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

난이도 - 실버1 🥈

알고리즘 분류: bfs

🧐 문제접근

먼저 python으로 푼 이유는, 무슨짓을 해도 swift로는 제한시간내에 풀이가 불가능하더라구요.
아마도 입력때문이 아닐까 생각합니다. 파이썬으로 했어도 로직은 동일합니다.

그래프의 모든 정점에 대해 bfs 탐색을 해서, 연결되어있는 노드가 가장 많은 정점들을 오름차순으로 출력하는 문제입니다.

먼저, 위 방법대로 완전탐색을 해도 문제가 없을까요?

정점의 개수 N = 10^4, 간선의 개수 M = 10^5 입니다.
bfs의 시간복잡도는 O(N+M)이고 총 N번 반복할것이므로 O(N(N+M)) 최악의 경우에 약 10^9 번 정도의 연산이 있겠군요.
아슬아슬하긴 한데, 시간제한도 5초이고, 여기서 간선은 모두 단방향 간선이므로 실제 시간복잡도는 저것보다 훨씬 낮다고 기대해 볼 수 있겠네요.

일단 한번 시작해 보겠습니다.

코드

1. bfs 탐색

모든 정점에 대해 bfs탐색을 하는데, 총 개수를 세야 하므로, queue에 새로운 원소가 추가될때마다 cnt + 1 을 해주고, 최종적으로 해당값을 return 해 줍니다.

def bfs(start):
	cnt = 1
	queue = deque([start])
	visit = [False for _ in range(n+1)]
	visit[start] = True

	while queue:
		cur = queue.popleft()

		for nx in graph[cur]:
			if not visit[nx]:
				visit[nx] = True
				cnt += 1
				queue.append(nx)

	return cnt

2. 최대값들만 모으기

1부터 n까지 반복하면서,
현재 노드와 연결된 개수들을 cnt에 저장합니다.

현재 노드의 연결개수 > 기존 최대값:
이면 최대값을 갱신하고, ans을 초기화 하고, ans에 추가합니다

현재 노드의 연결개수 = 기존 최대값:
이면 ans에 추가합니다

이렇게 하면, 최대의 값을 가지는 것들이 오름차순 순으로 ans에 들어가게 됩니다

maxCnt = 1
ans = []

for i in range(1,n+1):
	cnt = bfs(i)
	if cnt > maxCnt:
		maxCnt = cnt
		ans.clear()
		ans.append(i)
	elif cnt == maxCnt:
		ans.append(i)

전체코드

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

n,m = map(int,input().split())

def bfs(start):
	cnt = 1
	queue = deque([start])
	visit = [False for _ in range(n+1)]
	visit[start] = True

	while queue:
		cur = queue.popleft()

		for nx in graph[cur]:
			if not visit[nx]:
				visit[nx] = True
				cnt += 1
				queue.append(nx)

	return cnt

graph = [[] for _ in range(n+1)]

for _ in range(m):
	a,b = map(int,input().split())
	graph[b].append(a)

maxCnt = 1
ans = []

for i in range(1,n+1):
	cnt = bfs(i)
	if cnt > maxCnt:
		maxCnt = cnt
		ans.clear()
		ans.append(i)
	elif cnt == maxCnt:
		ans.append(i)

print(*ans)

한줄평가: 무난한 문제였지만, swift로는 못풉니다.. ㅎㅎ