[백준] 24481번, 24482번 : 알고리즘 수업 - 깊이 우선 탐색 3, 4 파이썬

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

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

 

dfs 시리즈로 날먹중

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

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

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

모든 노드의 깊이(depth)를 출력!

시작 정점 R의 깊이는 0이고 방문 되지 않는 노드의 깊이는 -1로 출력하자.

 

24481번 코드

import sys
sys.setrecursionlimit(10**9)

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

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

 

dfs함수에 depth만 추가한거 빼고는 24479번 코드와 거의 똑같다.

처음에 visited배열을 -1로 초기화하고

dfs에 depth 추가해서 깊어질때마다 1씩 추가했다.

 

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

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

 

24482번 코드

import sys
sys.setrecursionlimit(10**9)

def dfs(r, depth):
  visited[r] = depth
  line[r].sort(reverse=True) # 내림차순으로 정렬
  for i in line[r]:
    if visited[i] == -1:
      dfs(i, depth +1)

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