2665. 미로 만들기

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

✔ 유형 : 다익스트라

✔ 문제 풀이: 문제에서 구하고자 하는 것은 최단 거리가 아니라 검은 방을 최대한 적게 지나야 하는 것이다.

시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데,/ 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.

문제에 흰 방에 대한 최소 기준이 없다. 이 문제의 목표는 

1. 처음에서 끝으로 도달

2. 검은 방을 적게 거침

 

다익스트라 : 하나의 시작점으로부터 다른 모든 정점까지의 최단거리를 구하는 알고리즘.

 

다익스트라 알고리즘을 이용하여 최단거리 = 검은방으로 바꾼 횟수로 문제를 해결하면 된다.

 

코드

import sys
import heapq

input=sys.stdin.readline # input함수 바꾸기
sys.setrecursionlimit(15000) # 10^8 까지 늘림.

#input
#한 줄에 들어가는 방의 수
N = int(input())

#미로 맵
Maze = [list(map(int, list(input().rstrip()))) for _ in range(N)] # 붙여서 입력받기 rstrip!!!

# 방향 배열
dx = [1,-1,0,0]
dy = [0,0,1,-1]

INF = int(1e9)
def dijkstra():
    # 최소 힙 초기화
    heap = [(0, 0, 0)]  # (count, x, y)
    visited = [[INF] * N for _ in range(N)]
    visited[0][0] = 0
    
    while heap:
        dist,x,y = heapq.heappop(heap)
        
        if dist > visited[x][y]:
            continue
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
        
            if nx <0 or ny < 0 or nx >=N or ny >=N: continue # 인덱스 범위 체크
            cost = dist
            
            if Maze[nx][ny] == 0 : # 검은방이면 비용 증가
                cost += 1
                
            
            if cost < visited[nx][ny]: #이미 확정된 비용보다 작다면?
                visited[nx][ny] = cost
                heapq.heappush(heap, (cost, nx, ny))
                
    return visited[N-1][N-1]
            
    
   
   
   



print(dijkstra())
        
        
#Note
#의식의 흐름
#1. 뚫을지 안뚫을지를 결정해서 두가지의 재귀함수로 나눠서 풀기 -> 시간초과
#2. 알고보니 1의 방법은 DFS였음
#3. 우리가하려는건 시작-끝까지 최소비용의 검은방. 최소!!!!비용!!!! = BFS
#4. 시작과 끝이 있고 최단거리? = 다익스트라?
#5. 검은방뚫는건 어케해? 어차피 흰방을 어케거쳐가더라도 검은방만 적게!!!지나서 목적지에가면됨
#6. 따라서 비용이 적은 간선을 택한다는 의미가 검은방을 적게 거쳐간다는 의미와 같다.
#7. 검은방을 만나면 비용을 증가시키고, 머 다릏게 돌아가다가 검은방 비용적은 루틴이있ㅇ므 걔가 덮어씌어버리는것!!