[백준] 1260번: DFS와 BFS - 파이썬 풀이

---

문제

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

1260번: DFS와 BFS

 

---

풀이

 

개념

: DFS, BFS를 그림으로 표현할 때 이해가 잘 되었다.

다음 영상은 이해할 때 많은 도움이 되었던 영상이다.

https://www.youtube.com/watch?v=_hxFgg7TLZQ 

즉, DFS BFS 둘 다 그래프를 완전히 탐색하는 방법이기 때문에

코드로 구현 시 구조는 같다

 

그럼 다른 점은? 탐색하는 순서!

앞으로 방문할 노드 리스트에서 원소를 뺄 때

뒤에서 뽑는지(DFS) 앞에서 뽑는지(BFS)만 정하면 된다.

 

앞으로 DFS BFS 문제를 풀때는 이런 기본형에

약간의 조건을 더 추가해 다양하게 응용 할 수 있다.

 

 

방문했던 노드를 표시하는 방법 (visited 구현하기)

1. list 이용

: visited를 list로 구현한다.

list로 구현한 visited 구조

리스트의 인덱스는 해당하는 노드의 방문 여부가 되고

이렇게 구현하면 된다!

 

visited = list(0 for _ in range(N+1))
visited[0] = 1

장점	방문할 노드를 .index()등의 방법으로 찾지 않아도 바로 확인할 수 있다.
단점	노드가 많을 경우, 공간에서 손해를 본다.

 

 

2. 딕셔너리 이용

: 딕셔너리를 이용해 방문한 노드를 찾는다.

참고 코드

https://ebbnflow.tistory.com/173

[알고리즘] 탐색 BFS, DFS _ 백준 1260 파이썬

장점	노드 n개 중에서 방문한 찾을 때 O(n)의 시간이 걸리는걸 줄일 수 있다. 구현도 간단해진다.

 

 

*구현 시 주의 할 점

방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야한다

input으로 주어지는 노드 값 들은 이미 정렬되어 있기 때문에,

인접 노드를 추가할 때 reversed 해준 값을 추가해준다.

 

---

제출 코드

 

내가 푼 방법

N, M, start = map(int, input().split())
tree = [[]*1 for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

for l in tree:
    l.sort()

def DFS(start):
    visited = list(0 for _ in range(N+1))
    visited[0] = 1
    stack = []
    stack.append(start)
    while stack:
        node = stack.pop()
        if visited[node] == 0:
            visited[node]=1
            stack += reversed(tree[node])
            print(node, end=' ')


def BFS(start):
    visited = list(0 for _ in range(N+1))
    visited[0] = 1
    queue = []
    queue.append(start)
    while queue:
        node = queue.pop(0)
        visited[node] = 1
        for adj in tree[node]:
            if visited[adj] == 0:
                visited[adj] = 1
                queue.append(adj)
        print(node, end=' ')
DFS(start)
print()
BFS(start)

 

 

참고 코드

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

def dfs(graph, v):
    visited = {}
    stack = [v]
    while stack:
        n = stack.pop()
        if n not in visited:
            visited.setdefault(n)
            stack += reversed(graph[n])
    return visited

def bfs(graph, v):
    visited = {}
    queue = deque([v])
    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.setdefault(n)
            queue += graph[n]
    return visited

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

graph = {i: [] for i in range(1, n + 1)}
for i in range(1, m + 1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

for key in graph:
    graph[key].sort()
print(' '.join(list(map(str, dfs(graph, v)))))
print(' '.join(list(map(str, bfs(graph, v)))))

 

 

 

---

결과