[ BOJ 1261 ] 알고스팟(Python)

문제

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

[1,1]에서 [n,m]까지 이동하러면 벽을 최소 몇개 부수어야 하는지 구하는 문제다.
벽 부수고 이동하기 문제와 비슷한 듯 다르다.
어떻게 풀어도 틀리다고 뜨고,, 시간 초과, 메모리 초과가 나서 눈물이 났다.

틀린 문제 풀이

처음엔 bfs와 deque를 이용해서 풀어보려고 했다.
visited 리스트로 방문한 곳을 체크해주었고,
dist 리스트에 각 위치까지 최소로 부신 벽의 개수를 저장해주었다.

• 방문을 하지 않았던 위치이고, 길일땐 벽을 부실 필요가 없으므로 dist 리스트에 현재 위치와 같은 벽의 개수를 저장해주었다.
  dist[nx][ny] = dist[cur_x][cur_y]
q.append(((nx,ny),cnt))
• 방문을 하지 않았던 위치이고, 벽일땐 벽을 부시고 dist 리스트에 현재 위치에 1을 더한 값과 현재 위치 중 더 작은 값을 저장해주었다.
  dist[nx][ny] = min(1 + dist[cur_x][cur_y], dist[nx][ny])
q.append(((nx,ny),cnt+1))

🥺 문제는 방문한 곳이었다.
같은 위치여도 벽을 부시고 방문한 곳과 벽을 부시지 않고 방문한 곳은 다른 값을 갖는다.

처리를 어떻게 해줘야할지 모르겠어서 한참을 해맸다.
디버깅을 해서 값을 계속 확인했는데도 감이 잡히지 않아서 결국 다른 사람의 풀이를 보게됐다.

맞은 문제 풀이

정말 직관적이고 간단하다.
풀이를 보면서 친구들과 감탄했다.
이게 바로 소질 있는 사람이 작성한 코드인가?ㅠ
wow. . . .

• visited 리스트를 따로 만들지 않고, dist의 모든 값을 -1로 초기화해준다.
  dist의 값이 -1이면 방문하지 않은 것이다.

1. 방문한 곳이면 continue 해준다.
2. 벽이면 queue의 오른쪽에 넣어준다. 벽을 부셨으므로 dist 리스트에 현재 dist 값에 1을 더한 값을 저장해준다.
   q.append((nx,ny))
dist[nx][ny] = dist[cur_x][cur_y] + 1
3. 길이면 queue의 왼쪽에 넣어준다.
   q.appendleft((nx,ny))
dist[nx][ny] = dist[cur_x][cur_y]

• 코드에서 queue의 요소를 꺼낼 땐, 항상 왼쪽에서 pop해준다.
  따라서 ⭐️길일땐 벽일때보다 먼저 방문해주기 위해서 queue의 왼쪽에 넣어주는 것⭐️이다.

진짜 천재 아니냐고요,,, 억덕게.. 이런 생각을... ,

코드

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

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

# 가로 M, 세로 N
m, n = map(int,input().rstrip().rsplit())
matrix = []

for _ in range(n):
    row = input().rstrip()
    matrix.append(row)

dist = [[-1] *(m+1) for _ in range(n+1)]
dist[0][0]=0

q = deque()
q.append((0,0))


while q:
    p = q.popleft()
    cur_x, cur_y = p[0], p[1]

    for k in range(4):
        nx = dx[k] + cur_x
        ny = dy[k] + cur_y
        if (0 <= nx < n and 0 <= ny < m):
            #방문 했으면 continue
            if dist[nx][ny]!=-1:
                continue

            # 벽이면 q의 오른쪽에 넣어줌
            if matrix[nx][ny] == '1':
                q.append((nx,ny))
                dist[nx][ny] = dist[cur_x][cur_y] + 1 
            else:
                # 길이면 q의 왼쪽에 넣어줌
                # => 더 빨리 탐색하기 위해서 왼쪽에 넣어줌
                q.appendleft((nx,ny))
                dist[nx][ny] = dist[cur_x][cur_y] 

print(dist[n-1][m-1])