[Algorithm] 1261. 알고스팟

1261: 알고스팟(BFS)

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

• 문제 티어 : G4
• 풀이 여부 : Solved
• 소요 시간 : 24:16

정답 코드

import sys
from collections import deque

input = sys.stdin.readline

M, N = map(int, input().rstrip().split()) # M : 가로, N : 세로
arr = [list(map(int, input().rstrip())) for _ in range(N)]
visited = [[-1]*M for _ in range(N)]

def bfs(x, y):
  dq = deque([(x, y)])
  visited[x][y] = 0 # 운영진의 현재 위치(0, 0)

  dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
  while dq:
    x, y = dq.popleft()
    for i in range(4):
      nx, ny = x + dx[i], y + dy[i]
      if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == -1:
        if arr[nx][ny] == 0: # 벽을 뚫지 않아도 되는 경우
          dq.appendleft((nx, ny))
          visited[nx][ny] = visited[x][y]
        else: # 벽을 뚫어야 하는 경우
          dq.append((nx, ny))
          visited[nx][ny] = visited[x][y] + 1

  return visited[N-1][M-1]

print(bfs(0, 0))

접근 방식

BFS 기본 문제와 똑같은 풀이방법대로 작성했다.

다만 이 문제에서 주의해야 할 점은 “벽을 최소 몇 개 부수어야 하는지 구하는”부분이다.

범위 내의 좌표임과 동시에 방문하지 않은 좌표 + 벽을 뚫지 않고 갈 수 있는 좌표의 우선 고려 로 조건을 설정해야한다.

      if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == -1:
        if arr[nx][ny] == 0: # 벽을 뚫지 않아도 되는 경우
          dq.appendleft((nx, ny))
          visited[nx][ny] = visited[x][y]
        else: # 벽을 뚫어야 하는 경우
          dq.append((nx, ny))
          visited[nx][ny] = visited[x][y] + 1

따라서 기존 BFS에서는 deque에 append() 를 해주는 것이 일반적이었지만,

이 문제의 경우 arr[nx][ny]의 값이 0인 경우를 우선적으로 고려해야한다.

그렇기에 arr[nx][ny]의 값이 0인 경우는 FIFO의 특징을 가진 Queue(파이썬에서 사용하는 Deque은 Queue를 두개 붙인 형태이기에 append, appendleft, pop, popleft가 모두 가능하다.)이지만,

우선적으로 처리하기 위해 appendleft() 로 (nx, ny)를 넣어줬다.

배운점 또는 느낀점

너비우선탐색에서 같은 너비의 좌표여도 우선적으로 처리해야 하는 조건을 다루는 방법을 배웠다!