[Python/Silver II] DFS와 BFS - 1260, 스택, 재귀함수, deque, queue

문제 설명

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

code

import sys
from collections import deque
input = sys.stdin.readline

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

graph = [[] for _ in range(n+1)]

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

for i in range(1, n+1):
    graph[i].sort()

def dfs(n):
    print(n, end=' ')
    visited[n] = True
    for i in graph[n]:
        if not visited[i]:
            dfs(i)

def bfs(n):
    visited[n] = True
    queue = deque([n])
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True


visited = [False] * (n + 1)
dfs(v)
print()
visited = [False] * (n + 1)
bfs(v)

•  문제 조건 1. 정점 개수 n, 간선 개수 m, 탐색 시작 정점 번호 v입니다.
  • n, m, v = map(int, input().split())
• 문제 조건 2. 인접 리스트입니다.
  • graph = [[] for _ in range(n+1)]
  • n+1로 []를 곱해주는 이유는 무엇인가요?
    • graph[0] 0번 인덱스는 사용되지 않고 편의상 무시됩니다.
    • 예를 들어 graph[1]은 노드 1에 인접한 노드들의 리스트가 되고, graph[2]는 노드 2에 인접한 노드들의 리스트가 됩니다.
• 문제 조건 3. m개의 줄에는 간선이 연결하는 두 정점의 번호가 주어집니다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있습니다. 양방향입니다.
  • for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b) # graph[a]에는 a와 인접한 b 노드가 있습니다.
    graph[b].append(a) # graph[b]에는 b와 인접한 a 노드가 있습니다.
• 문제 조건 4. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작을 것을 먼저 방문합니다.
  • for i in range(1, n+1): # graph[0]은 편의상 사용하지 않기에, 1부터 n까지 for문
    graph[i].sort() # graph 값을 오름차순으로 정렬합니다.

 

• DFS 알고리즘 구현
  • 구현 조건 1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리합니다.
  • 구현 조건 2. 스택 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다.
  • 구현 조건 3. 만약 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
  • 구현 조건 4. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.
  • 1번 수행
    
    • print(n, end=' ')
      visited[n] = True # 탐색 시작 노드를 스택에 삽입, 방문 처리(True)합니다.
  • 2번 수행
    
    • for i in graph[n]: # 인접 노드를 체크합니다.
    • if not visited: # 방문하지 않은 인접 노드가 있으면 방문 처리합니다.
      dfs(i) # 재귀함수

 

• BFS 알고리즘 구현
  • 구현 조건 1. 탐색 시작 노드를 큐에 삽입하고, 방문 처리합니다.
  • 구현 조건 2. 큐에서 노드를 꺼낸 뒤, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고, 방문 처리합니다.
  • 구현 조건 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.
  • 1번 수행
    • visited[n] = True
      queue = deque([n]) # deque에는 이터러블 값만 넣을 수 있어서 [n]로 넣어줍니다.
  • 3번 수행
    • while queue:
  • 2번 수행
    • v = queue.popleft() # 큐에서 노드를 꺼냅니다.
      print(v, end=' ')
    • for i in graph[v]: # 인접 노드를 체크합니다.
    • if not visited[i]: # 방문하지 않은 노드를 확인합니다.
    • queue.append(i) # 방문하지 않은 노드를 모두 큐에 삽입합니다.
    • visited[i] = True # 해당 노드를 방문 처리합니다.

 

• 함수 실행
  • 공통. DFS, BFS 수행을 위해 방문 여부 리스트를 초기화 합니다.
  • 출력 조건. 첫째 줄에 DFS 결과물, 그 다음 줄에 BFS 결과물을 출력합니다.
    • visited = [False] * (n+1) # DFS 방문 여부 리스트 초기화합니다.
    • dfs(v) # dfs 함수를 실행합니다.
    • print() # 개행을 위해 print를 작성합니다.
    • visited = [False] * (n+1) # BFS 방문 여부 리스트 초기화합니다.
    • bfs(v) # bfs 함수를 실행합니다.

---

https://github.com/seonmin5/codingtest_Python

GitHub - seonmin5/codingtest_Python