[백준2665] / 미로만들기 - 다익스트라/그래프탐색

 

백준2665

 

 

푼 날짜 : 2024.11.20

푼 문제 : [2665] / 미로만들기

사용한 언어 : python

알고리즘 : 다익스트라(dijkstra)

 

 

접근방식 :

4방향 탐색을 하며 최소로 방을 변경하는 횟수를 누적해 주었다.

이 문제에서는 1이 흰방, 0이 검은 방인데 검은방-> 흰방을 계산해야 해서 0과 1을 바꿔주는 작업이 필요했다.

 

now_color = 0 if int(graph[ny][nx]) else 1
all_cost = now_cost + now_color

 

따라서 위 처럼 현재 컬러에 따라 0인지 1인지 바꾸어서 누적값을 계산했다.

 

 

코드 :

import sys
import heapq

input = sys.stdin.readline
INF = float("INF")

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

def dijkstra(N, graph):
    heap = [(0, 0, 0)]
    dist = [[INF for _ in range(N)] for _ in range(N)]
    dist[0][0] = 0

    while heap:
        now_cost, now_i, now_j = heapq.heappop(heap)
        if dist[now_i][now_j] < now_cost: continue
        
		# 4방향 탐색
        for i in range(4):
            ny, nx = now_i+dy[i], now_j+dx[i]

            if 0<=ny<N and 0<=nx<N:
            	# 검은방0 이면 1로 계산, 흰방1 이면 0으로 계산하기 위함
                now_color = 0 if int(graph[ny][nx]) else 1
                all_cost = now_cost + now_color
                
                if dist[ny][nx] > all_cost:
                    dist[ny][nx] = all_cost
                    heapq.heappush(heap, (all_cost, ny, nx))
                    
    # 최종적으로 검은방에서 흰방으로 바꾼 개수 출력
    return dist[N-1][N-1]

N = int(input())
graph = []
for _ in range(N):
    lst = list(input().rstrip())
    graph.append(lst)

ans = dijkstra(N, graph)
print(ans)

 

 

골드 문제를 척척 풀어내는 나 기특해 !!!!! 

잘하고 있어!!!!