미로 탈출

프로그래머스

---

BFS로 풀면 되는 문제.

 

BFS 탐색 함수를 따로 구현해서

시작지점 ~ 레버까지의 최단거리, 레버 ~ 도착지점까지의 최단거리를 각각 구한 후 더해주면 된다.

만약 2가지 최단거리 중 하나라도 None이 나오는 경우에는 도착이 불가능한 경우이므로 -1을 리턴해준다.

 

풀이 코드

from collections import deque

# BFS 돌리기
def bfs(maps, start_x, start_y, end_x, end_y, end_val):
    n = len(maps)
    m = len(maps[0])
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    
    visited = [[0] * m  for _ in range(n)]
    
    q = deque([(start_x, start_y)]) # 탐색 시작 노드 큐에 넣기
    visited[start_x][start_y] = 0 # 탐색 시작 노드 방문 처리
    
    while q:
        x, y = q.popleft()
        
        if maps[x][y] == end_val: # 큐에서 꺼낸 노드에서 탐색을 종료시켜야 하는 경우
            return visited[x][y]
        
        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 visited[nx][ny]:
                continue
            
            if maps[nx][ny] == 'X':
                continue
            # 'X'인 경우 제외하고는 모두 큐에 넣는다.
            else:
                visited[nx][ny] = visited[x][y] + 1
                q.append((nx, ny))
            


def solution(maps):
    answer = 0
    
    start_x = 0
    start_y = 0
    end_x = 0
    end_y = 0
    lever_x = 0
    lever_y = 0
    
    n = len(maps)
    m = len(maps[0])
    
    # 시작 지점, 춝, 레버 저장
    for i in range(n):
        for j in range(m):
            if maps[i][j] == 'S':
                start_x = i
                start_y = j
            elif maps[i][j] == 'E':
                end_x = i
                end_y = j
            elif maps[i][j] == 'L':
                lever_x = i
                lever_y = j
                
    first = bfs(maps, start_x, start_y, lever_x, lever_y, 'L') # 시작 지점에서 레버까지의 최단 거리
    second = bfs(maps, lever_x, lever_y, end_x, end_y, 'E') # 레버에서 도착점까지의 최단 거리
    
    if first == None or second == None: # 둘 중 하나라도 None을 리턴한다면 이동할 수 없는 것
        answer = -1
    else:
        answer = first + second
    
    return answer

 

 

쉽게 풀 수 있던 BFS 문제였지만 오랜만에 풀어서 사소한 부분에서 미스가 났던 문제.

몇 번 수정하니 통과할 수 있었다.