[백준] 6087 레이저 통신 python

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

6087번: 레이저 통신

 

도착지까지 최소거리를 찾아야해서 다익스트라 알고리즘을 사용해서 풀수있지만 도착지까지 갈 때 방향 전환까지 카운트해야해서 조금 까다로운 문제이다.

 다익스트라 알고리즘에 진행방향과 방향을 전환한 횟수를 같이 추가해서 풀었다.

import sys; input = sys.stdin.readline
from heapq import heappop, heappush

def dijkstra(raser, _map):
    d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    ret = 10000
    # s = raser[0], e = raser[1]
    visit = [[[-1, 10000] for _ in range(len(_map[0]))] for _ in range(len(_map))]
    h = [(0, raser[0][0], raser[0][1], -1, 0)]
    while h:
        dist, cur_r, cur_c, cur_dir, change_num = heappop(h)
        if cur_r == raser[1][0] and cur_c == raser[1][1]:
            # 방향이 바뀌는 최소 횟수 저장
            ret = min(ret, change_num)
        if visit[cur_r][cur_c][1] >= change_num:
            visit[cur_r][cur_c][1] = change_num
        elif visit[cur_r][cur_c][0] > -1:
            continue
        visit[cur_r][cur_c][0] = dist

        for i in range(4):
            nr = cur_r + d[i][0]
            nc = cur_c + d[i][1]
            n_num = change_num
            if _map[nr][nc] == "*": continue
            if cur_dir != -1 and cur_dir != i:
                n_num += 1
            heappush(h, (dist + 1, nr, nc, i, n_num))

    return ret


def main():
    W, H = map(int, input().split())
    raser = []
    _map = ["*" * (W + 2)]
    for r in range(H):
        tmp = input().rstrip()
        _map.append("*" + tmp + "*")
        for c in range(W):
            if tmp[c] == "C":
                raser.append((r + 1, c + 1))
    _map.append("*" * (W + 2))

    print(dijkstra(raser, _map))


if __name__ == "__main__":
    main()

 

제출하고 나니 내가 사용한 방식은 상당히 비효율적인 방식이었다. h에 모든 값이 다 빠져나올때까지 진행하게 되는데 이게 생각보다 많이 걸리는 듯 하다.