백준 - 1260번 DFS와 BFS python 문제풀이 [Hellfer]

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

🔷 알고리즘 분류 - 너비우선탐색, 깊이우선탐색 

난이도 - 실버 2

너비 우선 탐색(Breadth-First Search, BFS) 알고리즘은 그래프 또는 트리를 탐색하는 방법 중 하나로, 시작 노드에서 가장 가까운 노드부터 탐색하는 방법입니다. BFS는 '레벨(level)'이 같은 노드들을 모두 탐색한 후에 다음 레벨의 노드들을 탐색하게 됩니다.

BFS는 큐(Queue) 자료구조를 이용해서 구현됩니다. 큐는 '선입선출(FIFO, First-In-First-Out)'의 특성을 가지므로, 먼저 들어간 노드가 먼저 나오게 됩니다. 이 특성을 이용하여 BFS는 시작 노드부터 가까운 노드를 먼저 탐색하는 방식을 구현하게 됩니다.

다음은 BFS 알고리즘의 기본적인 순서입니다:

1. 시작 노드를 큐에 넣고 방문 처리를 합니다.

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 넣고 방문 처리를 합니다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.

BFS는 최단 경로 문제에서 많이 사용되며, 또한 네트워크에서 가장 가까운 노드를 찾는 등의 문제에서도 사용됩니다. 이는 BFS가 시작 노드에서 가장 가까운 노드부터 탐색하기 때문입니다. 하지만 BFS는 모든 간선의 비용이 동일할 때만 최단 경로를 보장하므로, 간선의 비용이 다른 경우에는 다른 알고리즘(예: 다익스트라 알고리즘)을 사용해야 합니다.

 

깊이 우선 탐색(Depth-First Search, DFS) 알고리즘은 그래프나 트리를 탐색하는 방법 중 하나로, 현재 노드와 인접한 노드를 재귀적으로 탐색하는 방법입니다. DFS는 현재 경로상의 노드들만을 기억하면 되므로, 저장 공간의 수요가 비교적 작습니다. 또한, 목표 노드가 깊은 단계에 있다면 너비 우선 탐색 방법보다 빠르게 도달할 수 있습니다.

DFS는 스택(Stack)이나 재귀 함수를 이용해 구현할 수 있습니다. 스택은 '후입선출(LIFO, Last-In-First-Out)'의 특성을 가지므로, 마지막에 들어간 노드가 먼저 나오게 됩니다. 이 특성을 이용하여 DFS는 현재 노드와 인접한 노드를 먼저 탐색하는 방식을 구현하게 됩니다.

다음은 DFS 알고리즘의 기본적인 순서입니다:

1. 시작 노드를 스택에 넣고 방문 처리를 합니다.

2. 스택의 최상단 노드에서 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문 처리를 합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.

DFS는 모든 노드를 방문하고자 하는 경우에 이용할 수 있습니다. 또한, DFS는 트리의 높이를 알고 싶을 때나, 사이클이 존재하는지 확인하고 싶을 때 등 다양한 문제에 활용될 수 있습니다.

🔶문제 풀이 - 너비우선탐색과 깊이우선탐색을 이용한 풀이

from collections import deque
n,m,v=map(int,input().split())
graph=[[False]*(n+1) for _ in range(n+1)] # n+1 크기의 2차원 리스트를 생성하여 그래프를 표현합니다. 
visited1=[False]*(n+1) # DFS를 위한 방문 여부를 저장하는 리스트입니다.
visited2=[False]*(n+1) # BFS를 위한 방문 여부를 저장하는 리스트입니다.
for i in range(m) :
    x,y=map(int,input().split())
    graph[x][y]=1  # 노드 x와 y가 연결되어 있음을 표시합니다.
    graph[y][x]=1  # 노드 y와 x가 연결되어 있음을 표시합니다. (양방향)

def dfs(v) : # DFS 함수 정의
    visited1[v]=True # 방문한 노드를 표시합니다.
    print(v,end=' ') # 방문한 노드를 출력합니다.
    for i in range(1,n+1) : # 모든 노드를 순회합니다.
        if not visited1[i] and graph[v][i] : # 아직 방문하지 않았고, 연결되어 있는 노드라면
            dfs(i) # 해당 노드에 대해 DFS를 수행합니다.

def bfs(v) : # BFS 함수 정의
    queue=deque([v]) # BFS를 위한 큐에 시작 노드를 추가합니다.
    visited2[v]=True # 방문한 노드를 표시합니다.
    while queue : # 큐가 빌 때까지 반복합니다.
        v= queue.popleft() # 큐에서 노드를 하나 꺼냅니다.
        print(v,end=' ') # 방문한 노드를 출력합니다.
        for i in range(1,n+1) : # 모든 노드를 순회합니다.
            if not visited2[i] and graph[v][i] : # 아직 방문하지 않았고, 연결되어 있는 노드라면
                queue.append(i) # 해당 노드를 큐에 추가합니다.
                visited2[i]=True # 방문한 노드를 표시합니다.
dfs(v) # DFS를 수행합니다.
print() # 줄바꿈을 위해 print문을 추가합니다.
bfs(v) # BFS를 수행합니다.

 

🔶 초보자를 위한 생각주머니 키우기

🔸문제요약

 

이 문제는 그래프를 통해 주어진 시작점에서 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)를 수행하고, 각각의 방문 순서를 출력하는 것입니다. 노드의 개수, 간선의 개수, 그리고 시작점이 주어지며, 간선의 연결 정보도 입력으로 주어집니다.

🔸해결전략

1. 먼저 모든 정보를 입력받아 그래프를 구성합니다.

2. DFS와 BFS 각각에 대한 방문 여부를 저장하는 리스트를 만듭니다.

3. DFS와 BFS 알고리즘을 각각 구현합니다.

4. 주어진 시작점에서 DFS와 BFS를 수행하고, 방문 순서를 출력합니다.

🔸코드요약

1. deque 라이브러리와 입력값을 이용해 그래프와 방문 리스트를 초기화합니다.

2. DFS 함수는 재귀를 이용해 해당 노드와 연결된 노드를 깊이 우선으로 탐색하며 방문 순서를 출력합니다.

3. BFS 함수는 deque를 이용해 해당 노드와 연결된 노드를 너비 우선으로 탐색하며 방문 순서를 출력합니다.

4. 주어진 시작점에서 DFS와 BFS 함수를 호출하여 결과를 출력합니다.

 

🤗파이팅입니다~ 여러분!!🤗