[Gold III] 움직이는 미로 탈출 - 16954 (BFS)

[Gold III] 움직이는 미로 탈출 - 16954

문제 링크

성능 요약

메모리: 34208 KB, 시간: 68 ms

분류

너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.

이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.

1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.

욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.

입력

8개 줄에 걸쳐서 체스판의 상태가 주어진다. '.'은 빈 칸, '#'는 벽이다. 가장 왼쪽 아랫칸은 항상 벽이 아니다.

출력

욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력한다.

 

풀이 방법

그냥 간단한 BFS에 벽을 내리는 조건이 조금 더해진 문제인줄 알았지만, 역시 골드3은 골드3이다. 생각보다 엣지 케이스에 대해 생각할 게 많았다. 이 풀이를 본다면, 아마도 맞왜틀(맞는데 왜 틀렸지?) 상황을 거의 해결할 수 있을 것이다.

 

일단 처음 생각한 풀이 방법이다.

1. 상, 하, 좌, 우, 제자리,대각선 총 9방향 탐색을 한다. (탐색 조건 : 벽(#)이 아니고 방문하지 않았으며 8x8 범위 내에서만)

2. 1번을 한 번 실행한 후, 벽이 있을 경우 벽을 한 칸씩 내려준다.

3. 1번을 또 실행할 때 벽이 내려와서 부딪혔다면 해당 좌표는 탐색에서 제외시킨다.

4. 큐가 모두 비었을 때 최종적으로 3번의 영향을 받지 않고 도착 지점(0, 7)에 도달했다면, 1을 출력한다. 그렇지 않다면 0 출력.

 

풀이 방법만 보기에는 빠르게 구현을 할 수 있을 것 같다. 그러나, 엣지 케이스에 대해 잘 생각해주어야 한다. 이제부터 놓친 엣지 케이스에 대해 해결한 방법을 소개한다.

 

첫 시도 : 마지막 테스트 케이스 오답.

오답 원인 : 풀이 방법의 2번이 제대로 동작되지 않았다. 

해결 방법 : 9방향 탐색 후  벽을 내릴 때에는 bfs에서 현재 큐에 들어있는 만큼 모두 큐를 빼줘야한다.

while q: =>  while q: for _ in range(len(q):

 

두번째 시도 : 제출 시 23%에서 틀렸습니다.

오답 원인 : 엣지 케이스 중 세로로 벽이 연속으로 떨어지는 상황일 경우, 벽을 내리는 알고리즘을 현재 벽을 부숴주고 다음 벽을 만들었기 때문에 세로로 연속으로 벽이 붙어있다면 하나의 벽이 사라진다.

해결 방법 : 벽의 좌표를 저장할 때 그래프의 맨 아래 벽부터 입력을 받거나, 배열을 큐로 생성한다면 appendleft를 이용하여 해결할 수 있다.

 

세번째 시도 : 제출 시 90%에서 틀렸습니다.

오답 원인 : 제자리에 있어야 할 경우가 있기 때문이다.

해결 방법 : 출발 지점(7,0)에서의 방문 체크를 풀어준다.

ex) (위쪽 행 생략)

#.......
.#......
.#......

그렇다면,, 왜 첫 번째 방문만 방문 체크를 풀어줘야 하는지에 대한 궁금증이 생길 수가 있을 것이다. 왜냐하면 다른 장소에서도 가만히 있을 경우도 생각해야 하지 않냐는 의문이 들 수 있기 때문이다.

그래서 그냥 눈대중으로 보기에는 감이 잘 안와서 해당 케이스를 생각해서 직접 그려 보았다.

ex) (위쪽 행 생략)

 . # .
# . #
# . #
.  . #

무조건 제자리에 있어야 할 경우를 최대한 생각하여 그려보았다. 그러나, 첫 출발 지점이 아니기 때문에 옆면에서 넘어오는 것이므로 대각선 위로 오는 방법이 존재한다. 그러므로 첫 출발 지점만 방문을 풀어주면 로직이 완성된다는 것을 입증할 수 있다.

from collections import deque

# 8 x 8 행렬
graph = []
for i in range(8):
    graph.append(list(input()))
# 하, 상, 우, 좌, 대각 x 4, 제자리
dx = (1,-1,0,0,1,1,-1,-1,0)
dy = (0,0,1,-1,1,-1,1,-1,0)
visited = [[False for _ in range(8)] for _ in range(8)] # 방문 체크
wall = deque() # 벽이 있는 좌표
answer = 0 # 도착 여부
wall_count = 0 # 남아있는 벽의 개수

# 벽 좌표 넣기
for i in range(8):
    for j in range(8):
        if graph[i][j] == '#':
            wall.appendleft((i,j))

def bfs(a, b):
    global answer, visited
    q = deque()
    q.append((a,b))
    
    while q:
        for _ in range(len(q)):
            x, y = q.popleft()

            # visited[x][y] = True
            if x == 0 and y == 7:
                answer = 1
                return
            if graph[x][y] == '#':
                continue

            for i in range(9):
                nx, ny = dx[i] + x, dy[i] + y
                if 0 <= nx < 8 and 0 <= ny < 8 and visited[nx][ny] == False and graph[nx][ny] != '#':
                    visited[nx][ny] = True
                    q.append((nx,ny))

        # 내려야 할 벽이 존재한다면
        if wall:
            visited = [[False for _ in range(8)] for _ in range(8)] # 방문 체크 초기화
            for _ in range(len(wall)):
                # 한 번 이동했으니 벽을 내려준다.
                xx, yy = wall.popleft()
                if xx < 7:
                    graph[xx][yy] = '.'
                    graph[xx+1][yy] = '#'
                    wall.append((xx+1,yy))
                elif xx == 7:
                    graph[xx][yy] = '.'

# 왼쪽 아래 출발
bfs(7,0)

print(answer)