[백준/Java] 13567번 : 로봇

✏️ 문제 분석

https://www.acmicpc.net/problem/13567

 

로봇의 처음 위치는 (0, 0)이고 동쪽으로 향하면서 시작

• TURN 0 : 왼쪽으로 90도 회전
• TURN 1 : 오른쪽으로 90도 회전
• MOVE d : d만큼 앞으로 이동 (d>0)

명령이 n개 주어졌을 때, 최종 위치를 구하라.

(로봇이 MxM 영역 밖을 이탈하면 -1을 출력)

✏️ 구현 아이디어

MOVE 6

 

TURN 0 

MOVE 5

 

TURN 0

MOVE 2

 

TURN 0

MOVE 2

 

TURN 0

MOVE 4

 

TURN 0

MOVE 3

MOVE 2

 

TURN과 MOVE를 묶어서 보면

어느 쪽으로 TURN한 다음에 몇 칸 만큼 MOVE했는지를 하나의 동작으로 계산할 수 있다.

 

TURN 0이면 회전 방향이 오른쪽 -> 위 -> 왼쪽 -> 아래 순서로, 

TURN 1이면 회전 방향이 그 반대로 바뀐다.

 

위 예제의 경우 로봇이 다음과 같은 절차로 이동했다. (처음 진행 방향은 오른쪽)

 

오른 6

위 5

왼 2

아래 2

오른 4

위 5

 

여기서 오른쪽으로 총 6+4=10칸, 왼쪽으로 총 2칸 갔으므로 두 경우를 함께 고려하면 오른쪽으로 8칸 이동한 것과 같다.

그리고 위로 총 5+5=10칸, 아래로 총 2칸 갔으므로 두 경우를 함께 고려하면 위로 8칸 이동한 것과 같다.

 

따라서 (0, 0)에서 시작해서 오른쪽으로 8칸, 위로 8칸 이동한 (8, 8)이 답이다.

✏️ 알고리즘

구현 문제이다. 

✏️ 시간 복잡도

명령 개수 n이 최대 1,000이므로 모든 명령을 주어진 시간 (1초) 안에 연산할 수 있다.

✏️ 코드 설계

1. 값을 입력받음
2. 오른쪽, 위, 왼쪽, 아래로 몇 칸 이동했는지 저장할 배열 dir[] 선언
3. 현재 진행 방향을 저장할 nowDir 선언 (오른쪽부터 시작하므로, 초기값은 0)
4. 명령 하나 입력받을 때마다 다음을 실행
   1. 한 방향으로 이동하는 거리(num)가 M 이상이면 바로 -1을 출력하고 프로그램을 종료
   2. 그렇지 않으면 명령어가 turn인지 move인지 판단
   3. turn이면 nowDir을 방향에 맞게 바꾸기
      • 오른쪽으로 90도 회전 : nowDir++; 
      • 왼쪽으로 90도 회전 : nowDir--; 
      • nowDir값이 0~3 범위를 벗어나지 않도록 조건문 달아주기
   4. move이면 nowDir방향으로 num만큼 이동하기
      • dir[nowDir] += num;
5. dir[]에 방향 별로 몇 칸 이동했는지 저장되어있음
6. h = d[0] - d[2] = (오른쪽으로 이동한 길이) - (왼쪽으로 이동한 길이)
   v = d[1] - d[3] = (위로 이동한 길이) - (아래로 이동한 길이) 
7. (0, 0)이 시작점이므로 h와 v값이 0에서 M 사이면 유효하기 때문에 도착 지점을 출력하고, 아니면 -1을 출력

✏️ 정답 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //값 입력받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        //오른쪽, 위, 왼쪽, 아래
        int[] dir = new int[4];

        //처음 진행 방향은 오른쪽
        int nowDir = 0;

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            String  command = st.nextToken();
            int num = Integer.parseInt(st.nextToken());
			
            //이동 거리가 M 이상이면 -1 출력, 프로그램 종료
            if(num>M){
                System.out.println(-1);
                return;
            }
            
            if(command.equals("TURN")){
                switch(num){
                    case 0: //왼쪽으로 90도 회전
                        nowDir++;
                        if(nowDir>3) nowDir = 0;
                        break;
                    case 1: //오른쪽으로 90도 회전
                        nowDir--;
                        if(nowDir<0) nowDir = 3;
                }
            } else if(command.equals("MOVE")){
                dir[nowDir] += num;
            }
        }

        int h = dir[0] - dir[2]; //오른쪽-왼쪽
        int v = dir[1] - dir[3]; //위-아래

        if(h<0 || v<0 || h>=M || v>=M){
            System.out.println(-1);
        }else System.out.println(h + " " + v);
    }

}