백준 1261번 - 알고스팟

미로에 갇혔다. (N, M) 까지 이동하는데 벽을 몇개 부셔야 하는지 구하시오.

# 틀린 코드

아이디어는 쉬웠다.
그냥 (0,0) 부터 (N, M)까지 최단거리로 미로탈출 한 다음에 그 과정에서 벽을 만난 횟수만 세면 된다.
시작은 쉬웠는데 계속 벽 세는 부분에서 헤맸다.

벽을 만날 때마다 count += 1 을 해주면 queue에 들어가는 모든 경우의 수에 count가 증가한다.

그 다음 시도한 건 상하좌우 반복문 돌기 전에 변수에 넣어둔 후 그 값으로 더해나갔다. 얼추 해결한 듯 했으나 최단거리는 벽을 부수는데 벽을 안부수는 길도 있을 때가 있어서 오류가 났다.

벽 부수는 걸 어떻게 처리하지????????

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

N, M = map(int, input().split())
graph = []
visited = [[0 for _ in range(N)] for _ in range(M)]
for _ in range(M):
  graph.append(list(map(int, input().strip())))

mx = [-1, 1, 0, 0]
my = [0, 0, -1, 1]

def bfs():
  queue = deque([[0, 0]])
  while queue:
    x, y = queue.popleft()

    if x == M-1 and y == N-1:
      return True


    for i in range(4):
      dx = x + mx[i]
      dy = y + my[i]

      if dx < 0 or dy < 0 or dx >= M or dy >= N:
        continue

      elif visited[dx][dy] == 0:
        visited[dx][dy] = 1
        if graph[dx][dy] == 1:
          graph[dx][dy] = graph[x][y] + 1
        queue.append([dx, dy])

bfs()
print(max(graph[N-1][M-2], graph[N-2][M-2]))

# 정답 코드

탐색문제에서 어떤 것을 count를 할 때는 맵의 값을 이용하는 것이 좋다.
예를 들어, 벽의 개수를 센다고 하면
graph[dx][dy] = graph[x][y] + 1
이런 식으로 세면 네 방향을 세더라도 중복해서 세지 않는다.

추가적으로 이 문제에서 놓친 부분은 우선순위다. 최단거리가 아닌 벽을 최소로 부시는 게 이 문제의 목적이다. 그 부분을 코드에선 그래프가 0일 때 queue에 앞에 삽입하고, 그래프가 1일 때 queue에 뒤에 삽입해서 벽이 없는 좌표부터 탐색하도록 구현하였다.

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

N, M = map(int, input().split())
visited = [[-1 for _ in range(N)] for _ in range(M)]
graph = []
for _ in range(M):
  graph.append(list(map(int, input().strip())))


def bfs(x, y):
  queue = deque()
  queue.append([x, y])
  visited[x][y] = 0
  mx = [-1, 1, 0, 0]
  my = [0, 0, -1, 1]

  while queue:
    x, y  = queue.popleft()
    for i in range(4):
      dx = x + mx[i]
      dy = y + my[i]
      if dx < 0 or dy < 0 or dx >= M or dy >= N:
        continue
      if visited[dx][dy] == -1:
        if graph[dx][dy] == 0:
          queue.appendleft([dx, dy])
          visited[dx][dy] = visited[x][y]
        elif graph[dx][dy] == 1:
          queue.append([dx, dy])
          visited[dx][dy] = visited[x][y] + 1
  
  print(visited[M-1][N-1])


bfs(0, 0)