[BaekJoon] 백준 1325 효율적인 해킹
문제: https://www.acmicpc.net/problem/1325
내코드
관계로 엮여져 있고, 하나의 컴퓨터에서 시작해서 가장 많이 연결된 컴퓨터의 수를 구한다는 것에서
dfs로 풀어야겠다고 생각했다. 따지자면 방향성이 있는 그래프를 dfs로 탐색하는 문제다.
bfs로도 풀 수는 있겠지만 bfs는 최단 시간에 더 적합한 알고리즘이어서 dfs로 풀어봤다.
간단한 dfs 문제였지만 파이썬으로 푸니 시간초과가 나서 pypy로 채점했다.
# BaekJoon1325.py
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
relation = [[] for i in range(N)]
stack = []
result = [0 for i in range(N)]
# 신뢰 관계 저장 -> 인접 리스트
for _ in range(M):
a, b = map(int, input().split())
relation[b - 1].append(a - 1)
for i in range(N):
visited = [False] * N
stack.append(i)
visited[i] = True
# dfs
while stack:
value = stack.pop()
result[i] += 1
length = len(relation[value])
for j in range(length):
if not visited[relation[value][j]]:
stack.append(relation[value][j])
visited[relation[value][j]] = True
answer = []
max_value = max(result)
for i in range(N):
if result[i] == max_value:
print(i + 1, end=" ")
728x90
반응형
'CS > Algorithm 문제' 카테고리의 다른 글
[BaekJoon] 백준 14719 빗물 (0) | 2021.08.07 |
---|---|
[BaekJoon] 백준 1913번 달팽이 (0) | 2021.08.07 |
[BaekJoon] 백준 20444번 색종이와 가위 (0) | 2021.08.06 |
[BaekJoon] 백준 1182번 부분수열의 합 (0) | 2021.08.06 |
[BaekJoon] 백준 18870번 좌표 압축 (0) | 2021.07.31 |