[백준 / Python] 1260번 DFS와 BFS

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

1260번: DFS와 BFS

 

[문제 해석]

본 문제는 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제이다. 단, 방문할 수 있는 정점이 여러 개인 경우, 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우에 종료하도록 하는 문제이다.

 

이때, DFS란 깊이 우선 탐색, BFS는 넓이 우선 탐색을 의미한다.

 

[소스코드]

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

def bfs(v):
  q = deque()
  q.append(v)       
  visit_list[v] = 1   
  while q:
    v = q.popleft()
    print(v, end = " ")
    for i in range(1, n + 1):
      if visit_list[i] == 0 and graph[v][i] == 1:
        q.append(i)
        visit_list[i] = 1

def dfs(v):
  visit_list2[v] = 1        
  print(v, end = " ")
  for i in range(1, n + 1):
    if visit_list2[i] == 0 and graph[v][i] == 1:
      dfs(i)

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

graph = [[0] * (n + 1) for _ in range(n + 1)] 
visit_list = [0] * (n + 1)
visit_list2 = [0] * (n + 1)

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

dfs(v)
print()
bfs(v)

 

[문제 풀이]

트리나 그래프의 구조를 가지고 서로 연결된 노드들을 파악할 수 있는데, 해당 문제에서는 Node를 만들고 연결해서 문제를 해결하기에는 문제가 있다. 그렇기 때문에 인접한 행렬 방식으로 행과 열을 확인하여 해당 숫자들이 연결되어 있는지 확인하는 방법으로 진행하였다.

N개의 숫자가 있으므로, (n+1) x (n+1) 의 행렬을 리스트를 통해 0으로 채워주고, 인덱스와 값을 일치시키기 위해 N+1개의 숫자를 사용하였다.

연결된 숫자들 값을 입력받아 해당 행과 열의 값을 1로 바꿔줌으로써 행과 열의 숫자가 연결되어 있다는 표시를 해주었다.