[이것이 취업을 위한 코딩 테스트다 with 파이썬] (한빛미디어, 나동빈) Chapter5(3). DFS/BFS

 포스팅 개요

 '혹시나 책에 있을 모든 실수와 오류는 온전히 제 책임이며, 책에 실린 좋은 아이디어와 표현은 모두 리뷰어님들의 조언 덕분입니다. 정말 고맙습니다.'라는 지은이의 글은 나동빈 저자님의 인품을 느낄 수 있는 한 줄이었습니다.

 

 저도 저런 마인드를 가진 사람이 되겠다고 다짐하며 책과의 여정을 떠나보겠습니다.

 

이것이 취업을 위한 코딩 테스트다

---

 포스팅 본문

 이번 포스팅으로 Chapter5에 대한 내용을 마무리하겠습니다.

 

2021.04.23 - [Coding Test & Algorithm] - [이것이 취업을 위한 코딩 테스트다 with 파이썬] (한빛미디어, 나동빈) Chapter5(2). DFS/BFS

[이것이 취업을 위한 코딩 테스트다 with 파이썬] (한빛미디어, 나동빈) Chapter5(2). DFS/BFS

 이전 포스팅들의 개념을 토대로 이번에는 실전 예제 2문제를 풀어보겠습니다.

 

 본 코드는 모두 제 Github에 올려두었습니다. (https://github.com/herjh0405/Coding_Test)

---

5-10. 음료수 얼려 먹기

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

# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
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+1, y)
        dfs(x, y-1)
        dfs(x, y+1)
        return True
    return False

# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
    for j in range(m):
        # 현재 위치에서 DFS 수행
        if dfs(i, j) == True:
            result += 1

print(result) #정답 출력

 문제의 해설

 이 문제는 DFS로 해결할 수있다. 얼음을 얼릴 수 있는 공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링할 수 있다. 

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

 코드를 보고는 이해했지만 다음에 비슷한 문제를 만난다면 풀 수 있을까? 자주 풀어봐야겠다.

이 방식을 알았다면 얼마전에 유용하게 쓰였을 텐데 늦게 만나서 조금 아쉽다.

 (P.S. 근데 왜 BFS는 안쓰고 DFS로 푸는 걸까? 더 빨라서 그런가?)

---

5-11. 미로 탈출

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

from collections import deque

# 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]

# BFS 소스코드 구현
def bfs(x, y):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    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] == 0:
                continue
            # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if graph[nx][ny] == 1 :
                graph[nx][ny] = graph[x][y] + 1 # 2
                queue.append((nx, ny)) # [1, 0]

        # 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n-1][m-1]

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

 문제 해설

 BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문에, 이 문제는 BFS를 이용했을 때 매우 효과적이다. BFS를 수행할 때마다 값들을 1씩 증가시키면서 반복해주면 해결된다.

주의 : 소스코드 상에서, 첫 번째 시작 위치는 다시 방문할 수 있도록 되어 첫 번째 시작 위치에 해당하는 값이 3으로 변경될 여지가 있다. 하지만 본 문제에서는 단순히 가장 오른쪽 아래 위치에 이동하는 것을 요구하고 있기 때문에, 본 소스코드는 정상적으로 답을 도출하는 간결한 정답 코드이다.

---

 이렇게 길었던 DFS/BFS의 포스팅이 끝났습니다. 되게 이해하는 데는 큰 무리가 없지만 응용하기는 어렵겠다는 느낌을 받았습니다. 꾸준히 반복 학습하기로 다짐하면서 Chapter6에서 뵙겠습니다. :)