[Python] BOJ 1260 - DFS와 BFS

https://www.acmicpc.net/problem/1260

 

01. 🔎 문제 탐색

N: 정점의 개수
M: 간선의 개수
V: 시작 정점

시작점으로부터 DFS와 BFS를 수행하여 방문하는 정점의 위치를 순차적으로 출력

 

02. 📝 코드 설계하기

1.  2차원 배열에 두 정점 사이에 간선 유무를 마킹(0, 1)
2.  시작점을 인자로 DFS, BFS를 수행하여 방문하는 정점을 순차적으로 출력
      2.1.  방문한 정점은 `is_visited` 1차원 배열을 이용하여 마킹하는 것으로 재방문하지 못하도록 함

---

04. 🗝️ 정답 코드

import sys
input = sys.stdin.readline

# n: 정점 개수
# m: 간선 개수
# v: 시작 정점
n, m, v = map(int, input().split())

graph = [[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
  v1, v2 = map(int, input().split())
  graph[v1][v2] = 1
  graph[v2][v1] = 1

# DFS
def dfs(cur):
  res = str(cur)
  is_visited[cur] = 1

  for i in range(1, n+1):
    if graph[cur][i] == 1 and is_visited[i] == 0:
      res += " " + dfs(i)
  return res

# BFS
def bfs(cur):
  res = ""
  is_visited[cur] = 1
  
  q = []
  q.append(cur)
  while len(q):
    cur = q.pop(0)
    res += str(cur) + " "

    for i in range(1, n+1):
      if graph[cur][i] == 1 and is_visited[i] == 0:
        q.append(i)
        is_visited[i] = 1

  return res;

is_visited = [0 for _ in range(n+1)]
print(dfs(v))

is_visited = [0 for _ in range(n+1)]
print(bfs(v))