[백준] 24483번, 24484번 : 알고리즘 수업 - 깊이 우선 탐색 5, 6 파이썬

 

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

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

dfs 날먹 문제 끝......

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

알고리즘 수업 - 깊이 우선 탐색 1, 3(24479번, 24481번) 두 문제에서 출력하는 값을 그냥 곱해서 합한후 출력하기만 하면된다.

 

24483번 코드

import sys
sys.setrecursionlimit(10**9)

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

n,m,r =map(int, sys.stdin.readline().split())
visited = [0] * (n+1)
depth = [-1] * (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, 0)
sum = 0
for i in range(1, n+1):
  sum += visited[i] * depth[i]
print(sum)

 

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

앞의 문제랑 다똑같은데 내림차순으로 탐색하면된다.

 

24484번 코드

import sys
sys.setrecursionlimit(10**9)

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

n,m,r =map(int, sys.stdin.readline().split())
visited = [0] * (n+1)
depth = [-1] * (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, 0)
sum = 0
for i in range(1, n+1):
  sum += visited[i] * depth[i]
print(sum)

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

이부분만 수정