[BFS] 미로탈출 - Python / JavaScript

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/159993

프로그래머스

 

[문제 간단 요약]

 

• 미로에서 시작 지점(S) → 레버(L) → 출구(E) 순서대로 이동해야 한다.
• 이동은 상하좌우로만 가능하며, 벽(X)은 통과할 수 없다.
• 각 이동은 1초가 걸린다.
• 레버를 당기지 않으면 출구로 갈 수 없다.
• 도달할 수 없는 경우 -1을 반환한다.

 

[문제 해결 방안]

• 이 문제는 최단 경로 탐색 문제이며, BFS(너비 우선 탐색)으로 해결 가능하다.
• 해결 순서:
  1. S → L 최단 시간 BFS
  2. L → E 최단 시간 BFS
  3. 두 구간 모두 도달 가능하다면 합산, 하나라도 불가능하면 -1 반환

 

• 즉, BFS 두 번 수행이 핵심이다.

[문제 해결 코드 - python]

from collections import deque

def bfs(y,x,maps,cnt,search):
    q = deque()
    q.append([y,x,cnt])
    used = [[0 for _ in range(len(maps[0]))] for _ in range(len(maps))]
    directs = [[0,1],[0,-1],[1,0],[-1,0]]
    used[y][x] = 1
    while q:
        y,x,cnt = q.popleft()
        for direct in directs:
            dy = y + direct[0]
            dx = x + direct[1]
            if dy < 0 or dx < 0 or dy > len(maps)-1 or dx > len(maps[0])-1: continue
            if used[dy][dx] != 0 or maps[dy][dx] =='X': continue
            if maps[dy][dx] == search:
                return [dy,dx,cnt+1]
            used[dy][dx] = 1
            q.append([dy,dx,cnt+1])
            


def solution(maps):
    answer = 0
    for y in range(len(maps)):
        for x in range(len(maps[0])):
            if maps[y][x] == 'S':
                S=[y,x]
    cnt=0
    L = bfs(S[0],S[1], maps, cnt, 'L')
    if L == None:
        return -1
    E = bfs(L[0],L[1], maps, L[2], 'E')
    if E == None:
        return -1
    return E[2]

 

[문제 해결 코드 - javascript]

function bfs(maps, start, target) {
  const n = maps.length;
  const m = maps[0].length;
  const visited = Array.from({ length: n }, () => Array(m).fill(false));
  const q = [[start[0], start[1], 0]];
  visited[start[0]][start[1]] = true;

  const directions = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  while (q.length > 0) {
    const [x, y, dist] = q.shift();
    if (maps[x][y] === target) return dist;

    for (const [dx, dy] of directions) {
      const nx = x + dx;
      const ny = y + dy;

      if (
        nx >= 0 &&
        nx < n &&
        ny >= 0 &&
        ny < m &&
        !visited[nx][ny] &&
        maps[nx][ny] !== "X"
      ) {
        visited[nx][ny] = true;
        q.push([nx, ny, dist + 1]);
      }
    }
  }
  return -1;
}

function solution(maps) {
  let start, lever, end;
  for (let i = 0; i < maps.length; i++) {
    for (let j = 0; j < maps[0].length; j++) {
      if (maps[i][j] === "S") start = [i, j];
      if (maps[i][j] === "L") lever = [i, j];
      if (maps[i][j] === "E") end = [i, j];
    }
  }

  // S → L
  const s_to_l = bfs(maps, start, "L");
  if (s_to_l === -1) return -1;

  // L → E
  const l_to_e = bfs(maps, lever, "E");
  if (l_to_e === -1) return -1;

  return s_to_l + l_to_e;
}