[알고리즘] python - DFS/BFS

탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조

 

- 스택 : 선입후출 First In Last Out

- 큐 : 선입선출 First In First Out

 

DFS(Depth-First Search) : 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

 

 - 인접 행렬(Adjacency matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식이다. 구현은 스택 자료구조에 기초한다.

 - 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식

 

두 방식을 메모리와 속도 측면에서 살펴보자. 메모리 측면에서, 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다. 반면에 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용할 수 있다. 하지만 이와 같은 속성 때문에 인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. 

 

BFS(Breadth First Search) : 너비 우선 탐색이라는 의미를 가지며, 가까운 노드부터 탐색하는 알고리즘이다. 구현은 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 

 

 

3. 음료수 얼려 먹기

▶ 입력 조건

 - 첫 번째 줄에 얼음 틀에 세로 길이 N과 가로 길이 M이 주어진다. (1≤N, M≤1,000)

 - 두 번째 줄부터 N+1번재 줄까지 얼음 틀의 형태가 주어진다.

 - 이때 구멍이 뚫려있는 부분은 0 , 그렇지 않은 부분은 1이다.

 

▶ 출력 조건

 - 한 번에 만들 수 있는 아이스크림의 개수를 출력한다. 

 

n, m = map(int, input().split())

graph = []
for i in range(n) :
    graph.append(list(map(int, input())))
        
def dfs(x,y) :
	#범위 벗어난 부분 도착하면 False
    if x<= -1 or x>=n or y<= -1 or y>=m :
        return False
    
    # 0부분에 도착하면 해당 부분 1로 바꾸고, 동서남북 모두 검사한다. 
    if graph[x][y] == 0 :
        graph[x][y] == 1
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        return True
    return False
    

count = 0
for i in range(n) :
    for j in range(m) :
        if dfs(i,j) == True :
            count += 1
print(count)

DFS 알고리즘을 사용하여, 간단하게 해결할 수 있다. 

 

 

4. 미로 탈출

▶ 입력 조건

 - 첫째 줄에 두 정수 N, M(4≤N, M≤200)이 주어집니다. 다음 N개의 줄에는 각각 M개의 정수( 0 혹은 1 )로 미로의 정보가 주어진다.     각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

 

▶ 입력 조건

 - 첫째 줄에 최소 이동 칸의 개수를 출력한다.

 

from collections import deque

n, m = map(int, input().split())

graph = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


for i in range(n) :
    graph.append(list(map(int, input())))
    
        
def bfs(x,y) :
    queue = deque()
    queue.append([x,y])
    
    while queue :
        queue.popleft()
        
        
        for i in range(4) :
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= n or ny < 0 or ny >= m or graph[nx][ny] == 0:
                continue
            
            elif graph[nx][ny] == 1 :
                graph[nx][ny] = graph[x][y] + 1
                queue.append([nx,ny])
                
    return graph[n-1][m-1]

print(bfs(0,0))

해당 문제는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문에, BFS를 사용하여 해결할 수 있다.