• 최단 경로 문제로 모델링하는 간단한 방법은, 현재 좌표와 방향을 묶어서 하나의 노드로 처리하고, 인접한 좌표로 이동하는 비용을, 현재 방향으로 인접한 노드는 0, 현재 방향과 다른 방향의 인접 노드는 1로 잡아주는 것이다. 이렇게 하면 코스트가 0 또는 1이므로 0-1 BFS로 최단 경로를 찾을수 있다.
• 다른 풀이들을 보면 BFS로 움직이되, 현재 방향으로 앞에 있는 노드들을 모두 한번에 큐에 넣어주는 식으로 풀이를 한 것들이 보인다. 그렇게 한것도 결국은 0-1 BFS로 모델링한것과 동일하게 작동하게 된다. 물론 그렇게 짤경우 코드가 좀더 최적화되어서 좀더 빠르게 동작할수는 있다.
• 내 코드에서는 구현의 편의성을 위해서, 왼쪽이나 오른쪽으로 90도 회전하는 것 뿐 아니라, 180도 회전하는 것도 허용했다. 그렇게 하더라도 180도를 돌아서 가는것은 절대로 최단 경로가 될수 없기 때문에, 답을 찾는 데에는 문제가 없다.
• 노드의 갯수는 {칸의 갯수} * {방향의 갯수} 이므로 결국 O(WH)이고, 엣지의 갯수도 O(WH). 최단 경로 탐색에 걸리는 총 시간복잡도도 O(WH)이다

"""Solution code for "BOJ 6087. 레이저 통신".

- Problem link: https://www.acmicpc.net/problem/6087
- Solution link: http://www.teferi.net/ps/problems/boj/6087

Tags: [0-1 BFS]
"""

import functools
from teflib import graph as tgraph
from teflib import search

COW = 'C'
WALL = '*'
INF = float('inf')


def next_states(state, graph, walls):
    u, cur_dir = state
    for v in graph[u]:
        if v not in walls:
            next_dir = v - u
            w = 0 if cur_dir == next_dir else 1
            yield ((v, next_dir), w)


def main():
    W, H = [int(x) for x in input().split()]
    grid = ''.join(input() for _ in range(H))

    source = grid.index(COW)
    dest = grid.index(COW, source + 1)
    sources = [(source, d) for d in (-W, 1, W, -1)]
    walls = {u for u, x in enumerate(grid) if x == WALL}
    dists = search.zero_one_distances(
        functools.partial(next_states,
                          graph=tgraph.GridGraph(H, W),
                          walls=walls), sources)
    answer = min(dists.get((dest, d), INF) for d in (-W, 1, W, -1))
    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.search.zero_one_distances