[백준] 1260번 - DFS와 BFS

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

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

출력의 첫 번째 줄에는 DFS의 수행 결과를,

두 번째 줄에는 BFS의 수행 결과를 출력하면 되는 문제이다.

앞서 DFS 기초가 되는 24479와 24480을, BFS 기초가 되는 24444와 24445를

풀었으면 해당 코드를 참고하여 쉽게 문제를 풀어낼 수 있다.

 

import sys
from collections import deque
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

bfsVisited = [0] * (n+1)
dfsVisited = [0] * (n+1)

dfsCount = 1

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

print(graph)

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

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

dfs(v)
print()
bfs(v)

 

처음에는 다음과 같은 코드로 풀었지만,

이후에 다시 한번 풀면서 조금 더 깔끔하게 고쳐보았다.

 

import sys
from collections import deque
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n,m,v = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)

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

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

def bfs(v):
  q = deque([v])
  visited[v] = 1
  cnt = 2
  while q:
    v = q.popleft()
    print(v, end=' ')
    for k in graph[v]:
      if visited[k] == 0:
        visited[k] = cnt
        cnt += 1
        q.append(k)

cnt = 1
def dfs(v):
  global cnt
  visited[v] = cnt
  print(v, end=' ')
  for k in graph[v]:
    if visited[k] == 0:
      visited[k] = cnt
      cnt += 1
      dfs(k)

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

 

정점을 입력하여 해당 정점으로부터의 탐색을 진행해야하기 때문에

bfs와 dfs 모두 받는 인자는 정점의 번호 1개로 설정한다.

 

bfs에서는 deque을 사용하여 문제를 풀게 되는데,

방문한 정점의 번호가 popleft 이후에 오는 v와 동일하기 때문에

해당 지점에서 print문을 작성해줄 수 있다.

 

bfs에서 큐가 계속해서 존재한다면(append),

해당 노드를 돌면서 popleft를 수행할 것이고

방문한 정점의 번호를 출력할 수 있게 된다.

 

dfs에서는 재귀를 사용하여 문제를 풀게 되는데,

bfs와 동일한 로직의 구성이지만 큐를 사용하지 않고

탐색을 깊이있게 끝마칠때까지 재귀가 돈다는 것이 특징이다.

 

dfs의 출력을 진행하고,

방문을 기록한 리스트는 다시한번 초기화한뒤

줄바꿈을 위해서 print()를 작성해주었다.

마지막으로 bfs를 실행하면 정답이 된다.

 

화이팅 💪