[Softeer] 로봇이 지나간 경로

 

문제

요약

로봇이 이동한 경로를 가기 위한 첫 시작 지점과 방향, 이동하기 위한 명령어를 찾으시오.

 

원본

https://softeer.ai/practice/6275

Softeer - 현대자동차그룹 SW인재확보플랫폼

풀이

시뮬레이션형 문제로 시간은 걸리지만 금방 풀 수 있는 문제 같다.

 

처음 헤맸던 부분, 방향을 바꾸면 무조건 두칸을 이동하는 것을 안해줬다.

좌표 상에서 방향을 탐색할 때, 원래 진행방향과 방향이 다르면 왼쪽 혹은 오른쪽으로 이동한 뒤

한칸을 이동한 위치가 된다. 따라서 방향 전환하고 두칸 전진!

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

h, w = map(int, input().split())
arr = [list(input().strip()) for _ in range(h)]
visited = [[0]*w for _ in range(h)]
d = [(-1, 0), (0,-1), (1,0), (0,1)]

def findStart():
    for i in range(h):
        for j in range(w):
            cnt = 0
            if arr[i][j] == "#":
                for di, dj in d:
                    ni, nj = i+di, j+dj
                    if 0 <= ni < h and 0 <= nj < w and arr[ni][nj] =="#":
                        cnt += 1
        
                if cnt == 1:
                    return i, j

def move():
    q = deque([(si, sj)])
    visited[si][sj] = 1
    answer = ""
    nd = -1
    directions = ['^', '<', 'v', '>']
    
    while q:
        x, y = q.popleft()
        visited[x][y] = 1
        for i in range(4):
            nx, ny = x+d[i][0], y+d[i][1]
            if 0 <= nx < h and 0 <= ny < w and arr[nx][ny] == "#" and visited[nx][ny] == 0:
                q.append((nx, ny))
                visited[nx][ny] = 1
                
                if x == si and y == sj:
                    print(directions[i])
                    answer += 'A'
                    tx, ty = q.pop()
                    q.append((tx+d[i][0], ty+d[i][1]))
                else:    
                    if nd != i:
                        if nd == 0:
                            answer += 'L' if i == 1 else 'R'
                        elif nd == 1:
                            answer += 'L' if i == 2 else 'R'
                        elif nd == 2:
                            answer += 'L' if i == 3 else 'R'
                        elif nd == 3:
                            answer += 'L' if i == 0 else 'R'
                    answer += 'A'
                    tx, ty = q.pop()
                    q.append((tx+d[i][0], ty+d[i][1]))
                nd = i
                break
    return answer

si, sj = findStart()
print(si+1, sj+1)
answer = move()
print(answer)