[파이썬/Python] 백준 1260번 DFS와 BFS

[파이썬/Python] 백준 1260번 DFS와 BFS

1260번: DFS와 BFS

---

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

해설

DFS와 BFS의 탐색 과정을 함수 내에 리스트로 저장해주고, 이를 출력하면 된다.

 

코드

import sys
from collections import deque

sys.setrecursionlimit(10000)

n, m, start = map(int, sys.stdin.readline().split())
graph = {}

for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    if u in graph:
        graph[u].append(v)
        graph[u].sort()
    else:
        graph[u] = [v]
    if v in graph:
        graph[v].append(u)
        graph[v].sort()
    else:
        graph[v] = [u]

def dfs(u):
    visited[u] = True
    res.append(u)
    if u in graph:
        for v in graph[u]:
            if not visited[v]:
                dfs(v)

def bfs(start):
    queue = deque([start])
    visited[start] = True
    while queue:
        u = queue.popleft()
        res.append(u)
        if u in graph:
            for v in graph[u]:
                if not visited[v]:
                    visited[v] = True
                    queue.append(v)

visited = [False for _ in range(n+1)]
res = []
dfs(start)
print(*(res))

visited = [False for _ in range(n+1)]
res = []
bfs(start)
print(*(res))

 

풀이

import sys
from collections import deque

sys.setrecursionlimit(10000)

n, m, start = map(int, sys.stdin.readline().split())
graph = {}

for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    if u in graph:
        graph[u].append(v)
        graph[u].sort()
    else:
        graph[u] = [v]
    if v in graph:
        graph[v].append(u)
        graph[v].sort()
    else:
        graph[v] = [u]

1. 그래프를 딕셔너리로 선언하고, 정점과 간선을 저장한다.

 

def dfs(u):
    visited[u] = True
    res.append(u)
    if u in graph:
        for v in graph[u]:
            if not visited[v]:
                dfs(v)

2. DFS 함수이다.

res 에 방문한 정점을 저장하여 탐색 과정을 확인할 수 있도록 한다.

 

def bfs(start):
    queue = deque([start])
    visited[start] = True
    while queue:
        u = queue.popleft()
        res.append(u)
        if u in graph:
            for v in graph[u]:
                if not visited[v]:
                    visited[v] = True
                    queue.append(v)

3. BFS 함수이다.

res 에 방문한 정점을 저장하여 탐색 과정을 확인할 수 있도록 한다.

 

visited = [False for _ in range(n+1)]
res = []
dfs(start)
print(*(res))

visited = [False for _ in range(n+1)]
res = []
bfs(start)
print(*(res))

4. 방문, 결과 리스트 초기화 및 결과 출력

 

피드백

DFS, BFS 를 딕셔너리로 선언했을 때와 리스트로 선언했을 때, 어떠한 문제에서 딕셔너리를 사용하고 리스트를 사용하는지, 어떤 문제에서 DFS, BFS가 효율적인지 문제를 더 많이 풀어야겠다.