[백준] 1260: DFS와 BFS

안녕하세요. 이번 문제는 DFS와 BFS 입니다.

너무 기본적인 문제라서 설명이랄게 없는데요.

그냥 BFS-DFS 개념을 알게돼서 기분이 좋아서 포스팅 하는 것 같습니다.

 

인접 행렬 방식이 아닌 인접 리스트 방식으로 풀었습니다.

 

문제는 https://www.acmicpc.net/problem/1260 입니다.

 

문제 핵심

- DFS와 BFS를 구현하는 것 (정석)

- 간선이 주어지지 않은 노드도 탐색할 수 있도록 할 것 (input이 그렇게 주어지더라구요)

  - 그러니까 n이 5고, 간선은 1이라면 1-2-3-4-5 모두 최초 조회 자체는 대응 가능하게 짜둬야 합니다.

 

코드

import sys
from collections import deque

graph = dict()
visited = set()
dfs_result = []

def dfs(node):
    if node in visited:
        return

    visited.add(node)
    dfs_result.append(node)

    for neighbor in graph[node]:
        dfs(neighbor)

def bfs(start_node):
    bfs_result = []
    q = deque([start_node])
    visited_bfs = set([start_node])

    while q:
        node = q.popleft()
        bfs_result.append(node) 
    
        for neighbor in graph[node]:
            if neighbor not in visited_bfs:
                q.append(neighbor)
                visited_bfs.add(neighbor)

    return bfs_result


input = sys.stdin.readline

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

for i in range(n):
    graph[i+1] = [] # n만큼 그래프 값 초기화

for _ in range(m):
    a,b = map(int, input().rstrip().split())

    graph[a].append(b)
    graph[b].append(a)

for nodes in graph.values():
    nodes.sort()

dfs(v)

print(*dfs_result, sep=" ")
print(*bfs(v), sep=" ")

 

 

여담

(진짜 여담)

 

아이작 도전과제 중에 Ultra Hard를 깨보려고 몇시간 내내 노력했는데 너무 힘들었습니다.

황금방 나올때마다 별로면 돌리고 악마방 못가면 돌리고.. 계속 돌렸는데 쉽지 않았습니다.

일단 다른 도전과제 다 깨고 다시 하는걸로.. 절대 도망치는게 아닙니다....