백준 #24484 알고리즘 수업 - 깊이 우선 탐색 6

코드

import sys
# sys.stdin = open("input.txt")
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(cur, depth):
    global cnt
    visited[cur] = cnt
    d[cur] = depth
    for nxt in graph[cur]:
        if not visited[nxt]:
            cnt += 1
            dfs(nxt, depth + 1)
    return

n, m, r = map(int, input().rstrip().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, n + 1):
    graph[i].sort(reverse = True)
    
visited = [0] * (n + 1)
d = [-1] * (n + 1)
cnt = 1
dfs(r, 0)
answer = 0
for i in range(1, n + 1):
    answer += visited[i] * d[i]
    
print(answer)

풀이

오늘은 예비군 훈련이 있었다.. 6년차 작계훈련이라 남는 시간이 많았다.

백준을 보던 도중 알고리즘 스터디의 1주차 주제인 그래프 탐색 관련 문제가 있어서 모바일로 풀어 보려고 했다.

집중이 안되어서 그런지 많이 틀렸고, cnt 에 관한 부분과 sort 부분을 다시 체크 해서 맞았다!!

기본적인 문제인 것 같은데 내일 다시 내 풀이를 안보고 풀어 봐야겠다.

화이팅!!!