프로그래머스 / 미로 탈출 / python

처음 시도 한 코드

from collections import deque
direction = [[1,0], [-1,0], [0,1], [0,-1]]

def solution(maps):
    answer = 0
    X = len(maps)
    Y = len(maps[0])
    for i in range(X):
        for j in range(Y):
            if maps[i][j] == 'S':
                sx, sy = i, j
                
    q = deque([[sx, sy, 0]])
    visited = [[False] * Y for _ in range(X)]
    lever = False
    
    while q:
        x, y, deph = q.popleft()
        visited[x][y] = True
        
        if maps[x][y] == 'L':
            lever = True
            visited = [[False] * Y for _ in range(X)]
            visited[x][y] = True
            
        if lever and maps[x][y] == 'E':
            return deph
            
        for d in direction:
            nx, ny = x+d[0], y+d[1]
            if 0 <= nx < X and 0 <= ny < Y:
                if not visited[nx][ny] and maps[nx][ny] != 'X':
                    visited[nx][ny] = True
                    q.append([nx,ny,deph+1])
                    
    return -1
    

이 코드의 문제점

위 작성한 코드의 방식은 레버에 방문하면 lever 변수를 True로 변경해줘서 lever가 True일 때 방문 여부를 확인하는 visited를 초기화 하고 그 이후 bfs를 마저 진행하면서 탈출하는 방법이다.

이 코드의 반례는 아래와 같다.

SEOOO
OXXXO
OXXXO
OXXXO
LXXXO

이러한 예제에서 bfs를 진행하면 처음에 L 방향과 E 방향으로 진행한다.
둘 다 그 방향대로 진행하다가 L을 만났을 때 visited를 초기화 하므로
처음에 E 방향으로 진행하던 bfs가 E쪽으로 돌아오게 된다.

그래서 틀린 답이 나오게된다.

이를 해결하고자 bfs 진행할 때 레버의 방문여부를 확인하는 lever를 공용으로 사용하지 않고 매번 bfs 인자 값으로 넘겨주면 visited를 lever 방분 전과 방문 후를 따로 사용한다.

from collections import deque
direction = [[1,0], [-1,0], [0,1], [0,-1]]

def solution(maps):
    answer = 0
    X = len(maps)
    Y = len(maps[0])
    for i in range(X):
        for j in range(Y):
            if maps[i][j] == 'S':
                sx, sy = i, j
    
    lever = False
    visited = [[False] * Y for _ in range(X)]
    visited_l = [a[:] for a in visited]
    q = deque([[sx, sy, 0, lever]])
    
    while q:
        x, y, deph, lever = q.popleft()
        
        if not lever:
            visited[x][y] = True
        else:
            visited_l[x][y] = True
        
        if maps[x][y] == 'L':
            lever = True
            visited_l[x][y] = True
            
        if lever and maps[x][y] == 'E' and visited_l[x][y]:
            return deph
            
        for d in direction:
            nx, ny = x+d[0], y+d[1]
            if 0 <= nx < X and 0 <= ny < Y:
                if not lever:
                    if not visited[nx][ny] and maps[nx][ny] != 'X':
                        visited[nx][ny] = True
                        q.append([nx,ny,deph+1, lever])
                else:
                    if not visited_l[nx][ny] and maps[nx][ny] != 'X':
                        visited_l[nx][ny] = True
                        q.append([nx,ny,deph+1, lever])
                    
    return -1

---

이제 알고리즘 적용하는건 문제 없다고 생각했는데 이렇게 한번 꼬인? 문제를 만나면 지금처럼 당연하게 오류가 반겨준다.... 좀 더 깊게 생각해서 변수를 사용할 필요를 느꼈다.