[백준 - Python] 2665 - 미로만들기

0.  문제 링크

 

 

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

2665번: 미로만들기

---

1.  풀이 방법

 

 

다익스트라

1. 구글에 일요일 아침의 데이트 파이썬을 검색하면 나오는 풀이와 흡사하게 풀었음.
2. 일단 검은 방은 전처리로 10,000으로 설정하였음. 최대 50 * 50이 맵 사이즈가 되기 때문에 2500 이상으로 설정하면 됨.
3. 이후 힙을 이용한 다익스트라로 목적지까지 최소 거리를 구하면 됨
4. 최종적으로 목적지에는 검은 방 * 10,000 + 흰 방 * 1의 값이 저장되는데, 여기서 10,000으로 나눈 몫을 반환하면 됨

 

A*

1. 위의 다익스트라에서 현재 위치의 값까지 가중치로 추가하였음
2. 따라서 힙에는 검은 방을 흰 방으로 바꾼 횟수가 같은 애들 중에 가장 목적지와 거리가 가까운 애를 우선적으로 선택하게 됨

---

2.  코드

 

 

import sys
import heapq
input = sys.stdin.readline


def dijkstra(maps):
    # 다익스트라 알고리즘을 사용
    dir = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    value = [[sys.maxsize] * n for _ in range(n)]
    heap = []
    heapq.heappush(heap, (0, 0, 0))

    while True:
        score, y, x = heapq.heappop(heap)
        if (y, x) == (n - 1, n - 1): break
        for dy, dx in dir:
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < n:
                if value[ny][nx] > score + maps[ny][nx]:
                    value[ny][nx] = score + maps[ny][nx]
                    heapq.heappush(heap, (value[ny][nx], ny, nx))

    return value[n - 1][n - 1] // 10000     # 정답의 출력을 위해 10,000으로 나눈 몫을 반환하면 됨


def A_star(maps):
    # 에이스타 알고리즘?을 사용
    dir = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    value = [[sys.maxsize] * n for _ in range(n)]
    heap = []
    heapq.heappush(heap, (n * 2, 0, 0))

    while True:
        score, y, x = heapq.heappop(heap)
        score = score + (2 * n - y - x)
        if (y, x) == (n - 1, n - 1): break
        for dy, dx in dir:
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < n:
                if value[ny][nx] > score + maps[ny][nx]:
                    value[ny][nx] = score + maps[ny][nx]
                    heapq.heappush(heap, (value[ny][nx] - (2 * n - ny - nx), ny, nx))

    return value[n - 1][n - 1] // 10000  # 정답의 출력을 위해 10,000으로 나눈 몫을 반환하면 됨


if __name__ == "__main__":
    n = int(input())
    maps = [list(map(lambda x: 10000 if x == '0' else 0, input().strip())) for _ in range(n)]
    # 일요일 아침의 데이트와 비슷하게 벽이 있는 곳은 10000으로 설정하여 문제를 풀었음

    # print(dijkstra(maps))
    print(A_star(maps))

---

3.  마무리