[Softeer] HSAT 1회 기출 - 로봇이 지나간 경로

HSAT은 softeer에서 진행되는 현대자동차의 정기 코딩 인증 평가이다.

 

문제

<배경>

현대자동차그룹에 입사하여 로봇 연구 개발 부서에 막 입사한 당신은 아래와 같은 기능을 하는 간단한 로봇의 사용법을 전달받았다.

로봇은 $H$행 $W$열의 2차원 격자판 위를 돌아다닌다. 격자판의 각 칸은 정사각형 모양이며, 로봇은 격자판의 칸 하나를 차지한다.

로봇은 오른쪽(동), 왼쪽(서), 아래(남), 위(북) 중 한 방향을 바라볼 수 있다.

로봇의 이동을 제어하는 명령어는 다음과 같이 세 가지이다.

 

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

당신의 사수는 로봇 사용법을 시연해 주고자, 격자판 어딘가에 로봇을 두고 명령어를 입력해 가며 로봇을 움직였다. 이 때, 사수는 로봇이 같은 칸을 두 번 이상 방문하지 않도록 명령을 내렸고, 로봇이 방문한 모든 칸 (출발 칸 포함)을 지도에 표시하였다. 당신은 다음 날 출근해서 사수가 한 것처럼 로봇에 명령을 내려봐야겠다고 생각하며 퇴근하였다.

 

다음 날 출근한 당신은 사수가 넘겨준 지도를 보고 로봇이 어떤 칸들에 방문하였는지를 정확히 알 수 있었지만, 사수가 로봇에 어떤 명령을 내렸는지는 알 수 없었다.

당신은 오늘 로봇이 지도에 사수가 표시한 모든 칸들만을 방문하도록 로봇을 조작하고자 하며, 이를 위해 아래 정보를 계산해 주는 프로그램을 작성하려고 한다.

1. 처음 로봇을 어떤 칸에, 어떤 방향(동서남북 중 하나)으로 두어야 하는가?
2. 이후 로봇에 어떤 명령어를 어떤 순서대로 입력해야 하는가?

명령어를 입력하는 일은 번거롭기 때문에, 당신은 입력할 명령어의 개수를 최소화해야 한다.

처음 로봇을 어디에, 어느 방향으로 놓는지에 따라서도 필요한 명령어 개수가 달라질 수 있음에 유의하라.

 

<입력>

 

<출력>

 

<예시>

---

풀이

로봇이 갈 수 있는 길이 한가지면 그대로 가면 되지만,

만약 두갈래로 나뉘는 길을 갔다고 하면 어떤길을 먼저 가야할지 고민일 수 있다.

하지만 전진 시 2칸을 간다는 조건 때문에 이런 일은 벌어지지 않아 문제가 간단해진다.

 

먼저 입력과 기본적인 변수들을 설정했다.

h,w = map(int, input().split())
matrix = [list(input() for _ in range(h))]

directionmark=['^', '<', 'v', '>']

dx = [-1,0,1,0]
dy = [0,-1,0,1]

 

그리고 문제를 푸는데 필요한 세 개의 함수를 만들어주었다.

finddirection함수는 4방향을 탐색하고 길이 있는 곳의 개수를 확인한다.

로봇은 자기가 이동하면서 길을 없애기 때문에 일반적인 길에서는 이 개수가 1이 되고 이때는 방향을 리턴해준다.

만약 그 이외의 경우에는 -1을 리턴한다.

def finddirection(x,y):
    count = 0
    for i in range(4):
        nx,ny = x+dx[i],y+dy[i]
        if 0<= nx < h and 0<= ny < w and matrix[nx][ny] == "#":
            direction = i
            count += 1
    return (direction if count == 1 else -1)

 

findstart함수는 지도를 입력으로 받아 길로 표시된 모든 좌표에 대해 finddirection함수를 호출하고,

그 값이 -1이 아니라면(즉 갈 수 있는 방향이 하나만 있다면) 길의 끝이므로 이 곳의 좌표와 시작방향을 리턴한다.

즉 시작하기 위한 길의 끝을 찾는 함수이다.

def findstart(matrix):
    for x in range(h):
        for y in range(w):
            if matrix[i][j]=='#':
                direction = finddirection(x,y)
                if direction != -1:
                    return x,y,direction

navigate함수는 길을 따라 로봇을 움직이는 함수이다.

이전방향과 앞으로 가야할 방향이 같다면 직진을 하는 것이고, 다르다면 어느방향으로 회전해야하는지 판단한다.

직진할 때는 2칸을 가야하므로 코드를 두번씩 실행했고, 방향탐지는 나머지 연산을 사용했다.

directionmark를 보면 [0]부터[3]까지 왼쪽으로 회전한 순서대로 값이 있는 것을 볼 수 있다.

따라서 새로운 방향에서 이전 방향을 뺏을 때 1이라면 좌회전인 것이다.

0에서 3을 뺀 -3도 mod4를 하면 1이 되므로 이 경우도 포함된다.

def navigate(x,y,direction):
    prevdir = newdir = direction
    matrix[x][y] = '.'
    while(True):
        if prevdir == newdir:
            print('A', end='')
            x,y = x+dx[newdir],y+dy[newdir]
            matrix[x][y] = '.'
            x,y = x+dx[newdir],y+dy[newdir]
            matrix[x][y] = '.'

            prevdir = newdir
            newdir = finddirection(x,y)
        
        if newdir == -1: #끝
            return
        
        elif (newdir-prevdir)%4 == 1:
            print('L', end = '')
        
        elif (newdir-prevdir)%4 == 3:
            print('R', end = '')

        prevdir = newdir
        
        

x,y,direction = findstart(matrix)
#print(x+1, y+1)
print(directionmark[direction])
navigate(x,y,direction)

 

대단한 알고리즘이 필요하다기 보다 구현쪽에 가까운 문제였다.