[BOJ 1260번] DFS와 BFS

1. 문제

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

 

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

---

2. 문제 풀이

인접 리스트를 선언하여 각 그래프의 연결 정보를 저장한다(안그러면 순서 엉망됨)

 

DFS 문제 풀이 

• dfs함수에 graph, start, visited, order(연결 그래프, 시작 노드, 방문 여부, 순서 리스트)를 매개변수로 전달한다.
• 시작 노드의 방문 여부를 true로 변경하고, order 리스트에 노드를 추가한다.
• 인접 리스트에 저장되어 있는 연결 노드 정보를 기반으로, 노드의 방문 여부를 확인한다.
• 만약 인접한 노드에 방문한 적이 없다면, 해당 노드와 인접한 다른 노드의 정보를 수집하기 위해 재귀함수를 호출하여 연결 그래프를 탐색한다.

 

BFS 문제 풀이 

• 시작 지점을 미리 넣어둔 큐를 정의하고, 현재 노드의 방문 여부를 true로 변경한다. 
• 큐에 노드가 없을 동안 반복한다.
  • 큐의 가장 첫번째 원소를 pop하고, 해당 원소를 order 리스트에 추가한다.
  • 현재 노드와 인접한 노드의 방문 여부를 확인한다. 
  • 만약 방문하지 않은 노드가 있다면 해당 노드의 방문 여부를 true로 변경하고 노드의 연결 정보를 확인하기 위해 큐에 추가한다. 
• order 리스트를 반환한다 

import sys
from collections import deque


def dfs(node, start, visited, order):
    visited[start] = True
    order.append(start)
    
    for neighbor in sorted(node[start]):
        if not visited[neighbor]:
            dfs(node, neighbor, visited, order)
            

def bfs(node, start, visited):
    queue = deque([start])
    order = []
    visited[start] = True
    
    while queue:
        current = queue.popleft()
        order.append(current)
        
        for neighbor in sorted(node[current]):
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)
                
    return order 


N, M, V = list(map(int, sys.stdin.readline().split()))
graph = {i: [] for i in range(1, N+1)}

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
    
order = []
visited = [False] * (N+1)
dfs(graph, V, visited, order)
print(' '.join(map(str, order)))

visited = [False] * (N+1)
print(' '.join(map(str, bfs(graph, V, visited))))

 

 

---

 

완전 전형적인 dfs / bfs 문제였다~~

안푼지 너무 오래 되어서 재활할려고 문제 풀어봄 프로그래머스 전력망 나누기 문제랑 비슷했다(아무래도 그래프를 dfs로 탐방한다는 점에서..)

dfs 문제는 그래도 보면 딱 감잡고 대충이라도 구현할 줄 알겠는데 아직도 bfs는 애매한 느낌..더 많이 풀어봐야할듯? 

 

 

그리고 백준 골드 됨 ㅎㅋㅎㅋ

더 열심히 할게요..