NO_COST_MODE = False
MAP_FILE = "map4.txt"
COST_FILE = "cost4.txt"

이동방향 = {(-1, 0): "↓", (0, 1): "←", (1, 0): "↑", (0, -1): "→"}
역추적방향 = {화살표: (-행변화, -열변화) for (행변화, 열변화), 화살표 in 이동방향.items()}


def 벽과공간획득(파일이름):
    """텍스트의 각 글자를 한 칸으로 만든다."""
    with open(파일이름, encoding="utf-8") as 파일:
        return [list(줄.strip()) for 줄 in 파일]


def 비용획득(파일이름, 비용무시=False):
    """자연수(1이상 9이하) 비용 격자를 읽는다. 비용무시=True이면 모든 비용을 1로 만든다."""
    with open(파일이름, encoding="utf-8") as 파일:
        if 비용무시:
            return [[1] * len(줄.strip()) for 줄 in 파일]
        return [[int(글자) for 글자 in 줄.strip()] for 줄 in 파일]


def 정보통합(벽과공간, 비용정보):
    """새 지도를 만들고 출발점과 도착점의 좌표를 반환한다."""
    지도 = []
    출발점 = 도착점 = (-1, -1)

    for 행번호, 한줄벽과공간 in enumerate(벽과공간):
        지도행 = []
        for 열번호, 각칸의정보 in enumerate(한줄벽과공간):
            지도행.append({
                "벽": 각칸의정보,
                "노드진입비용": int(비용정보[행번호][열번호]),
                "g": float("inf"),
                "직전": "",
            })
            if 각칸의정보 == "s":
                출발점 = (행번호, 열번호)
            elif 각칸의정보 == "d":
                도착점 = (행번호, 열번호)
        지도.append(지도행)

    if 출발점 == (-1, -1) or 도착점 == (-1, -1):
        raise ValueError("지도에는 출발점 s와 도착점 d가 필요합니다.")
    return 지도, 출발점, 도착점


def 탐색(지도, 출발점, 도착점):
    """지도에서 각 칸의 g값 및 직전 위치를 갱신한다."""
    행개수, 열개수 = len(지도), len(지도[0])
    목표행, 목표열 = 도착점
    후보 = []
    탐색순서 = []

    def g(위치):
        행, 열 = 위치
        return 지도[행][열]["g"]

    def h(위치):
        행, 열 = 위치
        return ((행 - 목표행) ** 2 + (열 - 목표열) ** 2) ** 0.5

    def f(위치):
        return g(위치) + h(위치)

    def 넣기또는갱신(위치):
        노드정보 = (위치, f(위치))
        일치노드찾음 = False
        for 순번, (후보위치, _) in enumerate(후보):
            if 후보위치 == 위치:
                후보[순번] = 노드정보
                일치노드찾음 = True
                break
        if not 일치노드찾음:
            후보.append(노드정보)

        후보.sort(key=lambda 항목: 항목[1])

    시작행, 시작열 = 출발점
    지도[시작행][시작열]["g"] = 지도[시작행][시작열]["노드진입비용"]
    지도[시작행][시작열]["직전"] = "0"
    넣기또는갱신(출발점)

    while 후보:
        현재위치, _ = 후보.pop(0)
        행, 열 = 현재위치
        현재칸 = 지도[행][열]
        탐색순서.append(현재위치)

        if 현재위치 == 도착점:
            break

        for (행변화, 열변화), 화살표 in 이동방향.items():
            다음행, 다음열 = 행 + 행변화, 열 + 열변화
            if not (0 <= 다음행 < 행개수 and 0 <= 다음열 < 열개수):
                continue

            이웃칸 = 지도[다음행][다음열]
            if 이웃칸["벽"] == "1":
                continue

            새비용 = 현재칸["g"] + 이웃칸["노드진입비용"]
            if 새비용 >= 이웃칸["g"]:
                continue

            지도[다음행][다음열]["g"] = 새비용
            지도[다음행][다음열]["직전"] = 화살표
            넣기또는갱신((다음행, 다음열))

    return 지도, 탐색순서


def 경로복원(지도, 출발점, 도착점):
    """직전 화살표를 따라 최종 경로를 복원한다. 경로가 없으면 빈 리스트를 반환한다."""
    행, 열 = 도착점
    if not 지도[행][열]["직전"]:
        return []

    경로 = [도착점]
    while (행, 열) != 출발점:
        행변화, 열변화 = 역추적방향[지도[행][열]["직전"]]
        행, 열 = 행 + 행변화, 열 + 열변화
        경로.append((행, 열))
    return 경로[::-1]


def 결과표시(완성지도, 탐색순서, 출발점, 도착점):
    """지도 / 중복 처리를 포함한 탐색 순서 / 최종 경로를 출력한다."""
    print("A*")
    for 행번호, 지도행 in enumerate(완성지도):
        표시행 = []

        for 열번호, 칸 in enumerate(지도행):
            if (행번호, 열번호) == 출발점:
                표시행.append("s")
            elif 칸["직전"] != "":
                표시행.append(칸["직전"])
            else:
                표시행.append(칸["벽"])
        print(" ".join(표시행))
    print()

    print(f"탐색 순서({len(탐색순서)}회):", 탐색순서)
    경로 = 경로복원(완성지도, 출발점, 도착점)
    if not 경로:
        print("탐색 실패(경로 없음)")
        return

    목표행, 목표열 = 도착점
    총비용 = 완성지도[목표행][목표열]["g"]
    print(f"최종 경로({len(경로)}칸 총 비용 {총비용}): {경로}")


def main():
    벽과공간 = 벽과공간획득(MAP_FILE)
    비용정보 = 비용획득(COST_FILE, 비용무시=NO_COST_MODE)
    지도, 출발점, 도착점 = 정보통합(벽과공간, 비용정보)
    완성지도, 탐색순서 = 탐색(지도, 출발점, 도착점)
    결과표시(완성지도, 탐색순서, 출발점, 도착점)


if __name__ == "__main__":
    main()
