백준 1260 - 파이썬

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

1260번: DFS와 BFS

DFS와 BFS 문제는 처음 풀어보기에 BFS와 DFS의 이론을 찾아보고 바로 코드를 참고해 봤다.

 

노드간의 연결을 True, False로 표현

from collections import deque

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

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

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

visited1 = [False] * (n+1)
visited2 = [False] * (n+1)

def bfs(v):
  q = deque([v])
  visited2[v]  = True

  while q:
    v = q.popleft()
    print(v, end=' ')

    for i in range(1, n+1):
      if not visited2[i] and graph[v][i]: # 만약 해당 i값을 방문하지 않았고, v와 연결이 되어 있다면
        q.append(i)
        visited2[i] = True

def dfs(v):
  visited1[v] = True
  print(v, end=' ')

  for i in range(1, n+1):
    if not visited1[i] and graph[v][i]:
      dfs(i)

dfs(start)
print()
bfs(start)

코드를 설명해보면 가장 먼저 graph에 False로 초기화를 진행하여 입력된 간선만 True로 바꿔주어 어떤 간선이 현재 존재하는지 표현하였다.

 

BFS는 큐를 사용하여 구현하기 때문에 deque라는 라이브러리를 사용하여 구현하였다. 가장 먼저 deque를 첫번째 노드로 초기화 해주고, queue가 빌때까지 while문을 반복해주면된다.

 

DFS같은 경우는 스택을 이용하여 구현하기 때문에 재귀함수를 이용했다.

 

노드를 저장하여 표현

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

def dfs(start):
  visited[start] = True
  print(start, end = " ")

  for i in graph[start]:
    if not visited[i]:
      dfs(i)

def bfs(start):
  queue = deque([start])
  visited[start] = True

  while queue:
    v = queue.popleft()
    print(v, end=' ')

    for i in graph[v]:
      if not visited[i]:
        visited[i] = True
        queue.append(i)

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 graph:
  i.sort()

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

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

문제에 있는 예제입력1을 입력해보면 변수 graph에 [[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]] 이렇게 저장이 되는데, 이것을 BFS와 DFS를 구현한 것이다.

 

BFS와 DFS를 공부하면서 느낀 점은 개념은 이해하기 쉬웠으나 코드를 스스로 구현하는데는 무리가 있었다. 얼른 익숙해져 다른 응용 문제들도 잘 풀어보고 싶다.