프로그래머스 / BFS / 미로 탈출

문제

---

 

https://school.programmers.co.kr/learn/courses/30/lessons/159993#

프로그래머스

 

입출력

---

 

 

해설

---

 

n * n 미로를 레버를 당긴 후 탈출하는 문제이다.

 

해당 문제는 전형적인 BFS 문제이며, 상태는 레버를 당긴 상황과 당기지 않은 상황으로 나눌 수 있을 것이다.

그렇기 때문에 BFS를 돌릴 때 상태를 추가적으로 저장할 수 있어야 한다.

 

1. 시작 좌표를 알아낸다.

2. 방문배열을 3차원 배열로 레버를 당긴 상태를 추가적으로 저장할 수 있도록 한다.

3. BFS를 돌린다.

 

초기의 위치가 0인 것을 유의하고 또한 레버를 당기지 않고도 출구는 지나갈 수 있으며,

탈출을 하려면 무조건 레버를 당긴 상태여야 한다.

 

정답코드

---

'''
'25. 12. 9.(화)

1. bfs 돌리는데 방문배열을 3차원으로 잡고 돌린다.
2. visited[x][y][z] (y, z) 좌표에 x를 하고 도달했는지 판별
x는 레버를 당겼는지 아닌지 판별
'''
from collections import deque
#target 찾으면 좌표 보내기
def find(maps: list, target: str) -> tuple:
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] == target:
                return i, j
    return -1, -1
def solution(maps: list) -> int:
    answer = -1
    
    q = deque()
    x, y = find(maps, 'S')#시작 좌표 알아내기
    q.append((x, y, 0))#(x, y) 좌표, 레버를 당겼는지
    
    ROW = len(maps)
    COL = len(maps[0])
    MOVE = (0, 1), (0, -1), (1, 0), (-1, 0)
    visited = [[[-1]*COL for _ in range(ROW)]for _ in range(2)]
    
    visited[0][x][y] = 0
    
    ex, ey = find(maps, 'E')#출구 좌표 알아내기
    while q:
        x, y, isOn = q.popleft()
        if x == ex and y == ey and isOn:
            answer = visited[isOn][x][y]
            break
        for dx, dy in MOVE:
            nx, ny = x + dx, y + dy
            nxtOn = isOn#이전 상황을 그대로 가져간다.
            if nx < 0 or nx >= ROW or ny < 0 or ny >= COL:continue
            if maps[nx][ny] == 'L':nxtOn = 1#당겼음.
            
            if visited[nxtOn][nx][ny] != -1 or maps[nx][ny] == 'X':continue
            visited[nxtOn][nx][ny] = visited[isOn][x][y] + 1
            q.append((nx, ny, nxtOn))
    return answer

 

깃허브 : https://buly.kr/58TRMko

유튜브 : https://youtu.be/9LCNahIByTQ