[Algorithm 개념] DFS / BFS

1. DFS (Depth-First-Search)

스택 자료 구조 이용하거나 재귀 함수를 이용.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다.

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

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

#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,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False] * 9

dfs(graph, 1, visited)

문제 1. 음료수 얼려먹기

N * M 크기의 얼음 틀이 있습니다. 구멍이 뚫려있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시. 구멍이 뚫려있는 부분끼리 상,하,좌,우 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성한다. 

# 입력
# 4 5
# 00110
# 00011
# 11111
# 00000 

* 문제 해결 아이디어
1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문.
2. 방문한 지점에서 다시 상,하,좌,우를 살펴보면서 방문을 진행하는 과정을 반복하면, 연결된 모든 지점을 방문할 수 있다.
3. 모든 노드에 대하여 1~2번의 과정을 반복하며, 방문하지 않은 지점의 수를 카운트.

코드

def dfs(x, y):
    # 주어진 범위를 벗어나면 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    
    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
    
# n, m을 공백을 기준으로 구분하여 입력 받기.
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기.
graph = []
for i in range(n):
    graph.append(list(map(int, input())))
    
# 모든 노드에 대하여 음료수 채우기
result = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            result += 1
            
print(result)

 

2. BFS  (Breadth-First-Search)

그래프에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘. 큐 자료구조를 이용. 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 처리.

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

 

문제 2. 미로 탈출

동빈이는 N * M 크기의 직사각형 형태의 미로에 갇혔습니다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1, 1) 이며 미로의 출구는 (N, M) 의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0이며, 괴물이 없는 부분은 1로 표시되어 있다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 

(칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산)

# 5 6
# 101010
# 111111
# 000001
# 111111
# 111111

코드

from collections import deque
def bfs(x, y):
    queue = deque()
    queue.append((x,y))
    
    while queue:
        x, y = 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:
                continue
            
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append(nx, ny)
                
    return graph[n-1][m-1]
                
        
        
# n, m을 공백을 기준으로 구분하여 입력 받기.
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기.
graph = []
for i in range(n):
    graph.append(list(map(int, input())))
    
#이동할 네가지 방향
dx = [-1,1,0,0]
dy = [0,0,-1,1]

#수행한 결과 출력.
print(bfs(0,0))