🔍 Problem

알고리즘 수업 - 깊이 우선 탐색 1

---

📃 Input&Output

• Input1 : mirkovC4nizCC44

• Input2 : C4

• output : mirkovniz

---

📒 해결과정

가. stack에 input1의 인덱스값 하나씩 추가한다.

나. 추가하는 도중 끝을 기준으로, Input2 가 발견되면 해당 길이만큼 stack 뒤에서 꺼낸다.

다. stack이 비어있으면 FRULA, 비어있지 않으면 stack안의 원소들을 출력한다.

---

❗주의점

가. order로 만약 1번 노드가 3번재에 방문했으면 order[1] = 3 즉, 각 노드들의 방문 순서 저장

나. list.index 함수 쓰지말기, 너무 오래 걸림!

---

💻 Code

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

import sys
sys.setrecursionlimit(150000)  # 이 줄을 꼭 추가하세요!

N,M,R=map(int,sys.stdin.readline().split())

vst=[False]*(N+1)

links=[[] for _ in range(N+1)]
result=[]
cnt=1
order=[0]*(N+1)

def dfs(R):
    global cnt
    
    vst[R]=True
    order[R]=cnt
    cnt+=1
    
    links[R].sort()
    for i in links[R]:
        if vst[i]==False:
            dfs(i)
                        
for _ in range(M):
    x,y=map(int,sys.stdin.readline().split())
    links[x].append(y)
    links[y].append(x)
    

dfs(R)
for i in range(1,N+1):
    print(order[i])

---

🤔 느낀점

오랜만에 튜플을 써서 새로웠고 -1이 인덱스값으로 맨 뒤라는 것을 알게 되었다. 사실 원래 알고 있었지만 까먹고 있었던 것 같다.