문제
https://school.programmers.co.kr/learn/courses/30/lessons/159993#
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
입출력

해설
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
'코딩테스트 > programmers' 카테고리의 다른 글
| 프로그래머스 / 시뮬레이션 / 서버 증설 횟수 (0) | 2025.12.13 |
|---|---|
| 프로그래머스 / 수학, 정수론 / 숫자 카드 나누기 (0) | 2025.12.11 |
| 프로그래머스 / 구현 / 삼각 달팽이 (0) | 2025.11.30 |
| 프로그래머스 / 큐 / 다리를 지나는 트럭 (0) | 2025.11.27 |
| 프로그래머스 / 분할정복 / 쿼드압축 후 개수 세기 (0) | 2025.11.13 |