백준 1260 번 DFS와 BFS

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

1260번: DFS와 BFS

문제

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

입력

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

출력

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

 

풀이

단순하게 DFS, BFS 를 구현하면 되지만 방문가능 정점이 여러개일 경우 낮은것 부터 방문한다는 조건이 걸려있다.

 

이를 위해 DFS는 pop 한 노드(v)와 인접한 모든 정점을 정렬 한 후 reverse하여 스택에 집어넣었다.(코드:20번째줄)

이렇게 되면 스택은 마지막부터 빠지기 때문에 후에 가장 낮은수 부터 pop이 된다.

 

또한 이미 스택에 추가되어있다면

스택에 있던 요소를 제거하고 다시 맨뒤로 넣어주어야 조건을 만족한다. 그래야 낮은 수 부터 방문하게 된다.

(코드:24-26줄)

 

BFS는 단순 정렬만 낮은순 방문이 가능하다.

코드

#input setting
value=list(map(int,input().split()))
N=value[0]
V=value[1]
start=value[2]
graph=[[] for i in range(N+1)]
for _ in range(V):
    arr=list(map(int,input().split()))
    graph[arr[0]].append(arr[1])
    graph[arr[1]].append(arr[0])
 
def dfs(start):
    stack=[start]
    visited=[False for i in range(N+1)]
    result=[]
    while stack:
        v=stack.pop()
        result.append(v)
        visited[v]=True
        node=sorted(graph[v],reverse=True)
        for i in node:
            if not visited[i] and i not in stack:
                stack.append(i)
            elif not visited[i] and i in stack:
                del stack[stack.index(i)]
                stack.append(i)
    return result
 
def bfs(start):
    queue=[start]
    visited=[False for i in range(N+1)]
    result=[]
    while queue:
        v=queue.pop(0)
        result.append(v)
        visited[v]=True
        node=sorted(graph[v])
        for i in node:
            if not visited[i] and i not in queue:
                queue.append(i)
    return result
 
d=""
for i in dfs(start):
    d+=str(i)+" "
b=""
for i in bfs(start):
    b+=str(i)+" "
print(d[:-1])
print(b[:-1])