백준 #24479 알고리즘 수업 - 깊이 우선 탐색 1

코드

import sys
sys.stdin = open("input.txt")
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(cur):
    global cnt
    for nxt in graph[cur]:
        if not visited[nxt]:
            visited[nxt] = cnt
            cnt += 1
            dfs(nxt)
    return

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

visited = [0] * (n + 1)
for nodes in graph:
    nodes.sort()
visited[r] = 1
cnt = 2
dfs(r)
print(*visited[1:])

풀이

그래프이론과 관련된 문제를 찾다가 실버2 난이도인데 정답비율이 22프로여서 도전해보았다.

간단한 DFS 문제였지만 RecursionError와 메모리초과로 인해 한번에 맞추지 못했다 ㅎㅎ

문제를 읽고 시간복잡도나 메모리와 관련해서도 신경을 써주어야 하는데 아직은 잘 안된다.

이와 관련해서 좀 더 공부해야겠다! 화이팅!!