[백준 1260] DFS와 BFS with Python

🔗 문제 링크

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

1260번: DFS와 BFS

✏️ 풀이

import sys
from collections import deque

class Graph:
    def __init__(self, n):
        self.graph = {x:[] for x in range(1, n+1)}

    def add(self, start, end):
        self.graph[start].append(end)
        self.graph[end].append(start)

    def dfs(self, start):
        for i in self.graph:
            self.graph[i].sort(reverse=True)
        visited = []
        stack = deque([start])

        while stack:
            cur_node = stack.pop()
            if cur_node not in visited:
                stack += self.graph[cur_node]
                visited.append(cur_node)
                
        return " ".join(map(str, visited))

    def bfs(self, start):
        for i in self.graph:
            self.graph[i].sort()
        visited = [start]
        queue = deque([start])
        while queue:
            cur_node = queue.popleft()
            for i in self.graph[cur_node]:
                if i not in visited:
                    queue.append(i)
                    visited.append(i)
                    
        return " ".join(map(str, visited))

N, M, V = map(int, sys.stdin.readline().split())
my_graph = Graph(N)
for _ in range(M):
    start, end = map(int, sys.stdin.readline().split())
    my_graph.add(start, end)

print(my_graph.dfs(V))
print(my_graph.bfs(V))

먼저 Graph 클래스를 만들고 초기화된 self.graph에 add를 통해 그래프를 구현한다.

 

문제의 조건에 방문할 수 있는 정점이 여러 개인 경우에 정점 번호가 작은 순서대로 방문한다고 하여 dfs와 bfs 내부에서 먼저 인접 정점 리스트들(self.graph의 value들)을 정렬한다.

 

dfs는 stack을 활용하여 stack의 마지막 정점을 제거하고 첫 방문이면 그 정점의 인접 정점들을 다시 stack에 추가하기를 반복한다.

 

bfs는 queue를 활용하여 queue의 첫 정점을 제거하고 그 정점의 인접 정점들 중 아직 방문하지 않은 곳들을 queue에 추가하기를 반복한다.

 

 

🗃️ 다른 언어로 된 풀이

[백준 1260 - Node.js] DFS와 BFS