2665번: 미로만들기
첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.
www.acmicpc.net
📝 풀이
- n x n 바둑판 모양으로 총 n^2개의 방이 있을 때, 윗줄 맨 왼쪽 시작방에서부터 아랫줄 맨 오른쪽 끝방으로 이동하는데 필요한 방의 색을 바꾸는 횟수를 최소로 하는 경우를 구하는 프로그램
- 흰방은 1, 검은방은 0으로 나타내며 검은방은 지나갈 수 없는 방이다.
- 다익스트라 알고리즘으로 구현할 수 있으며 최소 힙을 방의 색을 바꾼 횟수를 기준으로 정렬한다.
💻 소스코드
import sys
import heapq
input = sys.stdin.readline
dy = (1, -1, 0, 0)
dx = (0, 0, 1, -1)
def dijkstra():
heap = []
heapq.heappush(heap, (0, 0, 0))
visited[0][0] = True
while heap:
cnt, y, x = heapq.heappop(heap)
if y == n - 1 and x == n - 1:
return cnt
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if not 0 <= ny < n or not 0 <= nx < n or visited[ny][nx]:
continue
visited[ny][nx] = True
if room[ny][nx] == 1:
heapq.heappush(heap, (cnt, ny, nx))
else:
heapq.heappush(heap, (cnt + 1, ny, nx))
n = int(input())
room = [list(map(int, input().strip())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
print(dijkstra())
'🥇 Problem Solving > Dijkstra' 카테고리의 다른 글
[Python] BOJ / 11779번 / 최소비용 구하기 2 (0) | 2022.05.29 |
---|---|
[Python] BOJ / 4485번 / 녹색 옷 입은 애가 젤다지? (0) | 2022.05.14 |
[Python] BOJ / 13549번 / 숨바꼭질 3 (0) | 2022.05.13 |
[Python] BOJ / 1956번 / 운동 (0) | 2022.04.29 |
[Python] BOJ / 1261번 / 알고스팟 (0) | 2022.04.28 |