[BOJ_16954/Python] 움직이는 미로 탈출

문제

16954번: 움직이는 미로 탈출

16954번: 움직이는 미로 탈출

---

풀이

import sys
from collections import deque
input = sys.stdin.readline


def bfs(x, y):
    q = deque()
    q.append((x, y, 0))  # x, y, 시간

    dx = [-1, -1, -1, 0, 0, 0, 1, 1, 1]
    dy = [-1, 0, 1, -1, 0, 1, -1, 0, 1]

    while q:
        x, y, time = q.popleft()

        for i in range(9):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < 8 and 0 <= ny < 8:
            	# 현재 벽 위치
                present_wall = list(filter(lambda a: 0 <= a[0] < 8 and 0 <= a[1] < 8,
                                           list((map(lambda a: (a[0] + time, a[1]), wall)))))
                if (nx, ny) not in present_wall:  # 이동하려는 곳이 벽이 아님
                    # 캐릭터의 위치 == 벽 위치라면 게임 오버
                    moved_wall = list(filter(lambda a: 0 <= a[0] < 8 and 0 <= a[1] < 8,
                                             list((map(lambda a: (a[0] + time + 1, a[1]), wall)))))
                    if (nx, ny) in moved_wall:
                        continue
                    # 만약 모든 벽이 나보다 아래에 있으면 게임 끝
                    if len(list(filter(lambda a: a[0] > nx, moved_wall))) == len(moved_wall):
                        return 1
                    # 도착했으면 게임 끝
                    if nx == 0 and ny == 7:
                        return 1

                    q.append((nx, ny, time + 1))

    return 0  # 이동 불가


# 입력
arr = []
wall = []
for i in range(8):
    line = list(input().strip())
    for idx, val in enumerate(line):
        if val == '#':
            wall.append((i, idx))
    arr.append(line)

# 풀이 & 출력
print(bfs(7, 0))

1. visited 는 캐릭터가 움직이지 않는 경우를 고려해줄 수 없어서 사용하지 않았다.

2. 이동하려는 좌표 (nx, ny)가 범위 내이고 벽이 아니라면 이동할 수 있게 한다.

3. 만약 새로 이동한 좌표에 움직인 벽이 겹쳐지면 게임 오버 (return 0)

4. 게임이 끝나는 경우는 두 가지 케이스를 생각해봤다. 목표했던 좌표에 도달하는 경우와, 모든 벽이 캐릭터 아래에 위치하는 경우다. 벽은 계속 아래로만 이동하기 때문에 캐릭터보다 아래에 위치한 벽은 캐릭터의 이동에 전혀 영향을 주지 않는다. 따라서 모든 벽이 캐릭터 아래에 위치한다면 캐릭터는 무조건 목적지에 도달할 수 있다고 처리했다.

 

---

사실 잘 짠 코드는 아니라고 생각한다. 만약 보시는 분들이 있다면 참고만 하시길.. 특히 반복할때마다 벽 위치를 계속 만들어서 판단하는게 효율적으로 많이 안 좋아보인다. 시간별로 달라지는 벽의 위치를 미리 만들어놓고 가져다 쓰면 좋을 것 같다!