CS/Algorithm 문제

[BaekJoon] 백준 1325 효율적인 해킹

[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
반응형