✔️ silver 1
그래프 이론
그래프 탐색
너비 우선 탐색
깊이 우선 탐색
문제 흐름
모든 노드에서 탐색했을 경우 가장 많은 노드를 탐색할 수 있는 노드를 찾는다.
BFS, DFS 모두 가능하지만 역시 BFS보다 DFS가 덜 익숙해서 DFS로 선택했다.
이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.
이렇게 명시되어 있는데, B를 해킹하면 A도 해킹할 수 있지만 A를 해킹한다고 B도 해킹할 수 있는 건 아니기 때문에 단방향 그래프로 저장해줘야 한다.
원래는 dfs 함수에 시작점 s를 받아 딱 DFS 탐색만 진행하도록 하려 했는데 매번 모든 노드를 돌면서 함수를 호출하면 함수호출하면서 시간이 더 걸릴 수도 있겠다 생각이 들었다.
그래서 모든 노드에 대해 반복하는 작업까지 함수에 포함시켜 한번만 호출되도록 했다.
한 노드를 시작점으로 탐색을 진행 할 때마다 결과(탐색 노드 수)를 현재 최대와 비교해 업데이트되도록 했다.
시작노드는 1부터 순서대로 들어가므로 정렬부분은 신경쓰지 않았다.
또 이 문제에 중요한 점이 있는데 바로 pypy3로 제출해야한다는 점이다.
이유는 모른다.... (??)
기본 python3로 제출하면 시간초과를 피할 수가 없다.
내 풀이도 python3로 제출하면 1%에서 멈춰있다가 냅다 시간초과가 뜬다.
코드
# 효율적인 해킹
# graph
import sys
input = sys.stdin.readline
def dfs(g: dict):
st = []
n = len(g)
max_value = 0
res = []
for s in range(1, n+1):
st.append(s)
vst = [0 for i in range(n+1)]
vst[s] = 1
tmp = 0
while st:
x = st.pop()
for u in g[x]:
if vst[u]:
continue
st.append(u)
vst[u] = 1
tmp += 1
if tmp > max_value:
max_value = tmp
res = [s]
elif tmp == max_value:
res.append(s)
return res
if __name__ == "__main__":
n, m = map(int, input().split())
g = {node: [] for node in range(1, n+1)}
for i in range(m):
a, b = map(int, input().split())
g[b].append(a)
result = dfs(g)
print(*result)마무리
사실 예전에도 이미 풀어본 적이 있는 문제다.
정답률도 18.85%로 극악인데, 예전에도 고생해서 기억에 남았다.
이번이나 그때나 pypy3로 제출해서 통과하긴 했는데 왜 안되는지는 여전히 구글링을 해도 잘 나오지 않았다.
"백준 1325"를 검색하면 유독 C++과 python이 자동완성으로 붙어 뜨던데 비슷한 문제를 겪는 경우가 많은 것 같다.
몇가지 풀이를 찾아봤는데 DFS 방식으로 풀었을 경우 메모리 초과가 발생해서 실패했다는 글들이 있었다.
메모리 초과인 DFS 풀이는 보통 재귀적 방법으로 구현되었는데 다른분의 통과한 DFS 풀이나 내 풀이는 비재귀적 방법으로 구현되어서 시간초과가 나지 않은 것 같다.
