<PART 2> DFS/BFS 예제

<3> 음료수 얼려먹기

N X M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.

입력예시)
5 5
10101
00110
10101
01101
11111

출력예시)
5

#크기 입력받기
n,m = map(int,input().split())
#2차원 리스트의 맵 정보 입력 받기
graph =[]
for i in range(n):
    graph.append(list(map(int,input())))
count = 0
#dfs 정의
def dfs(x,y):
    if x <= -1 or y<=-1 or x>=n or y>=m:
        return False
    if graph[x][y] == 0:
        graph[x][y] = 1
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y-1)
        dfs(x,y+1)
        return True
    return False
 
for i in range(n):
    for j in range(m):
        # 현재 위치에서 dfs수행
        # if graph[i][j] == 0:  # 이 방법은 0인 곳에서만 dfs진행
        #     dfs(i,j)
        #     count += 1
        if dfs(i,j) == True: # 이 방법은 모든 위치에서 dfs 실행
            count += 1
print(count)
            

풀이: 이렇게 모든 맵을 한꺼번에 입력받고 시작위치가 모든 곳일 경우 깊이 우선 탐색인 DFS를 사용하는 것이 좋습니다. dfs이므로 재귀함수를 이용합니다. 자신의 위치에서 상하좌우를 1로 만들기 위해 재귀함수를 사용합니다.

배운 점: 이런 문제를 만나면 항상 어떻게 풀어야 할지 막막했다. dfs를 배움으로써 자신의 위치에서 주변에 영향을 줄 경우 dfs방식을 쓰면 된다는 것을 알았다. 그리고 dfs는 재귀함수방식을 사용하면 된다는 점도 알았다. 마지막에서 모든 위치에서 dfs를 진행하는 것은 시간이 아까워서 자신의 위치가 0일 때만 dfs가 진행되도록 코드도 따로 작성하였다.

<4> 미로탈출
N x M 크기의 직사각형 형태의 미로에 갇혀 있다. 위치는(1,1)에서 시작하며 출구는(N,M)의 위치에 존재하며 한번에 한 칸씩이동할 수 있다. 괴물이 있는 부분은 0, 없는부분은 1로 표싯되며, 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 탈출하기 위해 움직여야 하는 최소 칸의 갯수를 구하시오.(칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.)

입력 예시)
5 6
101010
111111
000001
111111
111111

출력 예시)
10

from collections import deque
# 맵크기 입력받기
n,m = map(int,input().split())
 
 
# 맵정보받기
graph=[]
for i in range(n):
    graph.append(list(map(int,input())))
 
#상하좌우
dx=[-1,1,0,0]
dy=[0,0,-1,1]
 
def bfs(x,y):
    queue = deque()
    # queue에는 좌표형태로 추가가 된다.
    queue.append((x,y))
 
    # 큐가 빌 때까지 실행
    while queue:
        x,y = queue.popleft()
        # 4가지 방향 
        for i in range(4):
            nx = x + dx[i]  
            ny = y + dy[i]
            # 맵의 크기를 벗어난 경우
            if nx <= -1 or ny <= -1 or nx >= n or ny >= m:
                continue
            # 괴물을 만난 경우
            if graph[nx][ny] == 0:
                continue
            #처음 가보는 곳만 가기
            if 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))

풀이:
1. 맵의 크기와 정보를 입력받습니다.
2. 상하좌우를 모두 탐색해야하므로 dx,dy를 이용합니다.
3. 모든 위치에서의 시작이 아니라 결국 한붓그리기처럼 시작 위치에서 마지막까지 가야하므로 bfs가 좋습니다.
4. 큐에 추가시킬 때는 좌표형태로 넣어서 while에 들어가자마자 반환하고 자신의 위치를 기억합니다.
5. 그 후에 상하좌우를 한번씩 거치고 예외조건을 줍니다.
6. 처음 가보는 곳에만 자신의 위치값에 +1을 하면 자기 자리의 값이 곧 횟수가 됩니다. (다른 곳에서 같은 곳을 방문하지 않으므로 자동으로 값이 정해질 때 최소 횟수가 됩니다. ex. 3인데 다른 노드와 인접해서 다시 +알파가 되지 않습니다.)
7. 인접노드 순으로 진행되므로, 가는 곳이 중복 되거나 한 노드에 동시접근하는 경우는 없습니다.
8. 큐에 넣어주고 다시 이과정을 반복합니다.
9. 큐가 모두 비어지면 모든 루트를 진행한 것이므로 마지막 출구의 값만 반환합니다.

배운 점: 큐 자료구조를 통해서 문제를 해결할 때 언제 append를 해주고 popleft를 해야하는지 감을 못잡았었는데 이번 문제를 통해서 알게 되었다. 그리고 큐는 먼저 들어간 쪽이 나오는 구조이므로 위와 같은 문제처럼 최소 횟수를 구할 때 중복이거나 동시접근인 가능성이 아예없기 때문에 훨씬 풀기 좋은 방법인 것 같다.