[골드4] 2665번 : 미로만들기

🛠 문제

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

👩🏻‍💻 해결 방법

bfs를 통해 그래프를 탐색해주고, 동시에 우선순위큐(최소힙)를 통해 바꿔야 할 최소의 검은 방의 수를 구해줄 수 있다


소스 코드

import heapq
import sys
input = sys.stdin.readline

n = int(input())
graph = [list(map(int, input().rstrip())) for _ in range(n)]
visit = [[0] * n for _ in range(n)]

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

def dijkstra():
  q = []
  heapq.heappush(q, [0, 0, 0])
  visit[0][0] = 1

  while q:
    dist, x, y = heapq.heappop(q)
    # 끝방일 경우
    if x == n-1 and y == n-1:
      return dist

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

      if 0<=nx<n and 0<=ny<n and visit[nx][ny] == 0:
        visit[nx][ny] = 1
        # 검은방일 경우
        if graph[nx][ny] == 0:
          heapq.heappush(q, [dist+1, nx, ny])
        # 흰방일 경우
        else:
          heapq.heappush(q, [dist, nx, ny])

print(dijkstra())

💡 다른 사람의 풀이

from collections import deque

n = int(input())
a = [list(map(int, input())) for i in range(n)]
ch = [[-1] * n for i in range(n)]

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

def bfs():
  de = deque()
  de.append([0, 0])
  ch[0][0] = 0

  while de:
    x, y = de.popleft()

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

      if 0 <= nx < n and 0 <= ny < n:
        if ch[nx][ny] == -1:
          if a[nx][ny] == 0:
            ch[nx][ny] = ch[x][y] + 1
            de.append([nx, ny])
          else:
            ch[nx][ny] = ch[x][y]
            # 흰방을 먼저 방문하기 위해 appendleft 사용
            de.appendleft([nx, ny])

bfs()
print(ch[n-1][n-1])