[softeer] [인증평가(1차) 기출] 로봇이 지나간 경로 (python)

https://softeer.ai/practice/info.do?idx=1&eid=577 

Softeer

---

문제 회고

시작할 수 있는 point의 특징은 본인은 #이고 주변에 하나의 #만을 가지는 point를 먼저 찾았다. 총 두 개의 point가 찾아지는데 하나는 start 나머지는 end point로 설정하고 경로를 탐색한다.

가장 오래 고민했던 부분은 바라보는 방향을 돌릴 때 왼쪽, 오른쪽 어느 방향으로 돌려야 최적의 방법인지 결정하는 부분이었다. 처음에는 그냥 조건문으로 처리하려고 했는데 코드가 너무 길어질 것 같아서 softeer algo tutor를 참고해서 index를 이용해서 풀었다. -1을 해서 같은 방향이면 왼쪽으로, +1을 해서 같은 방향이면 오른쪽으로 회전하게 된다. 

---

import sys
from collections import deque

h, w = map(int, sys.stdin.readline().split())
hist = [[''] * w for _ in range(h)]
check = [[False] * w for _ in range(h)]
head = {(-1, 0): 0, (0, 1): 1, (1, 0): 2, (0, -1): 3}
pos = ['^', '>', 'v', '<']
answer = ''

for i in range(h):
    tmp = sys.stdin.readline()
    for j in range(w):
        hist[i][j] = tmp[j]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
candidate = []
for i in range(h):
    for j in range(w):
        if hist[i][j] == '.':
            continue
        count = 0
        for k in range(4):
            nx, ny = i + dx[k], j + dy[k]
            if 0 <= nx <= h - 1 and 0 <= ny <= w - 1:
                if hist[nx][ny] == '#':
                    count += 1
        if count == 1:
            candidate.append((i, j))

start_point, end_point = candidate[0], candidate[1]
now_point = start_point
now_head = ' '
def check_head(answer, point, prev_head):
    i, j = point
    for k in range(4):
        nx, ny = i + dx[k], j + dy[k]
        if 0 <= nx <= h - 1 and 0 <= ny <= w - 1:
            if hist[nx][ny] == '#' and not check[nx][ny]:
                next_point = (nx, ny)
                now_head = head[(nx - i, ny - j)]
                check[i + dx[k]][j + dy[k]] = True
                check[i + 2 * dx[k]][j + 2 * dy[k]] = True
                if prev_head == ' ' or prev_head == now_head:
                    answer += 'A'
                else:
                    if pos[prev_head - 1] == pos[now_head]:
                        answer += 'LA'
                    else:
                        answer += 'RA'
                return answer, (i + 2 * dx[k], j + 2 * dy[k]), now_head

print(f'{start_point[0] + 1} {start_point[1] + 1}')
answer, now_point, now_head = check_head(answer, now_point, now_head)
print(pos[now_head])

while now_point != end_point:
    answer, now_point, now_head = check_head(answer, now_point, now_head)
print(answer)