[Python] 백준 1325 & 백준 1668

처음에는 dfs로 시도했다가 아무리 해도 시간초과, 메모리 초과...

대환장;;

import sys
sys.setrecursionlimit(10**6)

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[b].append(a)

def find_comp(num, visited):
    for next in graph[num]:
        if next not in visited:
            visited.add(next)
            find_comp(next, visited)
    return len(visited)

result = []
for i in range(1, n+1):
    visited = set()
    visited.add(i)
    cnt = find_comp(i, visited)
    result.append(cnt)

max_value = max(result)
for i in range(len(result)):
    if result[i] == max_value:
        print(i + 1, end=" ")

 

정답은 잘 나오는데 어디가 잘못됐는지 몰라서 bfs로 재시도...

 

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[b].append(a)

def bfs(num, visited):
    queue = deque()
    queue.append(num)
    visited[num] = True
    while queue:
        now = queue.popleft()
        for next in graph[now]:
            if not visited[next]:
                queue.append(next)
                visited[next] = True
                
    return visited.count(True)

result = []
for i in range(1, n+1):
    visited = [False] * (n+1)
    result.append(bfs(i, visited))

max_cnt = max(result)
for i in range(len(result)):
    if result[i] == max_cnt:
        print(i+1, end = " ")

결과는 성공! ㅠㅠ

dfs 코드 손봐서 다시 올려봐야징...

 

# 백준 1668 트로피

n = int(input())
trophies = []
for _ in range(n):
    trophies.append(int(input()))

def left():
    smallest = trophies[0]
    cnt = 1
    for i in trophies:
        if smallest < i:
            cnt += 1
            smallest = i

    return cnt