[프로그래머스] Lv.2 미로탈출 [논리적 허점 + 코드 + 해설]

구현 & BFS & 최단경로

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

프로그래머스

코드

from collections import deque

def bfs(s, e, gx, gy, n, m, maps):
    visited = [[0] * m for _ in range(n)]
    visited[s][e] = 1
    queue = deque([[s, e]])
    
    result = 0
    dx = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    while queue:
        q = queue.popleft()
        x, y = q[0], q[1]

        isActive = True
        for idx in range(4):
            nx = dx[idx][0] + x
            ny = dx[idx][1] + y
            
            if nx < 0 or nx >= n or ny < 0 or ny >= m or visited[nx][ny] != 0 or maps[nx][ny] == "X":
                continue
            
            if nx == gx and ny == gy:
                visited[nx][ny] = visited[x][y] + 1
                result = visited[nx][ny]
                isActive = False
                break
            
            else:
                queue.append([nx, ny])
                visited[nx][ny] = visited[x][y] + 1
                
        if not isActive:
            break

    return result

def solution(maps):
    answer = -1
    
    n = len(maps)
    m = len(maps[0])
    
    startX, startY = 0, 0
    leverX, leverY = 0, 0
    goalX, goalY = 0, 0
    
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "S":
                startX, startY = i, j
            elif maps[i][j] == "L":
                leverX, leverY = i, j
                
            elif maps[i][j] == "E":
                goalX, goalY = i, j
    
    one = bfs(startX, startY, leverX, leverY, n, m, maps)
    two =  bfs(leverX, leverY, goalX, goalY, n, m, maps)

    if one > 0 and two > 0:
        answer =  (one + two) - 2
        
    
    return answer

 

설명

 원래 코드에서 논리적 허점부터 시작하려고 합니다. 잘못된 코드는 올리지 않았으며 제가 잘못 작성했던 논리적 모순이 있었던 코드를 기반으로 먼저 설명하고 이후 AC를 받은 코드를 기준으로 설명하겠습니다. 논리적 허점이 있었던 생각의 흐름은 이러했습니다.

 

 

1.

"레버를 당겨야만 미로탈출문이 열리는 거니까 레버를 당기지 않고 탈출지에 도착했다면

탈출을 한 게 아니지만 만약 어떠한 경로들 중에서라도 레버를 당기고 난 이후 도착한 경로들이 최단 경로가 되지 않을까?"

=

즉 레버는 다른 경로가 당기고 도착은 다른 경로가 한다. ( 0.0 ) 점수

 

 

 

2.

"레버를 당기는 위치에 왔다면 레버를 당기지 않은 곳들은 결코 최단 경로가 될 수 없기 때문에

현재 위치에서 시작하는 것들(레버 위치에서 경로를 탐색하는 것)을 제외하고

나머지 경로들은 이제부터 큐에 넣지 않는다. 이렇게 한다면 현재 위치까지가 레버까지의 최단경로가 될 거고 여기서부터 도착지까지 찾는 게 최단경로가 아닐까?"

=

즉 레버 위치까지 최단경로로 도달 + 레버 위치에서부터 도착지까지 이어서 도달시킨다. ( 30.1 ) 점수

 

 

 위 두 생각을 모두 구현했던 결과의 점수와 함께 작성해 보았다. 우선 첫 번째부터 설명을 해보려고 한다. 첫 번째 논리의 허점은 문제 상에서 먼저 레버까지 도달한 후 최단경로로 이동하면 된다고 명시했다. 그리고 간과한 사실 하나는 시작점, 통로, 레버, 출구 모두 여러 번 갈 수 있다고 했다. 그렇다면 레버를 당기지 않고 최단경로를 찾게 되는 거니까 문제 상에서 구현하고자 하는 방향이 아닌 게 된다. 왜냐하면 먼저 레버까지 간다음에 탈출지까지 가라고 했기 때문이다. 또 한 가지는 그렇다면 레버를 당기러 가기 위해서 방문했던 지점들 중 탈출 지점이 있으면 어떻게 할 건가? 이것이 곧 두 번째 생각의 허점으로 이어진다. 그렇게 된다면 당연히 탈출지점은 절대로 찾을 수 없게 된다. 설령 예제 케이스에서는 도달했다고 해도 논리적으로 방문한 곳을 재방문하지 않기 때문에 방문한 곳이 탈출 지점이라고 한다면 재방문이 불가능하여 탈출지점에 도달할 수 없다. 이게 가능한 이유는 (탈출 지점은 레버를 당기지 않아도 지나갈 수 있기 때문이고 지나갈 수 있다는 건 그 위치에 도달도 가능하거나 or 지나치는 게 가능하다. 따라서 해당 위치에 방문도 가능하다.) 위와 같은 사실들 때문에 첫 번째 논리는 정답을 받지 못했다.

 

 두 번째논리의 허점으로는 앞서 언급했었던 탈출지점이 방문했던 지점이라면 결코 탈출할 수 없다. 따라서 최단 경로로 가는 것을 따로 구현하긴 했지만 여러 번 반복가능 하다는 사실을 간과한 채 코드를 작성해서 30점 정도를 받고 정답을 받지 못했다. 그리고 마지막으로 여러 아이디어 참조를 바탕으로 내가 간과한 사실이 코드에서 논리적인 허점을 보여주고 있구나를 깨닫고 다시 작성하여 AC를 받을 수 있었다. 결국 조건을 제대로 이해하지 못해서 생긴 일이며 첫 번째 논리 같은 경우도 문제의 조건등을 제대로 따져보지 못했기 때문에 나왔던 생각이라고 볼 수 있을 것 같다.

 

 추가적으로 위 코드에서 -2를 빼게 된 이유는 예제 상에서 첫 시작을 0으로 두고 있으며 나는 방문을 했다는 뜻에서 1로 시작했기 때문에 도달한 위치들까지 총시작점에서 시작한 1과, 레버에서 도착지까지 간 1을 빼주기 위해 총 2를 빼주었다고 볼 수 있다. 또한 둘 중 하나라도 방문을 하지 못했다면 결국 -1리턴하게 된다 (또는 둘다 도달하지 못했다면). 레버까지 도달하지 못했다면 결국 탈출지를 열 수 있는 방법이 사라졌기 때문에 도달한다고 하여도 탈출이 불가능하다. 탈출지를 찾지 못했다는 건 탈출지가 갈 수 없는 곳으로 막혀있다면 결국 탈출지도 레버는 당겼지만 탈출은 못할 수도 있는 상황이 있기 때문에 둘 다 만족하는 경우에만 즉 둘 다 방문한 경우에만 답을 도출할 수 있도록 했다.