풀이

1. direction을 표현해야 한다. 동서남북으로 이동할때, 각각을 0,1,2,3으로 표현할 수 있다.
   
2. 매 시간마다 방향을 바꿔야 한다. 동서남북으로 이동할 수 있는 민식이는 직전의 이동방향과 다르게 이동해야하기 때문에, 직전의 이동방향을 저장해야한다.
   BFS 이동에 사용되는 Queue에 직전에 이동한 방향도 추가한다.
3. 두 개의 도착지 하나의 목적지로 도달하지 않고, 두 곳을 방문해야 종료되기 때문에, 이를 count할 변수가 필요하다.
   S → 첫번째 C인 가능한 가장 짧은 경로를 탐색한다. 그 이후에, 첫번째 C → 두번째 C 인 최단 경로를 탐색한다.
   
   여기서 가장 중요한 점은, S → 첫번째 C 최단 경로가 두개가 나올 수 있다는 것이다. 둘 중에서 어떤 방법을 채택하는 것이 가장 짧은지는 첫번째 C → 두번째 C를 탐색해야 알 수 있다.
   따라서, 첫번째 C에 도달하는 최단 시간을 저장해둘 필요가 있다.
4. 3.에서 이어서 생각해보면, 한 위치에 도달할때 어떤 경로로 왔는지 다르다면 완전히 다르다는 것을 알 수 있다. 따라서, visited는 각 방향별로 선언해야 한다.
   위의 예시를 이동하면 아래와 같이 visited를 만들 수 있다.
   만약에 같은 방향으로 이미 진행한 상황이여서 T로 처리 되어있다면 그 순간에 늦게 도착한 case는 최단시간일 수 없기 때문에 바로 제외하면 된다.
5. 정리하자면 아래와 같다.

   a. 직전 방향과 같으면 안되니 queue에 방향도 추가
   b. 도착지가 두 곳 이기 때문에 S → 첫번째 C 와 첫번째 C → 두번째 C`를 나눠서 탐색 하기
   c. 첫번째 C로 도달하는 경로는 최단 경로들만 저장해두기
   d. 방향을 고려한 3차원의 visited 배열생성하기

코드

from collections import deque

n,m=map(int,input().split())
map=[list(input()) for _ in range(n)]

dx=[0,-1,0,1]
dy=[-1,0,1,0]
def bfs(start_x,start_y,direction,time):
    found_save_point=[]
    queue=deque()
    queue.append([start_x,start_y,direction,time])
    visited= [[[1 for _ in range(m)] for _ in range(n)]for _ in range(4)]
    c_count=0
    while queue:
        cur_x,cur_y,cur_dir,time=queue.popleft()
        # next move
        for next_dir in range(4):
            # same direction
            if cur_dir==next_dir:
                continue

            # next moves in map range
            next_x,next_y=cur_x+dx[next_dir],cur_y+dy[next_dir]
            if next_x<0 or next_x>=n or next_y<0 or next_y>=m:
                continue
            # not wall and prevent revisiting same map_position from same direction
            if map[next_x][next_y]!='#' and visited[next_dir][next_x][next_y]:
                # C found
                if map[next_x][next_y]=='C':
                    if not found_save_point :  # first C
                        c_count+=1
                        if c_count==2:
                            return time+1
                    elif found_save_point[0][0]!=next_x or found_save_point[0][1]!=next_y:
                        continue
                    found_save_point.append([next_x,next_y,next_dir,time+1])
                else:
                    if found_save_point:
                        continue
                    visited[next_dir][next_x][next_y]-=1
                    queue.append([next_x,next_y,next_dir,time+1])
        if not queue and found_save_point:
            visited= [[[1 for _ in range(m)] for _ in range(n)]for _ in range(4)]
            map[found_save_point[0][0]][found_save_point[0][1]]='.'
            while found_save_point:
                queue.append(found_save_point.pop())

    return -1
# start bfs :  S(i,j), prev direction, c_count, minute
for i in range(n):
    for j in range(m):
        if map[i][j]=='S':
            print(bfs(i,j,-1,0))