[백준 알고리즘/Python] 1260 DFS와 BFS

문제

 

문제 이해

DFS는 스택으로 BFS는 큐로 해결할 수 있습니다.

컴퓨터 내부에서 재귀함수의 수행은 스택 자료구조를 이용합니다. 함수를 계속 호출했을 떄 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료가 됩니다.

즉, 제귀로 깔끔한 코드를 짤 수 있습니다.

 

먼저 DFS 코드입니다.

#DFS 메서드 정의
def dfs(graph, v, visited):
    #현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

여기서 graph는 2차원 배열입니다.

• 처음에 시작인 v노드를 거치고
• graph배열 안에 있는 주변 노드를 검색합니다.
• 만약 방문(visited[]에 True)했다면 건너 뛰고
• 아니라면 제귀를 호출해 스택에 넣습니다.

 

BFS 코드입니다.

#BFS 메서드 정의
def bfs(graph, start, visited):
    #큐 구현을 위해 deque 사용
    queue = deque([start])
    #현재 노드를 방문 처리
    visited[start] = True
    #큐가 빌때 까지 반복
    while queue:
        #큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        #해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

이건 큐를 이용합니다. 

• 큐에 start 노드를 집어 넣습니다.
• 그리고 방문했다고 도장을 찍습니다.
• 이제 큐에서 작업을 시작합니다. 큐가 비어있다면 탐색을 마친겁니다.
• 큐에서 하나를 뽑습니다. 파이선 list는 오른쪽에서만 들어가고 오른쪽에서만 뺄 수 있는데, deque는 왼쪽에서 뽑을 수 있게 popleft를 지원합니다. 우리는 큐를 사용하기 때문에 먼저들어온것(왼쪽)을 뽑아야 합니다.
• 하나 뽑은것의 주변을 (graph[]) 살펴봅니다. 주변에 도장이 찍혀 있다면 넘어가지만
• 안찍혀 있다면 큐의 집어 넣습니다. (이 때는 오른쪽으로 들어갑니다.)
• 큐에 집어넣음과 동시에 도장을 찍습니다.

주변에 있는 모든것을 큐에 넣는다는 계념을 배웟습니다.

 

전체 코드

from collections import deque

N, M ,V = map(int,input().split())

#DFS 메서드 정의
def dfs(graph, v, visited):
    #현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

#BFS 메서드 정의
def bfs(graph, start, visited):
    #큐 구현을 위해 deque 사용
    queue = deque([start])
    #현재 노드를 방문 처리
    visited[start] = True
    #큐가 빌때 까지 반복
    while queue:
        #큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        #해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [[] for _ in range(N+1)] 
for i in range(M):
    node, link = map(int,input().split())

    graph[node].append(link)
    graph[link].append(node)
    graph[node].sort()
    graph[link].sort()

#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * int(N+1)

#정의된 DFS 함수 호출
dfs(graph, V, visited)

visited = [False] * int(N+1)
print()

#정의된 bfs 함수 호출
bfs(graph, V, visited)

사실 graph계념을 정리해는데 어려웟씁니다. 하나의 노드에만 연결관계를 알려주니 길이 끊기는 일이 있더군요. 노드의 관계를 설정할 때 양 노드 모두에게 연결이 되었다는 것을 설정해야 합니다.

여기서는 append()할 때 양쪽 모두에게 넣었습니다.

그리고 작은 것 부터 순서대로 탐색을 해야하니 sort()를 사용했습니다. 이러면 숫자가 작은것 부터 정렬이 됩니다.