oneway's history

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

1. 자바로 풀때처럼 리스트 형식으로 구현할라고 했는데, 정점 수가 많아서 메모리 초과가 났다.

  -> 그래서 연결된 부분만 입력받도록 append 하는거로 바꿈

  -> 오름차순 컨셉 유지하기위해 graph의 모든 부분을 오름차순함.

2. 재귀로 DFS 할라했는데, 간선이 20만개로 너무 많아서 계속 Recursion Error 남. IDE에선 잘 돌아가는데.

  -> 그래서 그냥 Stack 과 While 문으로 해결함.

  -> Stack을 쓰다보니 앞쪽부터 빼가니까 graph를 내림차순으로 바꿈

import sys
from collections import deque
input = sys.stdin.readline
N, M, R = map(int, input().split())
# graph = [[False for i in range(N+1)] for i in range(N+1)]
graph = [[] for i in range(N+1)]
visited = [False for i in range(N+1)]
answer = [0 for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    # graph[a][b] = graph[b][a] = True
    graph[a].append(b)
    graph[b].append(a)

for i in range(N+1):
    # graph[i].sort()
    graph[i].sort(reverse=True)

# print(graph)
cnt = 1


# def dfs(num):
#     visited[num] = True
#     global cnt
#     # answer[cnt] = num
#     if answer[num] == 0:
#         answer[num] = cnt
#         cnt += 1
#     for idx in range(len(graph[num])):
#         s = graph[num][idx]
#         # 간선으로 연결되어있고 이미 방문하지 않았다면
#         # if graph[num][idx] == True and visited[idx] == False:
#         if visited[s] == False:
#             dfs(s)


# dfs(R)

stack = deque()
stack.append(R)

while stack:
    num = stack.pop()
    visited[num] = True
    if answer[num] == 0:
        answer[num] = cnt
        cnt += 1

    for idx in graph[num]:
        if visited[idx] == False:
            stack.append(idx)


for i in range(1, N+1):
    print(answer[i])

# 1. 전체를 리스트로 담다보니 메모리 초과남
# 2. 재귀를 쓰려다보니 간선이 200000개가 최대라 recursion error 뜸
# 3. 스택쓰고 while 쓴다.

그래프 문제를 너무 오랜만에 풀어서 그런가 꽤나 오래걸렸다.