1260. DFS와 BFS - 파이썬

1260. DFS와 BFS 

사용한 알고리즘 및 자료구조
1. BFS, 스택
2. DFS, 큐
3. 연결 리스트

접근 방식
1. BFS와 DFS 를 구현한다.

문제 특이사항
1. 방문할 수 있는 정점이 여러 개인 경우에는
정점 번호가 작은 것을 먼저 방문해야 한다.

스택: 후입선출
큐: 선입선출

의 특징을 염두에 두고 구현해야 한다.

2. DFS
특정 지점의 연결 리스트를 조회할 때
연결 리스트를 
1) 오름차순 정렬 후 
2) pop()으로 스택에 삽입하면
3) 정점 번호가 큰 순서대로 스택에 삽입된다. 
==> 정점 번호가 작은 순서대로 조회할 수 있다!

3. BFS
특정 지점의 연결 리스트를 조회할 때
연결 리스트를
1) 내림차순 정렬 후 
2) pop() 으로 큐에 삽입하면
3) 정점 번호가 작은 순서대로 큐로 들어간다.
==> 정점 번호가 작은 순서대로 조회 가능!

리스트의 인덱스를 지정하지 않는 pop()연산으로
시간 복잡도를 절약. 

느낀점
시/공간 복잡도를 항상 염두하자.

최선을 ㄷ해 

# BFS연산을 위해 덱 import
from collections import deque
import sys # 빠른 input을 위해 sys를 import 후 
input = sys.stdin.readline # 편의상 input을 sys.stdin.readline으로 사용. 

# 3. 연산
# 3-1. DFS
def DFS():
    while STK: # 스택이 차 있는 동안 
        now = STK.pop() # 현재 지점을 확인. 
        if DFS_nods[now]: # 간선이 남아있다면 
            DFS_nods[now].sort() # 간선들을 '오름차순' 정렬
            while DFS_nods[now]: # 이후 모든 간선들을 스택에 삽입. 
                STK.append(DFS_nods[now].pop()) # 오른쪽부터 pop. 

        # 4. 출력
        if not DFS_visited[now]: # 현재 정점을 방문하지 않았다면
            DFS_visited[now] = 1 # 방문 표시 후 
            print(now, end=' ') # 현재 정점 번호를 서식에 맞게 인쇄. 

# 3-2. BFS

def BFS(): 
    while Q: # 큐가 차있는 동안 
        now = Q.popleft() # 현재 지점을 확인. 

        if BFS_nods[now]: # 만약에 간선들이 있다면 
            BFS_nods[now].sort(reverse=True) # 간선을 내림차순으로 정렬 후 
            while BFS_nods[now]: # 간선을 큐에 삽입.
                Q.append(BFS_nods[now].pop()) # 오른쪽부터 큐에 삽입. 

        if not BFS_visited[now]: # 현재 정점을 방문하지 않았다면
            BFS_visited[now] = 1 # 방문 표시 후 
            print(now, end=' ') # 현재 정점 번호를 서식에 맞게 인쇄.

# 주요 함수

# 1. 입력
# 1-1. 입력 및 선언
# N: 정점의 갯수
# M: 간선의 갯수
# V: 시작 정점 번호.

N, M, V = map(int, input().split())

DFS_nods = [[] for _ in range(N+1)] # DFS에 사용할 연결 리스트
DFS_visited = [0] * (N + 1) # DFS에 사용할 방문 여부 리스트
BFS_nods = [[] for _ in range(N+1)] # BFS에 사용할 연결 리스트
BFS_visited = [0] * (N + 1) # BFS에 사용할 방문 여부 리스트


# 1-2. 간선 정보 입력
# 간선의 갯수 M에 맞춰

for i in range(M):
    st, ed = map(int, input().split()) # 간선 정보를 입력받은 후
    DFS_nods[st].append(ed) # 연결리스트에 저장.
    DFS_nods[ed].append(st) # 양방향 간선이므로 반대 방향도 저장. 

    BFS_nods[st].append(ed) # BFS연결 리스트에도
    BFS_nods[ed].append(st) # 동일한 작업. 

STK = [] # DFS구현을 위한 스택 선언
STK.append(V) # 스택에 초기값 삽입. 
DFS() # DFS 연산. 출력 작업도 함수 내에서 수행. 

print() # 문제의 출력조건

Q = deque() # BFS구현을 위한 덱 선언
Q.append(V) # 덱에 초기값 삽입.
BFS() # BFS연산. 출력 작업도 함수 내에서 수행.