이번 문제는 BFS를 통해 해결하였다. 두 군데를 방문해야 하기 때문에 기존의 BFS와는 조금 다르게 접근해야 했다. 좌표들로 들어오는 방향을 체크하도록 하기 위해 방문처리 리스트를 3차원 리스트로 선언했다. 이 문제에서의 포인트는 다음과 같았다

• 어떠한 목적지에도 도착하지 못했다면 이전 방문 좌표로 돌아갈 수 없다.
• 가장 먼저 방문한 목적지에 대한 가장 빠른 시간을 구한다.
  • 목적지 표시를 지워주고, 방문처리 리스트를 초기화하여 방문했던 좌표에 다시 방문할 수 있도록 한다.
• 남은 하나의 목적지를 찾으면 종료한다.

방법에 대하여 생각하는 데에 정말 오래 걸렸고, 결과적으로는 다른 사람의 코드를 참고하게 되었다.

Code

from collections import deque
n, m = map(int, input().split())
grid = [list(str(input())) for _ in range(n)]
sy, sx = 0, 0
for i in range(n):
    for j in range(m):
        if grid[i][j] == 'S':
            sy, sx = i, j
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
def bfs():
    q = deque()
    visited = [[[False for _ in range(4)] for _ in range(m)] for _ in range(n)]
    q.append((sy, sx, -1, 0))
    cnt = 0
    save_point = deque()
    while q:
        y, x, d, time = q.popleft()
        for i in range(4):
            if i == d:
                continue
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < m and grid[ny][nx] != '#' and not visited[ny][nx][i]:
                if grid[ny][nx] == 'C':
                    if not save_point:
                        cnt += 1
                        if cnt == 2:
                            return time+1
                    elif save_point[0][0] != ny or save_point[0][1] != nx:
                        continue
                    save_point.append((ny, nx, i, time+1))
                else:
                    if save_point:
                        continue
                    visited[ny][nx][i] = True
                    q.append((ny, nx, i, time+1))
        if not q and save_point:
            visited = [[[False for _ in range(4)] for _ in range(m)] for _ in range(n)]
            grid[save_point[0][0]][save_point[0][1]] = '.'
            while save_point:
                q.append(save_point.pop())
    return -1
print(bfs())