미로 탈출

날짜 : 2023. 06. 07

사용 언어 : python

 

문제

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

 

코드

# 레버 위치 찾기 -> 레버까지의 거리 구하기(BFS) -> 레버에서 출구까지 거리 구하기(BFS)
from collections import deque
def solution(maps):
    m = len(maps)
    n = len(maps[0])
    i, j = 0, 0
    flag = False
    for i in range(m):
        for j in range(n):
            if maps[i][j] == "S":
                r, c = i, j
                break
    queue = deque()
    queue.append([r, c])
    visited = [[-1] * n for _ in range(m)]
    visited[r][c] = 0
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    while queue:  # 레버찾기
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx in range(m) and ny in range(n):
                if visited[nx][ny] == -1:  # 방문 x
                    visited[nx][ny] = visited[x][y] + 1  # 방문처리
                    if maps[nx][ny] == "L":  # 레버 발견
                        r, c = nx, ny
                        # flag = True
                        break
                    elif maps[nx][ny] == "O" or maps[nx][ny] == "E":  # 이동 가능경로
                        queue.append([nx, ny])
    # if not flag: return -1
    tmp = visited[r][c]
    visited = [[-1] * n for _ in range(m)]
    visited[r][c] = tmp
    queue = deque()
    queue.append([r, c])
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx in range(m) and ny in range(n):
                if visited[nx][ny] == -1:  # 방문 x
                    visited[nx][ny] = visited[x][y] + 1  # 방문처리
                    if maps[nx][ny] == "E":  # 출구 발견
                        return visited[nx][ny]
                    elif maps[nx][ny] == "O" or maps[nx][ny] == "S":  # 이동 가능경로
                        queue.append([nx, ny])
    return -1

 

 

풀이

- 행, 열의 길이를 구한 다음, 시작점의 인덱스를 구한다

- BFS를 사용해서 레버(L)의 위치를 구하고, 레버를 찾지 못하는 경우 출구에 도달해도 무의미하기 때문에 -1을 리턴

- 레버를 찾았다면 또다시 BFS를 돌려서 도착지 E에 도달한 경우 결과값 출력

- 도달하지 못한 경우(큐가 빈 경우) -1 출력

- 2차원 리스트 visited를 만들어 이동거리를 체크하고, BFS를 돌릴 때마다 선언

 

 

알게된 점

- 수업시간에 푸니까 집중이 안된다..

- 점심때 푸니까 문제없이 풀 수 있었던 것 같다.

- BFS를 돌릴 때 이동 가능한 통로를 단순 "O"만 고려하다 보니까 레버를 구하는 과정에서 출구를 거쳐야 하는 케이스와 출구를 구하는 경우 시작점을 무조건 거쳐야 하는 케이스가 있었기 때문에 이를 간과했던 것 같다.

(반례 : ["SEOOOOL"] -> S에서 L까지 도달하는 데 E를 거치게 되어있음. E에서 enqueue를 하지 않으면 E에서 컷)

- 그랬더니 테케 2개를 틀려서 보니까 레버 자체에 도달하지 못하는 케이스도 있었다.

- 그래서 이를 반영해서 flag를 넣고, flag값이 False인 경우 -1 출력했다.

 

참고 사이트

-