[백준] 1260 - DFS와 BFS (파이썬, Python)

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

1260번: DFS와 BFS

python으로 dfs와 bfs를 구현해보고 접한 첫 번째 문제였다.

입력 값만 잘 처리하면 쉽게 풀릴 문제라 생각했다.

 

from collections import deque
import sys

def bfs(graph, root) :
    visited = []
    queue = deque([root])

    while queue :
        cur_node = queue.popleft()
        if cur_node not in visited :
            visited.append(cur_node)
            queue.extend(graph[cur_node])
    return visited

def dfs(graph, root) :
    visited = []
    stack = [root]

    while stack :
        cur_node = stack.pop()
        if(cur_node not in visited) :
            visited.append(cur_node)
            stack.extend(reversed(graph[cur_node]))
    
    return visited

my_input = lambda : sys.stdin.readline().rstrip()

N, M, V = map(int, my_input().split())

graph = {}

for _ in range(M):
    s, d = map(int, my_input().split())
    if(s in graph.keys()):
        graph[s].append(d)
    else:
        graph[s] = [d]

    if(d in graph.keys()):
        graph[d].append(s)
    else:
        graph[d] = [s]
    
for k in graph.keys():
    graph[k].sort()

print(*dfs(graph, V))
print(*bfs(graph, V))

 

런타임 에러로 실패했다.

문제를 풀면서 N이 사용 안되는 점이 걸렸는데 역시 실패했다.

 

생각하지 못한 케이스가 있었다.

 

#입력 값
5 1 2
3 4

 

시작점에 연결된 간선이 하나도 없을 때를 고려하지 못했다.

위와 같은 케이스에서 KeyError 가 발생된다.

---

from collections import deque
import sys

def bfs(graph, root) :
    visited = []
    queue = deque([root])

    while queue :
        cur_node = queue.popleft()
        if cur_node not in visited :
            visited.append(cur_node)
            queue.extend(graph[cur_node])
    
    return visited

def dfs(graph, root) :
    visited = []
    stack = [root]

    while stack :
        cur_node = stack.pop()
        if(cur_node not in visited) :
            visited.append(cur_node)
            stack.extend(reversed(graph[cur_node]))
    
    return visited

my_input = lambda : sys.stdin.readline().rstrip()

N, M, V = map(int, my_input().split())

graph = {}

for i in range(1, N+1):
    graph[i] = []

for _ in range(M):
    s, d = map(int, my_input().split())
    graph[s].append(d)
    graph[d].append(s)    

for k in graph.keys():
    graph[k].sort()

print(*dfs(graph, V))
print(*bfs(graph, V))

 

개선 사항

1. 모든 노드를 graph의 key로 삽입했다.

 

---

from collections import deque
import sys

def dfs(matrix, start_node):
    visited = []
    stack = [start_node]
    while stack:
        cur_node = stack.pop()
        if cur_node not in visited:
            visited.append(cur_node)
            adj_node = [i for i in range(N+1) if matrix[cur_node][i] == 1]
            stack.extend(reversed(adj_node))

    return visited

def bfs(matrix, start_node):
    visited = []
    queue = deque([start_node])
    while queue:
        cur_node = queue.popleft()
        if cur_node not in visited:
            visited.append(cur_node)
            adj_node = [i for i in range(N+1) if matrix[cur_node][i] == 1]
            queue.extend(adj_node)

    return visited

my_input = lambda : sys.stdin.readline().rstrip()

N, M, V = map(int, my_input().split())

adj_matrix = [[0 for j in range(N+1)]for i in range(N+1)]

for _ in range(M):
    s, d = map(int, my_input().split())
    adj_matrix[s][d] = 1
    adj_matrix[d][s] = 1

print(*dfs(adj_matrix, V))
print(*bfs(adj_matrix, V))

 

다른 분들의 풀이를 찾아보니 인접행렬을 이용한 풀이법이 많았다.

또 하나 배워가는 문제였다.

 

---

참조 코드

https://this-programmer.com/entry/%EB%B0%B1%EC%A4%801260%ED%8C%8C%EC%9D%B4%EC%8D%AC-DFS%EC%99%80-BFS