https://school.programmers.co.kr/learn/courses/30/lessons/159993
문제 설명
1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다.
각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다.
통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다.
레버 또한 통로들 중 한 칸에 있습니다.
따라서 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후,
미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다.
이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다.
미로에서 한 칸을 이동하는 데 1초가 걸린다고 할 때,
최대한 빠르게 미로를 빠져나가는 데 걸리는 시간을 구하려 합니다.
미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때,
미로를 탈출하는 데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요.
만약 탈출할 수 없다면 -1을 return 해주세요.접근
최소(최단거리) + 격자 문제이므로 BFS라고 생각했다.
직전 문제인 게임 맵 최단거리와 거의 유사한 방식으로 풀면 된다.
BFS의 기본형에서
distance인자를 추가하고,
그래프 대신 격자 형태로 탐색하면 된다.레버를 반드시 통과해야 한다는 제약사항이 있다.
따라서
dist1,dist2로 나눠서 각각 BFS 최단거리를 구한 후answer = dist1 + dist2형태로 반환하자.
- 1차 BFS: 시작점
S→ 레버L까지 이동하고dist1계산 - 2차 BFS: 레버
L→ 출구E까지 이동하고dist2계산
- 1차 BFS: 시작점
sol1
from collections import deque
def solution(maps):
answer = 0
visited = [[False] * col in range(row)]
# visited가 필요한가?
# 왜냐면 갔던 곳을 또 가도 되긴 하는데...
# 경로1, 경로2 각각에서는 필요할 것 같다.
# 대신 dist1을 구한 뒤에는 한 번 초기화하고 다시 탐색하면 될 듯.
row = len(maps)
col = len(maps[0])
queue1 = deque([(0, 0, 0)])
# BFS + 격자 문제이므로 격자 관련 변수도 선언
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
while queue1:
r, c, dist1 = queue1.popleft()
if maps[r][c] == 'L':
return dist1
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
queue1.append(nr, n1, dist1 + 1)
queue2 = deque([(nr, nc, 0)])
while queue2:
r, c, dist2 = queue2.popleft()
if maps[r][c] == 'E':
return dist2
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
queue2.append(nr, nc, dist2 + 1)
return dist1 + dist2sol1의 문제점
S를 무조건(0, 0)으로 두고 시작했다.마음이 급해서 조건을 꼼꼼히 보는 것을 놓쳤다.
시작점S의 좌표를 먼저 찾아줘야 한다.visited를 제대로 사용하지 않았다.방문한 좌표를
True로 변경하는 것과,
이동할 좌표가 아직 방문하지 않은 곳인지 확인하는 것을 누락했다.방문 조건을 확인하는 것을 누락했다.
다음 좌표가
- 맵 범위 안에 있는지
- 벽
X가 아닌지 - 아직 방문하지 않은 곳인지
확인한 뒤 Queue에 넣어야 한다.
sol2
from collections import deque
def solution(maps):
answer = 0
visited1 = [[False] * col for _ in range(row)]
visited2 = [[False] * col for _ in range(row)]
# visited가 필요한가?
# 경로1, 경로2 각각에서는 필요하다.
# 대신 dist1을 구한 뒤 visited를 초기화하고 다시 탐색하면 될 듯.
row = len(maps)
col = len(maps[0])
# 시작지점 S의 좌표 찾기: 완전탐색
start = None
for i in range(row):
for j in range(col):
if maps[i][j] == 'S':
start = (i, j)
sr, sc = start
queue1 = deque([(sr, sc, 0)])
# BFS + 격자 문제이므로 방향 변수 선언
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
while queue1:
r, c, dist1 = queue1.popleft()
visited1[r][c] = True
if maps[r][c] == 'L':
return dist1
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if visited1[nr][nc] == False and maps[nr][nc] != 'X' and 0 <= nr < row and 0 <= nc < col:
queue1.append((nr, nc, dist1 + 1))
queue2 = deque([(nr, nc, 0)])
while queue2:
r, c, dist2 = queue2.popleft()
visited2[r][c] = True
if maps[r][c] == 'E':
return dist2
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if visited2[nr][nc] == False and maps[nr][nc] != 'X' and 0 <= nr < row and 0 <= nc < col:
queue2.append((nr, nc, dist2 + 1))
return dist1 + dist2또 틀림
return을 하면 현재 BFS만 끝나는 것이 아니라solution()함수 자체가 끝나버린다.따라서 1차 BFS에서 레버
L을 찾았을 때는dist1을 바로return하면 안 된다.레버의 좌표와 거리를 따로 저장한 뒤,
break를 사용해서 1차 BFS만 종료해야 한다.배열을 탐색할 때는 인덱스 에러가 나지 않도록 반드시 범위 검사를 먼저 해야 한다.
기존에는
if visited1[nr][nc] == False and maps[nr][nc] != 'X' and 0 <= nr < row and 0 <= nc < col:로 작성했는데, 이 경우
nr,nc가 범위를 벗어난 상태에서visited1[nr][nc]를 먼저 확인하려고 하면서 에러가 발생할 수 있다.따라서 다음과 같이 바꿔준다.
if 0 <= nr < row and 0 <= nc < col: if not visited1[nr][nc] and maps[nr][nc] != 'X':append()에는 하나의 요소만 넣을 수 있다.따라서
queue.append(nr, nc, dist + 1)형태가 아니라,
queue.append((nr, nc, dist + 1))처럼 괄호를 한 번 더 사용해서 튜플 하나를 넣어야 한다.
2차 BFS의 시작점은 마지막으로 계산된
nr,nc가 아니라,
실제로 레버라고 확인된 좌표여야 한다.nr,nc는 탐색 과정에서 계속 바뀌는 임시 좌표이므로,
레버를 찾았을 때(r, c)를 별도로 저장해둬야 한다.
sol3 (정답)
from collections import deque
def solution(maps):
row = len(maps)
col = len(maps[0])
visited1 = [[False] * col for _ in range(row)]
visited2 = [[False] * col for _ in range(row)]
start = None
for i in range(row):
for j in range(col):
if maps[i][j] == 'S':
start = (i, j)
sr, sc = start
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
queue1 = deque([(sr, sc, 0)])
visited1[sr][sc] = True
lr = lc = -1
lever_dist = -1
while queue1:
r, c, dist1 = queue1.popleft()
if maps[r][c] == 'L':
lr, lc = r, c
lever_dist = dist1
break
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if 0 <= nr < row and 0 <= nc < col:
if not visited1[nr][nc] and maps[nr][nc] != 'X':
visited1[nr][nc] = True
queue1.append((nr, nc, dist1 + 1))
if lever_dist == -1:
return -1
queue2 = deque([(lr, lc, 0)])
visited2[lr][lc] = True
while queue2:
r, c, dist2 = queue2.popleft()
if maps[r][c] == 'E':
return lever_dist + dist2
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if 0 <= nr < row and 0 <= nc < col:
if not visited2[nr][nc] and maps[nr][nc] != 'X':
visited2[nr][nc] = True
queue2.append((nr, nc, dist2 + 1))
return -1시간복잡도
O(N × M)
N × M 크기의 격자에서 각 칸은 BFS 한 번당 최대 한 번 방문한다.
각 칸에서는 상하좌우 4방향을 탐색하므로 BFS 한 번은 O(4NM) = O(NM)이다.
S → L, L → E로 BFS를 두 번 수행하고,
시작점 S를 찾기 위한 완전탐색도 O(NM)이지만 상수는 제거하므로
최종 시간복잡도는 O(NM)이다.
공간복잡도
O(N × M)
visited1, visited2가 각각 O(NM)의 공간을 사용하고,
BFS의 Queue 역시 최악의 경우 O(NM)의 공간을 사용할 수 있다.
입력으로 주어진 maps를 제외한 추가 공간을 기준으로 계산하면
최종 공간복잡도는 O(NM)이다.
배운점
우리가 보통 좌표계를 생각할 때
(x, y)순서를 떠올리는데,
2차원 배열에서는[행][열], 즉[y][x]순서로 접근하기 때문에 이 부분을 조심해야겠다고 생각했다.이번에는 아예
x,y대신row,col을 사용해서maps[row][col] visited[row][col]형태로 통일하는 것이 더 헷갈리지 않았다.
S,L좌표를 찾았을 때 해당 좌표를 다음 탐색에서 다시 사용할 수 있도록
별도의 변수에 저장하는 과정이 조금 헷갈렸다.특히
nr,nc는 단순히 다음에 탐색할 후보 좌표이고 계속 값이 바뀌기 때문에,
레버를 찾았을 때는lr, lc = r, c처럼 실제로
L이라고 확인된 좌표를 별도로 저장해야 한다.BFS를 두 번 수행할 때는
visited도 각각 따로 사용하거나 초기화해야 한다.S → L탐색에서 방문했던 칸도,L → E탐색에서는 다시 지나갈 수 있기 때문이다.격자 BFS에서는 Queue에 좌표를 넣기 전에
범위 안인가? → 벽이 아닌가? → 아직 방문하지 않았는가?순서로 확인하는 습관을 들여야겠다.
'CS지식 > 알고리즘' 카테고리의 다른 글
| BFS-게임 맵 최단거리 python 프로그래머스 lv2 (0) | 2026.09.12 |
|---|