[백준] 24479번, 24480번 : 알고리즘 수업 - 깊이 우선 탐색 1, 2 파이썬

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

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

 

 

dfs 문제풀어보자

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

 dfs를 이용해서 그래프를 탐색하는 문제

dfs를 수행할때 각 노드에 연결된 노드를 오름차 순으로 방문해야한다!

 

24479번 코드

import sys
# 재귀 깊이 한도를 크게 설정
sys.setrecursionlimit(10**9)

def dfs(r):
  global cnt
  visited[r] = cnt
  line[r].sort() #오름차순으로 정렬
  for i in line[r]:
    if visited[i] == 0:
      cnt+=1
      dfs(i)

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

 

코드 설명

 

- 재귀한도 설정

sys.setrecursionlimit(10**9)

 

파이썬의 기본 재귀 깊이는 1000으로 제한되어 있습니다. RecursionError를 방지하기 위해 재귀 깊이 한도를 10**9로 설정합니다.

 

- DFS 함수

def dfs(r):
    global cnt
    visited[r] = cnt
    line[r].sort()  # 오름차순으로 정렬
    for i in line[r]:
        if visited[i] == 0:
            cnt += 1
            dfs(i)

 

• dfs 함수는 현재 노드 r을 방문하고, 오름순으로 연결된 노드들을 방문합니다.
• 방문 순서를 기록하기 위해 cnt를 사용합니다.

- 그래프 입력

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

• visited 리스트는 각 노드의 방문 순서를 기록
• line 리스트는 각 노드의 연결 정보를 저장

 

 

24480번 풀이 (알고리즘 수업 - 깊이 우선 탐색 2)

24479번과 다른 점은 노드를 내림차 순으로 방문한다. 그래서 24479번 코드에서 한 줄만 수정하면된다.

 

24480번 코드

import sys
sys.setrecursionlimit(10**9)
def dfs(r):
  global cnt
  visited[r] =cnt
  line[r].sort(reverse=True) # 내림차순으로 정렬
  for i in line[r]:
    if visited[i] == 0:
      cnt +=1
      dfs(i)

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

 

 

 

line[r].sort(reverse=True) # 내림차순으로 정렬

이부분만 고치면된다.

 

감사합니당.