백준 - 1260번(DFS,BFS)

DFS와 BFS는 해당 블로그에서도 한번 정리한 적 있고 이 문제도 아이디어를 떠올린 후 기본 구현법만 알면 쉽게 풀 수 있다.

 

핵심 아이디어는 입력받는 그래프의 구조를 재배열 는 것이다.

 

에를 들어 [1,2], [1,3], [1,4], [2,4], [3,4] 이렇게 전달을 받았다고 가정한다.

이를 다시 정리해서 첫번째 배열 자리에는 2,3 // 두 번째 배열 자리에는 1,4 이런 식으로 n번째 원소의 자리가 연관되어 있는 숫자들이 오도록 재배치해서 정렬해주는 것이다. 또한 문제 조건에서 작은 수 먼저 탐색하는 조건을 붙여줬으니 오름 차순으로 정렬한다.

전체 코드는 아래와 같다.

 

import sys
from collections import deque

n, m, v = map(int,sys.stdin.readline().split())

arr = [[] for i in range(n+1)]

p1 = []
p2 = []
dfs_ans = [False] * (n+1)
bfs_ans = [False] * (n+1)

for i in range(m): #입력 받은 배열 재배치
    temp = list(map(int,sys.stdin.readline().split()))
    if temp[0] not in arr[temp[1]]:
        arr[temp[1]].append(temp[0])
    if temp[1] not in arr[temp[0]]:
        arr[temp[0]].append(temp[1])

for i in range(len(arr)):
    arr[i].sort() #작은 것 우선 탐색하기위해서 오름차순으로 정렬

def DFS(graph, start, visited, pt):
    visited[start] = True
    pt.append(start)

    for j in graph[start]:
        if visited[j] == False:
            DFS(graph,j,visited,pt)

def BFS(graph, start, visited, pt):
    q = deque([start])
    visited[start] = True

    while q:
        v = q.popleft()
        pt.append(v)
        for i in graph[v]:
            if visited[i] == False:
                q.append(i)
                visited[i] = True


DFS(arr,v,dfs_ans,p1)
BFS(arr,v,bfs_ans,p2)

print(*p1)
print(*p2)