[플랫폼: Python] 16954 - 움직이는 미로 탈출

[문제]

https://www.acmicpc.net/problem/16954

생각보다 손이 많이 갔던 문제입니다.

 

처음에 놓쳤던 부분은 벽이었습니다. 벽을 내릴 때, 순차적으로 내리지 않고 입력받은 순으로 처리하다 보니 잘못된 처리가 수행되었습니다.

 

다음으로 놓쳤던 부분은 이동한 벽과 캐릭터가 만났을 때 처리하는 것이었습니다, BFS를 사용하게 되면 하나의 방향이 아니라 이동 가능한 9개의 방향과 움직인 벽을 고려해야 하는데, 이를 어떻게 처리해야 할지 고민하는 데 많은 시간을 소요했습니다.

---

[초기화]

    def __init__(self):
        self.grid = [list(input()) for _ in range(8)]
        self.walls = set((i, j) for i in range(8) for j in range(8) if self.grid[i][j] == '#')

벽의 위치를 기록합니다.

 

이는 이동한 곳이 벽과 접촉되는지 확인하는 데 사용됩니다.

---

[풀이]

    def move_wall(self):
        next_walls = set()
        for x in range(8):
            for y in range(7, -1, -1):
                if self.grid[y][x] == '#':
                    self.grid[y][x] = '.'
                    if y < 7:
                        self.grid[y + 1][x] = '#'
                        next_walls.add((y + 1, x))

        self.walls = next_walls

벽을 이동함과 동시에 이동한 위치를 기록합니다.

 

벽의 이동은 밑에서부터 위로 순차적으로 처리합니다.

    def move_wook(self):
        dq = deque([(7, 0, 0)])
        visited = {(7, 0, 0)}  # 가만히 있는 선택지도 있으므로 시점을 추가

        while dq:
            for _ in range(len(dq)):  # 현재 시점 처리, 즉 임의의 t일 때 큐에 들어온 값을 모두 처리해야 함
                y, x, t = dq.popleft()
                if y == 0 and x == 7:
                    print(1)
                    return

                if (y, x) in self.walls:  # 움직인 벽에 접촉되는 지점들이 있다면 무시
                    continue
    
                for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1), (0, 0)]:
                    my, mx = y + dy, x + dx
                    if 0 <= my < 8 and 0 <= mx < 8 and self.grid[my][mx] == '.' and (my, mx, t + 1) not in visited:
                        dq.append((my, mx, t + 1))
                        visited.add((my, mx, t + 1))
    
            if self.walls:
                self.move_wall()

        print(0)

일반적인 BFS의 흐름과 유사하나, 시점을 고려해야 합니다.

 

왜냐하면, 캐릭터가 이동한 후 벽을 움직여야 하는데, 임의의 시점 t에 이동 가능한 포인트가 4개일 때 일반적인 BFS라면 앞선 포인트를 처리하고 벽을 이동시키게 됩니다.

 

위와 같은 상황이 발생하면, 나머지 3개의 포인트는 원래라면 움직일 수 포인트라도 움직이지 못하는 상황이 발생하게 됩니다.

 

그러므로 특정 시점에 들어온 데이터는 벽을 이동하기 전에 모두 처리해야 합니다.

 

또한 움직이지 않는 선택지가 있으므로 방문 처리를 수행할 때 시점으로 구분합니다.

 

물론 최단거리 방문이 아니므로 방문 처리를 수행하지 않아도 되지만, 백준 기준 시간 측면에서 약 50배 차이가 납니다.

    def solve(self):
        self.move_wook()

---

[전체 코드]

from collections import deque


class Main:
    def __init__(self):
        self.grid = [list(input()) for _ in range(8)]
        self.walls = set((i, j) for i in range(8) for j in range(8) if self.grid[i][j] == '#')

    def move_wall(self):
        next_walls = set()
        for x in range(8):
            for y in range(7, -1, -1):
                if self.grid[y][x] == '#':
                    self.grid[y][x] = '.'
                    if y < 7:
                        self.grid[y + 1][x] = '#'
                        next_walls.add((y + 1, x))

        self.walls = next_walls

    def move_wook(self):
        dq = deque([(7, 0, 0)])
        visited = {(7, 0, 0)}  # 가만히 있는 선택지도 있으므로 시점을 추가

        while dq:
            for _ in range(len(dq)):  # 현재 시점 처리, 즉 임의의 t일 때 큐에 들어온 값을 모두 처리해야 함
                y, x, t = dq.popleft()
                if y == 0 and x == 7:
                    print(1)
                    return

                if (y, x) in self.walls:  # 움직인 벽에 접촉되는 지점들이 있다면 무시
                    continue
    
                for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1), (0, 0)]:
                    my, mx = y + dy, x + dx
                    if 0 <= my < 8 and 0 <= mx < 8 and self.grid[my][mx] == '.' and (my, mx, t + 1) not in visited:
                        dq.append((my, mx, t + 1))
                        visited.add((my, mx, t + 1))
    
            if self.walls:
                self.move_wall()

        print(0)

    def solve(self):
        self.move_wook()


problem = Main()
problem.solve()

---