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

 

풀이

 

• 문제 이해를 못했어서 조금 시간이 걸렸는데
• 분명 dfs로 해결은 했는데 뭐가 문제지 싶어서
• 계속 찾아본 결과
• 방문한 순서를 1~n번까지 순서대로 나열하는 문제라는 것을 알게 되었다.
• 아래 코드는 다른 dfs 코드와 비슷할 것이기에 풀이를 따로 작성할 것은 없지만
• 양방향으로 연결해야 하기에 아래와 같이 작성했으며
  • _dic[u].append(v)
  • _dic[v].append(u)
• 오름차순으로 방문한다고 했기에 정렬을 하지만 dfs로 방문하기에
• reverse=True를 사용해서 내림차순 정렬을 하여 역순으로 stack에 추가하면
• 오름차순이 되도록 해주기!

 

import sys

from collections import deque

input = sys.stdin.readline

n,m,r = map(int,input().split())

_dic = {i:[] for i in range(1,n+1)}

visit = [0]*(n+1)

for i in range(m):

    u,v = map(int,input().split())

    _dic[u].append(v)

    _dic[v].append(u)

for i in range(1,n+1): _dic[i].sort(reverse=True)

stack = deque([r])

cnt = 0

while stack:

    s = stack.pop()

    if visit[s]: continue

    cnt += 1

    visit[s] = cnt

    for i in _dic[s]:

        if not visit[i]: stack.append(i)

[print(i) for i in visit[1:]]