이번 문제는 BFS 알고리즘을 통해 해결하였다. 처음에는 최단거리를 찾으면 바로 방향을 바꾸는 최소 갯수를 구할 수 있을 것이라 생각하였고, BFS 알고리즘을 통해 최단거리를 찾았다. 그러나 최단거리에도 여러 방법이 존재하고, 그때마다 방향을 바꾸는 경우가 여러가지라는 것을 깨닫았고, 다익스트라 알고리즘에 첫번째 인자를 방향을 바꾼 횟수로 두어 최소힙을 통한 방식을 이용해보려고 하였다. 그러나 생각처럼 잘 구현되지는 않았다.

다시 BFS 알고리즘으로 돌아와, 이번에는 각 방향별로 갈 수 있는 최대 거리까지 이동하며 매번 deque에 해당 좌표를 넣도록 하였다. 그리고 방문 처리 리스트에는 방향을 바꾼 수를 넣도록 하였다. 이러한 방식으로 방향을 최소로 바꾼 경우의 값을 구할 수 있었다.

Code

import collections
w, h=map(int, input().split())
board=[str(input()) for _ in range(h)]
c=[]
for i in range(h):
    for j in range(w):
        if board[i][j]=='C':
            c.append((i, j))
dy, dx=[-1, 1, 0, 0], [0, 0, -1, 1]
def bfs(y, x):
    q=collections.deque()
    q.append((y, x))
    visited=[[1e9 for _ in range(w)] for _ in range(h)]
    visited[y][x]=0
    while q:
        y, x=q.popleft()
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            while True:
                if not (0<=ny<h and 0<=nx<w):
                    break
                if board[ny][nx]=='*':
                    break
                if visited[ny][nx]<visited[y][x]+1:
                    break
                q.append((ny, nx))
                visited[ny][nx]=visited[y][x]+1
                ny, nx=ny+dy[i], nx+dx[i]
    return visited
answer=bfs(c[0][0], c[0][1])
print(answer[c[1][0]][c[1][1]]-1)