미로 탈출 - Python, BFS

 

 

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

프로그래머스

 

 

코드 & 풀이

 

from collections import deque

def move_target(maps, directs, start_x, start_y, target):
    visited = [[0] * len(row) for row in maps]
    queue = deque()
    queue.append([start_x, start_y])
    visited[start_x][start_y] = 1
    
    while queue:
        now_x, now_y= queue.popleft()
        for direct in directs:
            next_x = now_x + direct[0]
            next_y = now_y + direct[1]
            if 0 <= next_x < len(maps) and 0 <= next_y < len(maps[0]) and maps[next_x][next_y] != "X" and visited[next_x][next_y] == 0:
                if maps[next_x][next_y] == target:
                    return visited[now_x][now_y]
                visited[next_x][next_y] = visited[now_x][now_y] + 1 # step count plus 1
                queue.append([next_x, next_y])
    return -1 # not find target
    
def find_target(maps, target):
    x, y = 0, 0
    for i, row in enumerate(maps):
        if target in row:
            x = i
            y = row.index(target)
            break
        
    return [x, y]

def solution(maps):
    directs = [(-1, 0), (1, 0), (0, -1), (0, 1)] # up down left right
    x, y = find_target(maps, "S") # start index
    L_x, L_y = find_target(maps, "L") # switch index
    step1 = move_target(maps, directs, x, y, "L")
    step2 = move_target(maps, directs, L_x, L_y, "E")
    
    return -1 if step1 == -1 or step2 == -1 else step1 + step2

 

전형적인 BFS 문제죠?

 

저 같은 경우는

 

우선 시작 위치, 스위치 위치를 찾고

 

시작 > 스위치 가는 경로

 

and

 

스위치 > 출구 가는 경로

 

이렇게 경로를 나눠서 구했습니다.

 

각각에 경우로 구하지 않으면

 

스위치를 키고 왔던 길을 돌아가야 하는 상황에

 

방문처리 때문에 할 수 없는 경우가 생기기 때문입니다.

 

그렇게 두가지 경우를 구하고

 

마지막에 각각의 경우가 -1이 없는지 확인하고

 

없으면 두 개의 값을 더해서 반환

 

있으면

 

-1을 반환했습니다.

 

이게 최적화를 위해서는

 

def solution(maps):
    directs = [(-1, 0), (1, 0), (0, -1), (0, 1)] # up down left right
    x, y = find_target(maps, "S") # start index
    L_x, L_y = find_target(maps, "L") # switch index
    step1 = move_target(maps, directs, x, y, "L")
    if step1 == -1:
        return -1
    step2 = move_target(maps, directs, L_x, L_y, "E")
    if step2 == -1:
        return -1
    return step1 + step2

 

경로를 찾을 때마다

 

검사하는게 좋겠지만....

 

코드가 너무 못생겨져서 전 위의 방식으로 처리했습니다.

 

다음에 또 봐요