[Coding Test] 1260번, DFS와 BFS(백준, Python)

이번에는 저번 포스팅에서 DFS와 BFS를 간단하게 살펴보고 구현까지 해보았다.

그래서 이를 응용을 어떻게 하는지 살펴보기 위해 백준의 'DFS와 BFS' 문제(1260)를 풀어보았다.

구현은 재귀함수 형태로 구현을 했다. 우선 문제를 살펴보자.

문제

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

 

입력

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

 

출력

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

입출력 예시

예시1

예시2

코드

node, edge, start_node = map(int,input().split())

#행렬 만들기
matrix = [[0]*(node+1) for _ in range(node+1)]
for i in range (M):
    a,b = map(int,input().split())
    graph[a][b] = graph[b][a] = 1

#방문 리스트 행렬
visited_dfs = [0]*(node+1)
visited_bfs = visited1.copy()

#dfs 함수 만들기(재귀함수 사용)
def dfs(start_node):
	# 시작 node 방문으로 설정
    visited_dfs[start_node] = 1 
    print(start_node, end=' ')
	# 행렬과 반복문을 이용해 다음 node 방문
    for i in range(1, node+1):
		# edge가 연결되어 있고, 아직 방문하지 않았으면 재귀함수를 이용해 다음 노드 방문
        if matrix[start_node][i] == 1 and visited_dfs[i] == 0:
            dfs(i)

#bfs 함수 만들기
def bfs(start_node):
    queue = [start_node]
	# 시작 node를 방문처리
    visited_bfs[start_node] = 1 #방문처리
    while queue:
		# 방문 노드를 queue에서 제거
        start_node = queue.pop(0)
        print(start_node, end = ' ')
		# 행렬과 반복문을 이용해 다음 node 방문
        for i in range(1, node+1):
			# edge가 연결되어 있고, 아직 방문하지 않으면, 방문목록으로 queue에 저장 후, 방문으로 처리
            if(matrix[start_node][i] == 1 and visited_bfs[i] == 0):
                queue.append(i)
                visited_bfs[i] = 1

dfs(start_node)
print()
bfs(start_node)

 

문제를 풀면서 느낀 것은 이론적으로 공부를 하고, 구현을 할 때의 느낌과 이를 다양한 input에 적용시킬 때의 느낌이 약간의 이질감이 들게된다. 이를 최대한 좁혀 나가기 위해 좀 더 다양한 문제를 접근해보고 쉬운 문제들을 풀며, list와 matrix등을 다루는데 더 익숙해질 필요가 있을 것 같다. 백준 문제로 접근을 하는 것도 좋지만 쉬운 문제인 프로그래머스를 풀며 빠르게 코드를 작성하는 것도 연습할 필요가 있어보인다.