2665. 미로 만들기
by 브이담곰
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. 검은방을 만나면 비용을 증가시키고, 머 다릏게 돌아가다가 검은방 비용적은 루틴이있ㅇ므 걔가 덮어씌어버리는것!!
'Coding Test > Baekjoon' 카테고리의 다른 글
1700. 멀티탭 스케줄링 (0) | 2024.07.25 |
---|---|
3055. 탈출 (0) | 2024.07.18 |
2294. 동전 (0) | 2024.07.18 |
2637. 장난감 조립 (0) | 2024.07.18 |
1707. 이분 그래프 (1) | 2024.07.18 |
블로그의 정보
농담곰담곰이의곰담농
브이담곰