로봇이 지나간 경로

문제

# * L: 로봇이 왼쪽으로 90도 회전하며, 이에 따라 바라보는 방향이 바뀐다.
# * R: 로봇이 오른쪽으로 90도 회전하며, 이에 따라 바라보는 방향이 바뀐다.
# * A: 로봇이 바라보는 방향으로 두 칸 전진한다. 단, 이 과정에서 로봇이 격자판 바깥을 나간다면 로봇은 이 명령을 수행할 수 없다.

import sys
from collections import deque
input = sys.stdin.readline

# H : 세로 크기, W : 가로 크기
H, W = map(int, input().split())

# 지도
Map = []

# 로봇이 지나간 길이 표시된 지도
for i in range(H):
    Map.append([j for j in input()])

# 동북서남 이동 방향
X = [0, -1, 0, 1]
Y = [-1, 0, 1, 0]
# 동, 북, 서, 남
NEWS = ['<', '^', '>', 'v']

# start 지점과 방향 도출
def start(a, b):
    cnt = 0
    for i in range(4):
        if 0 <= a + X[i] < H and 0 <= b + Y[i] < W and Map[a + X[i]][b + Y[i]] == '#':
            news = NEWS[i]
            cnt += 1
    
    if cnt > 1:
        return False
    
    return news

# bfs
def robot(a, b):
    # 방향
    path = deque()
    # 지나는 좌표
    queue = deque()
    queue.append([a, b])
    # 방문 기록
    visited[a][b] = True

    while queue:
        [x, y] = queue.popleft()

        # 동서남북 이동
        for i in range(4):
            nx = x + X[i]
            ny = y + Y[i]
            if 0 <= nx < H and 0 <= ny < W:
                if Map[nx][ny] == '#' and visited[nx][ny] == False:
                    visited[nx][ny] = True
                    path.append(NEWS[i])
                    queue.append([nx, ny])
    return path
    
    

# 로봇 출발지
a = 0
b = 0
for x in range(H):
    for y in range(W):
        # 시작 지점 확인
        if Map[x][y] == '#' and start(x, y):
            # 방문 좌표
            visited = [[False for i in range(W)] for i in range(H)]
            # 처음 로봇이 바라보는 방향
            first_news = start(x, y)
            path = robot(x, y)
            # 로봇에 내려야 하는 명령어
            answer = ''
            # 현재 방향
            current_path = path.popleft()
            cnt = 1
            while path:
                # 다음 방향
                next_path = path.popleft()
                # 같은 방향일 때
                if next_path == current_path:
                    cnt += 1
                    current_path = next_path
                    # A 명령어
                    if cnt % 2 == 0:
                        answer += 'A'
                        cnt = 0
                else:
                    # L 명령어
                    if NEWS[NEWS.index(current_path)-1] == next_path:
                        answer += 'L'
                    # R 명령어
                    else:
                        answer += 'R'
                    current_path = next_path
                    cnt += 1
            print(x+1, y+1)
            print(first_news)
            print(answer)

            # 종료
            sys.exit()