[알고리즘] - 미로 탈출 (이코테 실전 문제)
- 이번 문제는 이것이 취업을 위한 코딩 테스트다 with 파이썬 속 실전 문제 ‘미로 탈출’ 입니다. 문제 명세 및 입출력 예시는 해당 책을 참고해주세요!
접근 방식
- 처음 접근할 때는 DFS 방식으로 해당 문제를 풀어보려고 접근했습니다.
- DFS 탐색을 진행하며 탐색 횟수를 카운팅했고, 현재 위치에서 탐색이 가능한 노드들 중 (목적지에 도착 가능한 패스 중) 최소의 패스를 갖는 노드의 탐색 횟수를 리턴하도록 구현을 진행했습니다.
- 그러나 이와 같은 방식으로 구현을 진행하니, 현재 위치에서 최소의 패스를 갖는 노드를 찾는 과정에서 반복적으로 배열을 새롭게 할당해야 했고, 그 결과 지나치게 메모리를 낭비하게 되어 메모리가 초과되는 현상이 발생했습니다.
- BFS로 탐색 방식을 바꾸고 다시 문제에 접근했습니다.
- DFS에 비해 BFS 탐색 방식의 경우 넓이를 우선시 하기 때문에 같은 깊이의 노드들에 대해서 동일한 탐색 횟수를 할당하는 것이 자연스럽고 편리했습니다.
- 이에 따라 동일한 깊이의 노드들 중 목적지에 도착한 노드가 존재할 경우 탐색을 마치고 해당 탐색 횟수를 리턴할 수 있도록 구현을 진행했습니다.
구현
-
기본적인 BFS 함수에 해당 노드에서 추가로 탐색이 가능한지 여부를 나타내는 can_go 변수와 목적지 도착 여부를 확인하는 reach_final 변수를 선언하여 False로 초기화 한 뒤, 한 사이클의 탐색 (해당 노드가 방문할 수 있는 모든 노드들에 대한 탐색)을 진행하는 과정에서 탐색이 가능하다면 can_go를 True로 변경하고, 목적지에 도착했다면 reach_final을 True로 변경했습니다.
-
한 사이클의 탐색을 마친 뒤, 해당 변수들을 확인하여 탐색 횟수를 나타내는 cnt를 증가시키거나 BFS 함수를 종료하도록 했습니다.
-
BFS 함수의 탐색 과정을 담은 코드는 아래와 같습니다.
cnt = 1 while(queue): cur_node = queue.popleft() cur_x, cur_y = cur_node # 한 번의 순회 can_go = False reach_final = False for step in steps: mv_x = cur_node[0] + step[0] mv_y = cur_node[1] + step[1] # graph의 끝에 도달했으면 종료 조건은 True로 변경 if mv_x == n-1 and mv_y == m-1: reach_final = True # graph의 인덱스 범위를 안 넘는지 체크 if mv_x < 0 or mv_x >= n or mv_y < 0 or mv_y >= m: continue if not visited[mv_x][mv_y] and graph[mv_x][mv_y] == 1: # cnt += 1 can_go = True queue.append((mv_x, mv_y)) visited[mv_x][mv_y] = True if can_go: cnt += 1 if reach_final: return cnt return cnt
트러블 슈팅
-
이와 같이 구현하니, 예시로 주어진 입력에 대해서는 정답을 출력했지만 아래와 같은 입력에 대해서 제대로 된 정답을 출력하지 못했습니다.
5 6 111111 111111 111111 111111 111111 --- answer : 10 위의 코드를 통한 출력 : 26 -
위의 코드에서 탐색을 진행하며 cnt를 증가시키게 되는데, 이 때의 cnt가 누적되기 때문에 발생하는 문제였습니다.
- 이를 해결하기 위해, 따로 cnt 변수를 사용하지 않고, 방문을 체크하는 visited 배열에 True/False가 아닌 거리(탐색 횟수)를 저장하도록 했습니다.
- 즉, 방문을 체크하는 배열 내부를 -1로 초기화 해 둔 뒤, 방문할 때마다 이전 탐색 횟수에 1을 더해서 해당 인덱스에 저장하도록 했습니다.
- 이후 최종적으로 방문을 체크하는 배열을 리턴한 뒤, 해당 배열의 N, M 번째 원소를 확인하면 최소 탐색 횟수를 구할 수 있었습니다.
전체 코드
- 수정 후 전체 코드는 다음과 같습니다.
import sys
from collections import deque
def bfs(graph, start_node, visited, n, m):
x, y = start_node
visited[x][y] = 1
queue = deque([start_node])
steps = [
(-1, 0),
(1, 0),
(0, -1),
(0, 1)
]
while(queue):
cur_node = queue.popleft()
cur_x, cur_y = cur_node
# 한 번의 순회
reach_final = False
for step in steps:
mv_x = cur_x + step[0]
mv_y = cur_y + step[1]
# graph의 끝에 도달했으면 종료 조건은 True로 변경
if mv_x == n-1 and mv_y == m-1:
reach_final = True
# graph의 인덱스 범위를 안 넘는지 체크
if mv_x < 0 or mv_x >= n or mv_y < 0 or mv_y >= m:
continue
if visited[mv_x][mv_y] == -1 and graph[mv_x][mv_y] == 1:
queue.append((mv_x, mv_y))
visited[mv_x][mv_y] = visited[cur_x][cur_y] + 1
if reach_final:
break
return visited
input = sys.stdin.readline
n, m = map(int, input().rstrip().split())
maze = []
for _ in range(n):
# 문자열을 map 함수에 넣으면 한 글자 한 글자를 원소로 인식하여 반복
maze.append(list(map(int, input().rstrip())))
check = [[-1] * m for _ in range(n)]
min_check = bfs(maze, (0,0), check, n, m)
print(min_check[n-1][m-1])
- graph를 탐색하는 과정에서 갈 수 있는 곳은 상, 하, 좌, 우로 제한되기 때문에 상, 하, 좌, 우를 표현하기 위해 steps 배열을 정의하고, 이를 순회하며 네 방향에 대한 탐색을 진행했습니다.
- 또한 상, 하, 좌, 우를 탐색하는 과정에서 graph의 인덱스 범위를 벗어나는 경우가 발생할 수 있기 때문에, 이에 대한 체크를 진행했습니다.
- 문제의 조건에 따라 graph의 해당 인덱스의 값이 1인 경우만 방문 가능하도록 구현했습니다.
Lesson
트러블 슈팅 과정에서, 방문을 체크하는 배열을 활용해 탐색의 횟수를 저장한다면, DFS 방식으로도 메모리 초과 없이 구현이 가능할 것 같다는 생각이 들었습니다. 결국 DFS 방식 자체가 잘못된 것이 아니라, 제가 거리를 계산하는 방식이 잘못되었던 것이라는 생각이 들었습니다. 추후 BFS, DFS를 더 공부하면서 DFS 방식으로도 해당 문제를 구현해봐야겠습니다.