[python] 백준 24479번, 24444번 - DFS, BFS

24479번: 알고리즘 수업 - 깊이 우선 탐색 1 (acmicpc.net)

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

 

24444번: 알고리즘 수업 - 너비 우선 탐색 1 (acmicpc.net)

24444번: 알고리즘 수업 - 너비 우선 탐색 1

 

DFS와 BFS를 구현하는 문제이다.

지난번에 공부했던 기억을 되살려 코드를 작성해보려고 했는데 쉽지 않았다.

 

우선 이 문제를 구현하는 데 있어 기억해야할 점은

sys.setrecursionlimit() 의 사용이다.

파이썬의 재귀 깊이 제한은 매우 얕기 때문에 재귀를 사용해야 한다면 이 코드를 반드시 사용해야한다.

dfs를 구현할 때 재귀를 사용하였기 때문에 이를 사용하였다.

 

-dfs

import sys
sys.setrecursionlimit(10**6)
n,m,r = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n+1)]	# 그래프 노드와 인접 노드 저장
visited=[0] * (n+1)		# 방문한 노드를 저장하기 위한 리스트

cnt=1	# 방문 횟수

def dfs(graph, v, visited):
    global cnt
    visited[v] = cnt
    
    for i in graph[v]:
        if visited[i] == 0:
            cnt+=1
            dfs(graph, i, visited)
            

for i in range(m):
    u,v = map(int,sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
    
for i in range(n+1):	# 인접노드 정렬
    graph[i].sort()
     
dfs(graph, r, visited)

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

 

-bfs

import sys
from collections import deque
sys.setrecursionlimit(10**6)
n,m,r = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n+1)]

for i in range(m):
    u,v = map(int,sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
    
for i in range(n+1):
    graph[i].sort()
cnt=1
visited=[0]*(n+1)

def bfs(v):
            
    global cnt
    
    q = deque([v])
    visited[v] =1
    cnt +=1
    
    while q:
        v = q.popleft()
        
        for i in graph[v]:
            if visited[i] == 0:
                q.append(i)
                visited[i] = cnt
                cnt+=1
            
bfs(r)

print(*visited[1:], sep="\n")