[BOJ]1260. DFS와 BFS

문제:

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

입력:

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

출력:

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

풀이 방법:

양방향으로 이동가능이 하므로 2중배열로 만들어서 경로를 저장했다. 인덱스가 출발하는 정점이고 그 안에 들어있는 값들은 도착하는 정점이다.

DFS는 지금 마지막으로 들어온 정점이 중요하므로 그 정점이 가지고 있는 경로 중에 지나지 않은 곳으로 다시 들어가는 재귀방식으로 짜주면 된다.

BFS는 계속해서 배열을 누적하는 방식으로 진행했다. BFS에 계속 담아두고 반복문으로 하나하나 탐색하며 방문하지 않은 정점으로 이동하는 방식으로 진행했다. BFS에는 예외처리 구문이 들어가 있다. 왜냐하면 처음에는 없이 했더니 런타임에러가 발생하게 되었고, 그 이유를 알아보니 시작하는 정점이 1이라고 줬지만 1로 시작하는 정점이 없을 때 문제가 발생했다. 따라서 이 문제를 해결하기 위해 예외처리구문을 넣었다.

n,m,V=map(int,input().split())
path=[[]for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    if not a in path[b]:
        path[b].append(a)
    if not b in path[a]:
        path[a].append(b)
for p in path:
    p.sort()
 
DFS=[]
def dfs(now):
    DFS.append(now)
    for i in path[now]:
        if i in DFS:
            continue
        dfs(i)
    return
dfs(V)
print(*DFS)
def bfs(now):
    global BFS
    temp=[]
    if len(now)==n:
        return
    try:
        for i in now:
            for j in path[i]:
                if not j in BFS:
                    BFS.append(j)
        bfs(BFS)
    except:
        return
    return
BFS=[V]
bfs(BFS)
print(*BFS)