DFS+BFS 필수 문제 - DFS와 BFS
| 단계 | 제목 | 설명 | |
|---|---|---|---|
| 소단계 | 문제번호 | 제목 | |
| 1260 | DFS 와 BFS |
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
내 제출
미제출
결과
수정 제출
from collections import deque
N, M, V = map(int, input().split())
graph = [[False] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
a, b = map(int, input().split())
graph[a][b] = True
graph[b][a] = True
visited1 = [False] * (N + 1) # dfs의 방문기록
visited2 = [False] * (N + 1) # bfs의 방문기록
# deque 사용
def bfs(V):
q = deque([V]) # pop메서드의 시간복잡도가 낮은 덱 내장 메서드를 이용한다
visited2[V] = True # 해당 V 값을 방문처리
while q: # q가 빌때까지 돈다.
V = q.popleft() # 큐에 있는 첫번째 값 꺼낸다.
print(V, end=" ") # 해당 값 출력
for i in range(1, N + 1): # 1부터 N까지 돈다
if not visited2[i] and graph[V][i]: # 만약 해당 i값을 방문하지 않았고 V와 연결이 되어 있다면
q.append(i) # 그 i 값을 추가
visited2[i] = True # i 값을 방문처리
# 재귀함수 사용
def dfs(V):
visited1[V] = True # 해당 V값 방문처리
print(V, end=" ")
for i in range(1, N + 1):
if not visited1[i] and graph[V][i]: # 만약 i값을 방문하지 않았고 V와 연결이 되어 있다면
dfs(i) # 해당 i 값으로 dfs를 돈다.(더 깊이 탐색)
dfs(V)
print()
bfs(V)
결과
정답
코드 해석
우선 N = 6, M = 5, V = 1 인 케이스를 생각해보자
DFS (재귀함수 사용)
위와 같은 경우에 dfs 의 알고리즘의 경우 2차원 리스트를 만들고 이때 0행 0열의 값들은 전부 쓰이지 않는 값들이다.
이 graph 이중 리스트의 경우에는 각 node 들의 연결상태를 표현하는데 사용되며
True : 연결 False: 단락 으로 생각한다.
이 이후에 나오는 visited 리스트는 각 node 들의 방문여부를 파악하는데 사용되며 역시 True: 방문 , False: 미방문 으로 나뉠 수 있다.
이를 통해 마지막 부분에
def dfs(V):
visited1[V] = True # 해당 V값 방문처리
print(V, end=" ")
for i in range(1, N + 1):
if not visited1[i] and graph[V][i]: # 만약 i값을 방문하지 않았고 V와 연결이 되어 있다면
dfs(i) # 해당 i 값으로 dfs를 돈다.(더 깊이 탐색)
의 visited1[i] 가 False 일때 그리고 graph[V][i] (현재 node 에서 오름차순 1 2 3 4 순으로 연결 여부를 파악하고, 현재 node에서 그리고 연결 브릿지가 존재한다 = True) 가 True 이면 해당 Node 로 이동하고 다시 dfs 를 수행하며, 이때 dfs 의 전단계 step 은 저장된 상태 그대로 존재하며 이는 다음에 수행하는 dfs 함수가 None 값을 반환하는 경우에 다시 for 문을 돌려주게 된다.
-> 재귀함수
이렇게 각각 수행하는 단계마다, print(V) 를 삽입하여 각 방문node 들을 출력해주도록 한다.
BFS
처음 방문하게 되는 node 를 deque 에 삽입시켜주고 그 값의 visited2 를 True 처리해준다.
그리고 while 구문에서 q 조건을 걸고 루프를 돌려준다.(q 가 빈 리스트이면 break된다.)
node 끼리 브릿지로 이어진 부분마다 연결되며 각 연결된 node 들은 deque 에 삽입된다.
두개 이상의 node 가 연결된 경우 오름차순의 순서로 저장되며, 추후에 값을 빼낼때도 같은 순서로 빠진다.
(deque 의 특성상 내림차순으로 pop()을 할 수있지만, 이번 문제와는 성격이 안맞는다.)
현재 node 2 의 방문가능 루트를 탐색중이다.
이때 맨 처음에 시작한 node 1 에서 node 2 node 6 을 먼저 발견했다.
따라서 node 2의 탐색이 종료된 후엔
node 6의 탐색을 시작하며 이것이 deque 의 맨앞에 6이 있는 이유이다.
모든 탐색이 종료된 후에는 빈 deque 를 가지게 되고 이 조건때문에 while 문을 탈출할 수 있게 된다.
return 값을 지정해주지 않은 def 이므로 None 값을 리턴해주며 종료되고
결과가 출력된다.
참고로 deque 에서 요소값을 출력할때는 리스트와 같이 출력해도 되고, popleft(),pop() 을 사용하고 그것을 바로 print 해도 값은 같다.
-> 문제 내용 파악
이번문제에서는 dfs 와 bfs 의 기초적인 코드와 작동 알고리즘에 대한 이론적인 부분을 주로 살펴보는 문제였다.
문제에서 요구하는 출력기준은 중복된 점을 제외하고, 방문된 순서대로 점을 출력하는것이다.
이때 dfs 에서는 재귀함수를 사용하여 해결하였고
bfs 에서는 deque 를 사용하였다.
우선적으로 재귀함수에 대한 내용을 알아보도록 하자.
사용된 코드 이론
재귀함수는 함수속 함수(Function in Function)의 종류중 하나로 다른 함수로는 중첩함수 가 있다.
중첩함수는 자기 이외의 함수를 불러온다는 특징이 있고, 재귀함수는 자기자신을 호출한다는 특징이 있으며 이때 위의 코드에서는 지정된 함수에서 return 을 선언해주지 않았으므로 파이썬에서 자체적으로 return None 으로 인식하고 동작한다.
따라서 재귀함수는 hierarchy 적인 특징을 가지며, 각 재귀단계가 종료될때의 return 을 상위 함수로 return 시켜주며 이때 for 문이 있을 경우 각 계층에서의 과정을 마저 진행하게 된다.
이번 포스팅에서는 Python의 함수 중에서도 ‘함수 안의 함수 (Function in Function)’ 로서
-
(1) 중첩 함수 (Nested Function): 함수 안에 정의된 함수
-
(2) 재귀 함수 (Recursive Function): 함수 안에 자기 자신을 호출하는 함수
에 대해서 알아보겠습니다.
[ Python 함수 안의 함수 (Function in Function) ]
(1) 중첩 함수 (Nested Function): 함수 안에 정의된 함수
def 로 시작하는 함수 안에 또 다른 하나의 def 로 시작하는 함수를 정의할 수 있는데요, 이때 함수 안에 정의된 또 다른 함수를 중첩 함수 (Nested Function) 이라고 합니다.
중첩 함수는 자기가 속한 원래 함수의 매개변수를 받아서 사용할 수 있습니다. 아래의 예시는 outer() 함수의 num 매개변수를 중첩함수인 inner() 함수의 매개변수 input 으로 사용해서 최종 결과값인 result2 를 반환하도록 하는 함수입니다.
(2) 재귀 함수 (Recursive Function): 함수 안에 자기 자신을 호출하는 함수
재귀 함수(Recursive Function)는 함수 안에서 자기 자신을 호출하는 함수를 말합니다.
함수가 호출자이자 동시에 피호출자가 되어서 반복에 반복에 반복을 계속하는 함수입니다.
왼쪽의 사진을 보면 재귀함수가 자기 자신을 계속해서 반복하면서 호출을 하는 것이 무엇을 의미하는지 이해가 될 것 같습니다.
(*출처: http://www.itcuties.com/java/recursion-and-iteration/)
재귀함수(recursive function)와 중첩함수(nested function)를 같이 이용해서 Factorial 계산하는 함수를 정의해보겠습니다.
위의 factorial(5) 함수를 실행하면 아래에 각 절차를 풀어서 설명해 놓은 것과 같이 자기 자신의 factorial() 함수를 계속 반복해서 호출하면서 값을 계산해서 최종값을 반환하게 됩니다.
재귀함수는 편리한 점도 있지만 호출 비용이 크므로 성능이 중요한 경우에는 재귀함수 대신 반복문을 사용하는 것이 좋겠습니다. 그리고 재귀함수를 짤 때는 반드시 종료 조건을 정의해 주어야 무한반복의 함정에 빠지지 않습니다. (파이썬이 지정해 놓은 재귀 함수 반복 호출 최대 회수를 초과하면 ‘RuntimeError: maximum recursion depth exceeded while calling a Python object’ 에러가 발생합니다)
많은 도움이 되었기를 바랍니다.