[프로그래머스][Python][Lv. 2] 미로 탈출

문제 설명

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지만 큐처럼 사용해서 풀었다. 그런데 나중에 풀고나서 보니 미리 시작점, 레버 위치를 구하지 않아도 됐었고, 뭔가 난잡하게 푼거 같아서 좀 더 연습해야겠다.