🍀 미로 탈출
이 문제는 레버의 위치와 탈출구의 위치까지 탐색을 할 수 있어야 한다.
dfs, bfs 둘 중 고민을 하다가 모든 경로를 탐색하는 것은 같지만, 그 위치까지 도달하기까지 걸리는 시간을 marking해야 하므로 bfs가 적절할 것 같으며 수행속도 또한 빠르다고 판단하여 bfs로 풀었다.
이 문제를 풀기 위해 중요한 포인트는 아래와 같다.
탈출구는 레버를 당겨야만 문을 열 수가 있다.
이 말은 즉, 탈출구에 접근할 수 있어도 레버를 열지 않은 상태라면 미로를 탈출 할 수 없다는 것이다.if not leverOpen -> return -1행과 열의 길이는 다르다. 👉🏻 직사각형이 될 수 있다.
총 걸리는 시간 = 레버까지 탐색하는 최소시간 + 레버에서 출구까지 탐색하는 최소시간 👉🏻 💡
레버를 먼저 찾은 후 탈출구에 접근해야 한다.
결국 레버를 먼저찾고 출구를 찾아야한다. 따라서 레버를 찾는 bfs와 출구를 찾는 bfs를 두번 실행하며 상하좌우로 탐색이 가능하여 시간 복잡도는 O(N^2)로 maps의 최대 길이가 100인 점을 고려하면 이론상으로 통과할 수 있다.
1️⃣ javascript
// S, L, E의 위치를 찾기위한 함수.
function findPoints(board){
const result = Array(3).fill(0);
const points = ['S', 'L', 'E'];
for (let i = 0; i < board.length; i++){
for (let j = 0; j < board[0].length; j++){
points.forEach((v, index) => board[i][j] === v && (result[index] = [i, j]));
}
}
return result;
}
// 현재 위치에서 다음 위치를 탐색할 수 있는지에 대한 함수 -> board범위 안에 있으며 && 벽이 아닌 경우 탐색
function canGo(row, col, board){
const [rowLength, colLength] = [board.length, board[0].length];
return row >= 0 && row < rowLength && col >= 0 && colLength && 'SLOE'.includes(board[row][col]);
}
function solution(maps) {
const [startPoint, leverPoint, exitPoint] = findPoints(maps);
const leverBoard = Array.from({length: maps.length}, (_, idx) => [...maps[idx]].map(v => v !== 'X' ? false : v));
const direction = [[-1, 0], [0, 1], [1, 0], [0, -1]];
leverBoard[startPoint[0]][startPoint[1]] = 0; // 시작지점은 걸리는 시간을 0으로 초기화 -> 그냥 0으로 하면 [0, 1] + 1의 값이 들어간다.
const queue = [startPoint]; // 시작점 -> 시작위치 지정
// 레버탐색
while (queue.length > 0){
const [curRow, curCol] = queue.shift();
for (const [dx, dy] of direction){
const [nextRow, nextCol] = [curRow + dx, curCol + dy];
// 다음칸으로 갈 수 있으며, 방문하지 않았다면 걸리는 시간으로 marking하여 방문처리!!!
if (canGo(nextRow, nextCol, maps) && leverBoard[nextRow][nextCol] === false){
leverBoard[nextRow][nextCol] = leverBoard[curRow][curCol] + 1;
// 레버를 찾은 경우 더이상 탐색을 하지 못하게 queue를 빈 배열로 초기화하여 탐색을 더 하지 못하게 한다.
if (nextRow === leverPoint[0] && nextCol === leverPoint[1]) {
queue.length = 0;
break;
}
queue.push([nextRow, nextCol]);
}
}
}
// 레버를 당기지 못한다면 탈출구에 도착해도 나가지 못하므로 레버를 찾지 못할 시에는 탈출구 탐색을 멈충
if (!leverBoard[leverPoint[0]][leverPoint[1]]) return -1;
// 레버위치부터 탈출구 탐색
// -> 탈출구를 탐색할 때 원래 왔던 길도 갈 수 있으므로,
// 레버를 탐색하면서 방문표시를 했기때문에 새로운 방문하지 않는 배열을 만들어서 다시 탐색
queue.push(leverPoint) // 시작점 -> 레버위치 지정
const exitBoard = Array.from({length: maps.length}, (_, idx) => [...maps[idx]].map(v => v !== 'X' ? false : v));
exitBoard[leverPoint[0]][leverPoint[1]] = leverBoard[leverPoint[0]][leverPoint[1]];
while (queue.length > 0){
const [curRow, curCol] = queue.shift();
for (const [dx, dy] of [[-1, 0], [0, 1], [1, 0], [0, -1]]){
const [nextRow, nextCol] = [curRow + dx, curCol + dy];
if (canGo(nextRow, nextCol, maps) && exitBoard[nextRow][nextCol] === false){
exitBoard[nextRow][nextCol] = exitBoard[curRow][curCol] + 1;
if (nextRow === exitBoard[0] && nextCol === exitBoard[1]) {
queue.length = 0;
break;
}
queue.push([nextRow, nextCol]);
}
}
}
return exitBoard[exitPoint[0]][exitPoint[1]] || -1;
}2️⃣ python
from collections import deque
def find_points(board):
result = [0, 0, 0]
points = 'SLE'
for i in range(len(board)):
for j in range(len(board[0])):
value = board[i][j]
# index는 찾는 요소가 없으면 error를 일으키므로
if value in points:
result[points.index(value)] = [i, j]
return result
def can_go(row, col, board):
row_length, col_length = len(board), len((board[0]))
return 0 <= row < row_length and 0 <= col < col_length and board[row][col] is False
def solution(maps):
start_point, lever_point, exit_point = find_points(maps)
row_length, col_length = len(maps), len(maps[0])
direction = [[-1, 0], [0, 1], [1, 0], [0, -1]]
lever_board = [[v if v == 'X' else False for v in row] for row in maps]
lever_board[start_point[0]][start_point[1]] = 0
queue = deque([start_point])
# search lever
while queue:
cur_row, cur_col = queue.popleft()
for dx, dy in direction:
next_row, next_col = cur_row + dx, cur_col + dy
if can_go(next_row, next_col, lever_board):
lever_board[next_row][next_col] = lever_board[cur_row][cur_col] + 1
if [next_row, next_col] == lever_point:
queue.clear()
break
queue.append([next_row, next_col])
if not lever_board[lever_point[0]][lever_point[1]]: return -1
exit_board = [[v if v == 'X' else False for v in row] for row in maps]
exit_board[lever_point[0]][lever_point[1]] = lever_board[lever_point[0]][lever_point[1]]
queue.append(lever_point[:])
while queue:
cur_row, cur_col = queue.popleft()
for dx, dy in direction:
next_row, next_col = cur_row + dx, cur_col + dy
if can_go(next_row, next_col, exit_board):
exit_board[next_row][next_col] = exit_board[cur_row][cur_col] + 1
if [next_row, next_col] == exit_point:
queue.clear()
break
queue.append([next_row, next_col])
return -1 if exit_board[exit_point[0]][exit_point[1]] is False else exit_board[exit_point[0]][exit_point[1]]💡💡 python에서는 javascript의 findIndex와 달리 없는 값을 찾을 시 error가 발생하여 적절히 처리해주어야 한다. 또한, python에서는 0과 False는 같은 값으로 처리한다.
# python arr = [1, 2, 3] arr.index(100) # error 발생 ❌ b = False print(b == 0) # 👉🏻 True print(0 is False) # 👉🏻 False print(b is False) # 👉🏻 True
// javascript const arr = [1, 2, 3]; arr.findIndex(v => v === 100) // -1 반환
🚀 마치며
탐색 문제로서 dfs, bfs로 문제를 풀 수 있지만, bfs를 공부할 수 있는 중요한 계기가 되었다... 이론상으로는 알고 있어서 bfs를 쓰면 되겠다 싶었는데 어떻게 구현해야할지 감이 오지 않아 이코테 python으로 공부한 후에 문제를 풀 수 있었다. 원래 알고리즘 공부를 손을 놓았다가 진행하던 프로젝트를 통해서 단지 시간적인 효율만이 아닌 사고력을 길러준다는 점에서 다시 정진하고 있다. 이 문제를 푸는데 3일이 걸렸지만 다음에는 1시간 안에 풀 수 있을 것이다... ㅜㅜ🥲 그리고 python에서는 deque를 써서 앞에서 뺄 시 O(1)시간으로 했는데 이번 문제에 queue에 들어가는 요소들이 많지 않으므로 따로 Queue를 구현하지 않았다. Queue는 여기에서 찾아볼 수 있다.
step by step