백준 1260 파이썬 (DFS/BFS)

가장 기본적이고 DFS/BFS 개념문제라고 생각한다.

 

DFS는 깊이우선탐색이라고 하여 

그래프 자료구조를 그려놓고 수직의 방향으로 먼저 탐색하는 방법을 말한다.

재귀 혹은 스택 자료구조를 이용하여서 구현할 수 있다.

 

BFS는 넓이우선탐색이라고 하여

그래프에서 수평방향으로 먼저 탐색하는 방법이라고 이해하면 될것 같다.

큐 자료구조를 이용하여 구현한다.

---

# 1260번

# 입력값을 받는 부분
# 인접행렬로 그래프를 표현하였다.
n,m,v = map(int,input().split())
graph = [[0]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    a,b = map(int,input().split())
    graph[a][b] = graph[b][a] = 1

# DFS구현
visited_dfs = [0]*(n+1)
def dfs(v):
    visited_dfs[v] = 1                         # 방문처리
    print(v,end=' ')                         
    for i in range(n+1):
        if visited_dfs[i]==0 and graph[i][v]:  # 방문했었는지, 그리고 간선이 있는지 확인
        dfs(i)                                 # 재귀함수 호출
dfs(v)

# BFS구현
visited_bfs = [0] * (n+1)
from collections import deque
def bfs(v):
    visited_bfs[v] = 1                         # 방문처리
    queue = deque()
    queue.append(v)                            # 큐에 노드 삽입
    while queue:                               # 큐에 노드가 없을때까지 반복
        node = queue.popleft()                 # 큐에서 빼주기
        print(node,end=' ')
        for i in range(n+1):
            if visited_bfs[i] == 0 and graph[i][node]: # 방문했었는지, 그리고 간선이 있는지 확인
                queue.append(i)                        # 큐에 노드 삽입
                visited_bfs[i] = 1                     # 방문처리
print()
bfs(v)

 

탐색 알고리즘과 DFS/BFS를 공부하면서 느낀점은

처음엔 그냥 외워버려야지 라는 생각으로 공부했었는데 여러 문제를 풀고 책을 보다보니

문제별로 상황별로, 입출력 조건별로 코드가 다 제각각 다르고 그때그때 맞춰서 코딩해야 한다는 것이다.

핵심을 이해하고 나머지는 상황에 맞추는게 필요하다.

 

핵심은 

DFS는 재귀를 이용해서 구현한다는 점,

BFS는 큐에 노드들을 넣고 빼고 하면서 큐가 빌때까지 반복문을 돌린다는 점이 제일 핵심인듯 하다.

그리고 무한루프에 빠지지 않기 위해서는 언제나 base case에 대한 처리를 해줘야 한다(방문처리)

---

참고로 다른 문제이지만 DFS에서 스택을 이용해서 구현할때랑 재귀함수를 이용해서 구현할 때 탐색의 순서가 다를수 있다는 점도 알게 되었다.

재귀로만 구현해보다가 스택으로 구현했을때 

어? 뭐가 좀 다른데 이게 맞는건가? 싶었는데

위에서 말했듯이 DFS의 핵심은 위아래로 먼저 탐색한다는 점이다.

그래서 순서가 다르더라도 두개 모두 DFS알고리즘이라고 할 수 있다.

# 재귀함수를 이용해서
def dfs_recur(node, dfs_graph, dfs_list=[]):
    dfs_list.append(node)  
    for i in dfs_graph[node]:   
        if i not in dfs_list:
            dfs_recur(i,dfs_graph,dfs_list)
    return dfs_list

if __name__ == '__main__':
    # 여기서는 인접리스트 방식으로 그래프를 표현하였다.
    # 이렇게 문제마다 약간씩 조건들이 다르다.
    dfs_graph = {
        1: [2,3,4],
        2: [5],
        3: [6],
        4: [],
        5: [7],
        6: [5],
        7: [6],
    }
    print(dfs_recur(1, dfs_graph, dfs_list=[]))
    
    #결과 => [1, 2, 5, 7, 6, 3, 4]

 

# 스택을 활용한 DFS 구현하기 
def dfs_stack(start_node, dfs_graph):
    dfs_list = []
    stack_list = [start_node]
    while stack_list:
        node = stack_list.pop() # 리스트 메소드        
        if node not in dfs_list:
            dfs_list.append(node)
            stack_list.extend(dfs_graph[node])
    return dfs_list 

if __name__ == '__main__':
    # 인접리스트 방식
    dfs_graph = {
        1: [2,3,4],
        2: [5],
        3: [6],
        4: [],
        5: [7],
        6: [5],
        7: [6],
    }
    print(dfs_stack(1, dfs_graph))
    
# 결과 => [1, 4, 3, 6, 5, 7, 2]