[Python] 백준 16954번 움직이는 미로 탈출

문제바로가기

---

문제 설명

해당 문제는 8*8 체스판이 존재하고, 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 이 문제의 특징은 벽이 움직이고(1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고) 욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동 여부를 구하는 것

문제 풀이

---

벽이 한 칸 내려오는 것 = 욱제가 한 칸 위로 올라가는 것
또한 욱제가 맨 위칸으로 올라가기만 하면, 가장 오른쪽으로 갈 수 있다.
(1초 뒤에는 욱제와 같은 칸에 있는 벽들이 전부 아래로 내려가고, 욱제는 그 칸에 그대로 있으므로)

💡 맨 처음에 이 문제를 접근할떄, 체스판의 정보를 deque()로 받고 1초가 지날 때마다 맨윗칸을 pop을 시켜주고 빈칸을 추가했다. 하지만 이분의 풀이를 참고하니 애초에 pop시킬 필요가 없다.

애초에 최소 움직이는 수를 구하는것도 아여서 벽을 이동할 필요없이 visited[ni - 1]을 하면 하나씩움직일 #을 계산하것이므로 if graph[i][j] == '#':여기에걸림

from collections import deque
input = __import__('sys').stdin.readline
n = 8
graph = [list(input().strip()) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
dx = [0, 0, 1, -1, 1, -1, 1, -1, 0]
dy = [1, -1, 0, 0, 1, 1, -1, -1, 0]

q = deque()
q.append((7, 0))
visited[7][0] = True
ans = 0
while q:
    i, j = q.popleft()
    if graph[i][j] == '#':
        continue
    for idx in range(n + 1):
        ni = i + dy[idx]
        nj = j + dx[idx]
        if ni < 0 or ni >= n or nj < 0 or nj >= n or graph[ni][nj] == '#':
            continue
        if ni == 0:
            ans = 1
        if not visited[ni - 1][nj]:
            visited[ni - 1][nj] = True
            q.append((ni - 1, nj))
print(ans)

정리

• 문제를 접근할떄 시간복잡도랑 메모리를 최소한 할 수 있는 풀이법으로 접근하려고 계속 생각하자
• 항상 문제를 맞추더라도, 다른 사람의 풀이를 참고해보자