1260

1260

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 

단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 

더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 

탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 

어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. 

V부터 방문된 점을 순서대로 출력하면 된다.

 

 

 

- 자주 쓰이는 DFS와 BFS를 공부하고자 해당 문제를 풀어보고자 하였다.

 

먼저 BFS가 쉬워 보여서 먼저 풀어 보고자 한다.

BFS는 처음에 제대로 풀었으나 DFS의 경우에는 생각이 나질 않았다.

그래서 찾아보니 이렇다고 하였다.

DFS(깊이 우선 탐색, Depth-First Search)	BFS(너비 우선 탐색, Breadth-First Search)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐를 이용해서 구현

그러나 스택이나 재귀로 풀기에도 힘들다고 판단이 되어서 답을 찾아 보게 되었다.

 

def dfs(v):
	# 프린트 
    print(v, end=' ')
    # V점을 방문하였으니 표시
    visit[v] = 1
    # 각 점이 이어져있나 보기
    for i in range(1, n + 1):
    	# 방문을 안했고 연결이 되어있으면
        if visit[i] == 0 and s[v][i] == 1:
        	# 깊이가 우선이기 때문에 다시 그 연결된 점에서 DFS를 적용
            dfs(i)

def bfs(v):
	# Q에 점을 넣는다. 이는 BFS를 하기위한 준비 과정
    queue = [v]
    # V점 방문
    visit[v] = 0
    # 이제 Q를 보면서 
    while(queue):
    	# Q에서 저장하고
        v = queue[0]
        # 출력
        print(v, end=' ')
        # Q에서 앞점을 뺀다.
        del queue[0]
        # 점을 이 연결되어 있나 판단.
        for i in range(1, n + 1):
        	# DFS에서 먼저 방문하여 VISIT가 1이고 연결되어 있는지 판단.
            if visit[i] == 1 and s[v][i] == 1:
            	# 연결되어 있으면 그 점을 Q에 넣고 
                queue.append(i)
                # 방문을 하였다고 표시
                visit[i] = 0
           # 이를 반복하면서 한 깊이마다 출력하고 그와 연결된 점을 계속 Q에 넣어서 넓이를 기준으로 방문한다.


n, m, v = map(int, input().split())
s = [[0] * (n + 1) for i in range(n + 1)]
visit = [0 for i in range(n + 1)]
for i in range(m):
    x, y = map(int, input().split())
    s[x][y] = 1
    s[y][x] = 1
    
dfs(v)
print()
bfs(v)

 

자주 쓰이는 BFS, DFS를 공부하였고 다른 문제에도 자주 쓰일 것으로 판단되니 관련 문제들을 풀어 보면서 계속 학습해봐야겠다.

 

DFS - 스택 OR 재귀

BFS - QUEUE