[백준] 24479 파이썬(python) : 알고리즘 수업 - 깊이 우선 탐색 1

24479번 : 알고리즘 수업 - 깊이 우선 탐색 1

 

 

 

pypy3로 제출하면 메모리초과가 발생하니 python3로 제출해야한다.

 

import sys
sys.setrecursionlimit(10**9) #1
n, m, r = map(int, sys.stdin.readline().split())
graph = [ [] for _ in range(n+1) ] #2
visit = [0] * (n + 1) #3
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split()) #4
    graph[a].append(b) #5
    graph[b].append(a)
count = 1

def dfs(v):
    global count
    visit[v] = count #7
    graph[v].sort() #6
    for i in graph[v]:
        if visit[i] == 0:
            count += 1
            dfs(i)
dfs(r)
for i in range(1, n + 1): #8
    print(visit[i])

 

#1 : 재귀 함수 제한 해제 1억으로 설정했다.

#2 : 각 노드의 개수만큼 리스트 생성

#3 : dfs의 필수 방문확인 리스트 생성

#4 : 런타임에러를 피하기 위해 반복문에 readline()함수 사용

#5 : 서로 연결되는 양방향 노드

#6 : 입력값이 정렬되지 않기에 정렬

#7 : 첫 노드를 1로 해서 방문하는 노드마다 +1 추가

#8 : 특정 노드의 방문 순서를 알 수 있다.

 

dfs의 단계별로 풀어보기 첫번째 문제였다. 문제를 풀기위해 재귀함수해제도 해줘야했고 readline()함수도 사용해줘야 했다. 양방향노드의 다른 연결방법과 방문순서를 출력하는 방법을 배울 수 있는 문제였다.

 

다른 풀이

 

import sys
sys.setrecursionlimit(10**9)
n, m, r = map(int, sys.stdin.readline().split())
graph = [ [] for _ in range(n+1) ]
visit = [0] * ( n + 1 )
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
count = 1
visit[r] = count

def dfs(v):
    global count
    graph[v].sort()
    for i in graph[v]:
        if visit[i] == 0:
            count += 1
            visit[i] = count
            dfs(i)

dfs(r)

for i in range(1, n+1):
    print(visit[i])