프로그래머스 - 미로 탈출

문제

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

프로그래머스

 

 

풀이

그래프에서 최소 시간을 찾아야 하므로 BFS를 사용한다.

문제 조건 중 L 칸을 꼭 지나가야 하므로 BFS를 2번 진행한다.

S - > L, L -> E 이 2번 중에 갈 수 없는 경로가 존재하면 -1을 리턴한다.

L 칸에서 BFS를 새로 시작해야 하므로 큐, visit 배열등을 다시 초기화한다.

다음 방문 노드를 큐에 집어넣을 때 BFS 진행 횟수(step)를 함께 저장하면 같은 level의 노드들의 step을 똑같이 저장할 수 있다.

 

 

코드

python

def bfs(row, col, visit, max_row, max_col, maps):
    visit_L = False    
    q = []
    visit[row][col] = True
    q.append([row, col, 0])
    
    while q:
        cur_row, cur_col, step = q.pop(0)
 
        if maps[cur_row][cur_col] == "E" and visit_L:
            return step
 
        if maps[cur_row][cur_col] == "L":
            visit_L = True
            q = []
            visit = [[False for _ in range(len(maps[0]))] for _ in range(len(maps))]
            visit[cur_row][cur_col] = True
 
        for d in range(4):
            d_row = [1, -1, 0, 0]
            d_col = [0, 0, 1, -1]
            next_row = cur_row + d_row[d]
            next_col = cur_col + d_col[d]
 
            if next_row < 0 or next_row >= max_row or next_col < 0 or next_col >= max_col:
                continue
 
            if maps[next_row][next_col] != "X" and not visit[next_row][next_col] :
                q.append([next_row, next_col, step + 1])
                visit[next_row][next_col] = True
    
    return -1
    
 
def solution(maps):
    visit = [[False for _ in range(len(maps[0]))] for _ in range(len(maps))]
    for i in range(len(maps)):
        for j in range(len(maps[i])):
            if maps[i][j] == "S":
                answer = bfs(i, j, visit, len(maps), len(maps[0]), maps)
                return answer