[백준] 1260번: DFS와 BFS - Python

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

1260번: DFS와 BFS

아이디어

• 큐를 이용한 BFS
• 재귀를 이용한 DFS
• 방문처리 배열 하나로 두 번 사

구현(틀림)

import sys
from collections import deque
#dfs
def dfs(v):
    dfs_li.append(v)
    for i in range(n):
        if m_li[i][0] == v and not check[m_li[i][1]]:
            check[m_li[i][1]] = True
            dfs(m_li[i][1])

def bfs(v):
    q = deque()
    q.append(v)
    while q:
        now = q.popleft()
        bfs_li.append(now)
        for i in range(n):
            if m_li[i][0] == now and check[m_li[i][1]]:
                q.append(m_li[i][1])
                check[m_li[i][1]] = False

input = sys.stdin.readline
n, m, v = list(map(int, input().split()))

m_li = []
for i in range(m):
    tmp = list(map(int, input().split()))
    m_li.append(tmp)

check = [False]*(n+1)
dfs_li = []
bfs_li = []


dfs(v)
bfs(v)

for i in dfs_li:
    print(i, end=" ")
print()
for i in bfs_li:
    print(i, end=" ")

• 흠 틀렸다

틀린 원인 분석

• 이게 앞에 요소만 보고 연결을 판단하니까 인지하지 못하는 길이 있는 듯함
• 연결 판단을 앞자리로 하지 말고 거기에 그 노드가 존재하는지로 판단하고 풀어야 할 듯

구현(찾아봄..)

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)

 

마무리

• 뭔가 아리송하다 왜 안되는지 아직 잘 모르겠어서 다음에 도 다시 봐야 할 것 같은 문제
• dfs bfs 어느 정도 안다고 생각했는데 아직 멀었나 보다..
• 꼭 다시 풀어볼 것