문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/159993

제한 사항

입출력 예



풀이
def solution(maps):
answer = 0
row_size = len(maps)
col_size = len(maps[0])
start = [[-1, -1]]
lever = [[-1, -1]]
for r in range(row_size):
for c in range(col_size):
if maps[r][c] == 'S':
start = [[r, c]]
elif maps[r][c] == 'L':
lever = [[r, c]]
visited_map = [[False] * col_size for _ in range(row_size)]
answer += bfs(maps, start, visited_map, 'L')
visited_map = [[False] * col_size for _ in range(row_size)]
answer += bfs(maps, lever, visited_map, 'E')
return answer if 0 < answer else -1
def bfs(maps, points, visited_map, dest):
row_size = len(maps)
col_size = len(maps[0])
next_points = []
for point in points:
row = point[0]
col = point[1]
if maps[row][col] == dest:
return 0
else:
visited_map[row][col] = True
if check_boundary(maps, visited_map, row - 1, col):
next_points.append([row - 1, col])
if check_boundary(maps, visited_map, row, col - 1):
next_points.append([row, col - 1])
if check_boundary(maps, visited_map, row + 1, col):
next_points.append([row + 1, col])
if check_boundary(maps, visited_map, row, col + 1):
next_points.append([row, col + 1])
if 0 < len(next_points):
return bfs(maps, next_points, visited_map, dest) + 1
else:
return -100
def check_boundary(maps, visited_map, new_row, new_col):
row_size = len(maps)
col_size = len(maps[0])
if (0 <= new_row and new_row < row_size
and
0 <= new_col and new_col < col_size
and
visited_map[new_row][new_col] == False
and
maps[new_row][new_col] != 'X'
):
return True
return False
ㄴ 통과 못한 코드
from collections import deque
def solution(maps):
answer = 0
queue = deque()
row_size = len(maps)
col_size = len(maps[0])
start = [-1, -1]
lever = [-1, -1]
for r in range(row_size):
for c in range(col_size):
if maps[r][c] == 'S':
start = [r, c]
elif maps[r][c] == 'L':
lever = [r, c]
visited_map = [[False] * col_size for _ in range(row_size)]
queue.append((start, 0))
visited_map[start[0]][start[1]] = True
lever_result = bfs(maps, visited_map, queue, 'L')
if lever_result == -1:
return -1
queue.clear()
visited_map = [[False] * col_size for _ in range(row_size)]
queue.append((lever, 0))
visited_map[lever[0]][lever[1]] = True
exit_result = bfs(maps, visited_map, queue, 'E')
if exit_result == -1:
return -1
return lever_result + exit_result
def bfs(maps, visited_map, queue, dest):
row_size = len(maps)
col_size = len(maps[0])
while queue:
[row, col], count = queue.popleft()
if maps[row][col] == dest:
return count
direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for d_row, d_col in direction:
next_row = row + d_row
next_col = col + d_col
if check_boundary(maps, visited_map, next_row, next_col):
queue.append(([next_row, next_col], count + 1))
visited_map[next_row][next_col] = True
return -1
def check_boundary(maps, visited_map, next_row, next_col):
row_size = len(maps)
col_size = len(maps[0])
if (0 <= next_row and next_row < row_size
and
0 <= next_col and next_col < col_size
and
visited_map[next_row][next_col] == False
and
maps[next_row][next_col] != 'X'
):
return True
return False
ㄴ 통과한 코드
후기
최단거리 찾기 문제인데 오랜만에 푸는거 + 파이썬에 익숙하지 않아서 조금 시간이 걸렸다. 처음에는 재귀로 풀었는데 효율적이지 않았는지 시간 제한 실패가 떴다. 호출 스택 비용이 커서 오래걸리는 것 같다.
다음에 푼 거는 deque지만 큐처럼 사용해서 풀었다. 그런데 나중에 풀고나서 보니 미리 시작점, 레버 위치를 구하지 않아도 됐었고, 뭔가 난잡하게 푼거 같아서 좀 더 연습해야겠다.
'코딩테스트 (프로그래머스) > Python' 카테고리의 다른 글
| [프로그래머스][Python][Lv. 1] [PCCE 기출문제] 10번 / 공원 (0) | 2025.11.24 |
|---|