[백준] 1260번 DFS와 BFS (with python)

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

1260번: DFS와 BFS

 

1. 내가 작성한 코드

from collections import deque

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

visit_dfs = [0] * (n+1)
visit_bfs = [0] * (n+1)

matrix = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
  a,b = map(int, input().split())
  matrix[a][b] = matrix[b][a] = 1

def dfs(v):
  visit_dfs[v] = 1
  print(v, end=' ')
  
  for i in range(n+1):
    if visit_dfs[i] == 0 and matrix[v][i] == 1:
      dfs(i)


def bfs(v):
  visit_bfs[v] = 1
  queue = deque()
  queue.append(v)

  while queue:
    popV = queue.popleft()
    print(popV, end=' ')
    for i in range(1, n+1):
      if visit_bfs[i] == 0 and matrix[popV][i] == 1:
        queue.append(i)
        visit_bfs[i] = 1

dfs(v)
print()
bfs(v)

와 대박 dfs, bfs 처음해보는데 개어렵다 

 

 

한 문단씩 분석

 

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

visit_dfs = [0] * (n+1)
visit_bfs = [0] * (n+1)

matrix = [[0]*(n+1) for _ in range(n+1)]

정점, 간선, 시작할 정점의 주소를 입력받고, 방문한 것을 체크하기위한 list를 각각 생성한다.

 

인접행렬을 만들기 위해 matrix 배열에 [0]을 삽입한다.

이때, 행과 열에서 index가 0인 부분은 제외해야 하기 때문에 n+1번 반복해준다.

 

for i in range(m):
  a,b = map(int, input().split())
  matrix[a][b] = matrix[b][a] = 1

연결되어 있는 횟수 만큼만 반복하면 되기 때문에 간선의 개수만큼 for문을 돌려주고,

 

각 정점이 연결되어 있음을 알려주기 위해 1을 삽입한다.

 

(양방향 이기 때문에 이차원 배열을 이용한 것)

 

def dfs(v):
  visit_dfs[v] = 1
  print(v, end=' ')
  
  for i in range(n+1):
    if visit_dfs[i] == 0 and matrix[v][i] == 1:
      dfs(i)

dfs 를 구현한 코드이다. 재귀함수를 이용해서 구현한다.

 

def bfs(v):
  visit_bfs[v] = 1
  queue = deque()
  queue.append(v)

  while queue:
    popV = queue.popleft()
    print(popV, end=' ')
    for i in range(1, n+1):
      if visit_bfs[i] == 0 and matrix[popV][i] == 1:
        queue.append(i)
        visit_bfs[i] = 1

bfs를 구현한 코드이다. queue를 이용해서 구현해야 하는데, python의 기본 라이브러리인 deque를 이용하면

 

popleft()를 이용할 수 있기 때문에 deque로 자료구조를 바꿔준다.

 

한 번도 방문한적이 없지만, v와 연결되어 있을 경우 queue에 i를 삽입한다.