[백준] 13901. 로봇 (JAVA)

이번에 풀어 볼 문제는 < 백준 13901번. 로봇 > 이다.

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

📌 문제 탐색하기

목표

규칙에 맞게 이동한 뒤, 로봇의 최종 위치 출력하기

입력

[첫 줄] 방의 크기 R, C ( 3 ≤ R, C ≤ 1,000 )

[둘째줄] 장애물의 개수 k ( 0 ≤ k ≤ 1,000 )

[k개의 줄] 각 장애물의 위치 좌표 br (0 ≤ br ≤ R – 1) , bc (0 ≤ bc ≤ C - 1)

[다음 줄] 로봇의 시작 위치 좌표 sr(0 ≤ sr ≤ R – 1), sc(0 ≤ sc ≤ C - 1)

[다음 줄] 이동 방향의 순서(총 4개가 입력, 1은 위 방향, 2은 아래 방향, 3은 왼쪽 방향, 4는 오른쪽 방향)

출력

로봇의 마지막 위치 r, c를 출력하기

해야 할 것

1. 각 규칙 구현하기

- 사용자가 지정한 방향을 일직선으로 움직인다.

- 이동 중 벽이나 방문한 지역, 장애물을 만날 경우 로봇은 사용자가 지정한 다음 방향으로 움직인다.

- 사용자가 지정한 다음 방향이 없다면 맨 처음 방향으로 돌아가서 위의 과정을 반복한다.

- 로봇이 움직일 수 없을 경우 동작을 멈춘다.

 

아이디어

1. 각 규칙 구현하기

 

로봇이 규칙에 맞게 이동하도록 하는 함수를 정의하도록 하자.

이 함수에는 크게 아래 두 기능이 정의되어 있어야 한다.

 

1) 현재 위치에서 이동할 수 있는 지 여부 탐색 => 이동하지 못하면 동작을 멈추고 그 위치 좌표를 반환하기

2) 다음에 이동해야 할 방향으로 움직이기 

 

1) 번의 경우 따로 함수로 빼서 구현하고자 한다.

상,하,좌,우 를 탐색했을 때 네 방향 모두 이동이 불가능하면 false를 반환해주는 함수를 만들자.

 

2) 다음에 이동해야 할 방향은 사용자가 입력한 방향 순서에 따라 정해져야 한다.

따라서 사용자가 입력한 방향을 배열로 저장해두고, 만약 해당 방향으로 이동 불가시 인덱스를 하나 증가시켜 다음 원소를 확인할 수 있도록 하자. 만약 인덱스가 방향 배열의 끝(3)에 다다르면 다음 인덱스는 0이 되어야 한다.

 

📌 코드 설계하기

1. input 입력받기

2. 현재 위치에서 이동할 수 있는 칸이 있는지 확인하는 함수를 구현한다.

3. 로봇을 이동시키는 함수를 구현한다.

- 현재 노드에서 이동 가능한지 먼저 탐색한다. 만약 이동이 불가능하면, 현재 노드를 바로 return 한다.

- 이동 가능하다면,

   - 사용자의 입력이 담긴 방향 배열에서 diPoint 위치에 해당하는 값을 읽어온다.

   - 1이면 상, 2이면 하, 3이면 좌, 4이면 우 가 될 수 있도록 방향벡터 배열 dx, dy 를 구성해준다.

static int[] dx = new int[]{0, -1, 1, 0, 0};
static int[] dy = new int[]{0, 0, 0, -1, 1}; // 0(사용하지 않음), 상 하 좌 우

int nx = sr + dx[direction[diPoint]];
int ny = sc + dy[direction[diPoint]];

 

   - 해당 방향으로 이동 가능한지 판단한다.

          - 불가능하면 : diPoint 를 1 증가시키고 다시 해당 방향으로 이동 가능한지 확인한다. 만약 현재 diPoint가 3이라면 0으로 초기화 시켜준다.

          - 가능하다면, 해당 노드로 이동해서 다시 탐색을 계속한다. (재귀로 구현)

📌 정답 코드

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


public class Main {

    static int R, C;
    static char[][] map;
    static boolean[][] visited;
    static int[] direction;

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

        //입력받기
        String[] firstLine = bufferedReader.readLine().split(" ");
        R = Integer.parseInt(firstLine[0]);// 방의 크기 R, C (3 ≤ R, C ≤ 1,000) , 방의 크기 최대 10^6 칸
        C = Integer.parseInt(firstLine[1]);

        map = new char[R][C];
        visited = new boolean[R][C];

        for (int i = 0; i < R; i++) {
            char[] line = map[i];
            Arrays.fill(line, '*');
        }

        int k = Integer.parseInt(bufferedReader.readLine());// 장애물의 개수 k ( 0 ≤ k ≤ 1,000 )
        for (int i = 0; i < k; i++) {
            String[] secondLine = bufferedReader.readLine().split(" ");
            int br = Integer.parseInt(secondLine[0]);
            int bc = Integer.parseInt(secondLine[1]);// k개의 줄에 장애물의 위치 좌표 br, bc
            map[br][bc] = 'x';
        }

        String[] thirdLine = bufferedReader.readLine().split(" ");// 로봇의 시작위치 좌표 sr, sc
        int sr = Integer.parseInt(thirdLine[0]);
        int sc = Integer.parseInt(thirdLine[1]);

        String[] fourthLine = bufferedReader.readLine().split(" ");
        direction = new int[4];
        for (int i = 0; i < 4; i++) {
            direction[i] = Integer.parseInt(fourthLine[i]);// 이동방향 순서 ( 1 : 상, 2 : 하 , 3: 좌 : 4: 우 ), 총 4개 입력
        }

        // 로봇의 마지막 위치좌표 r, c 출력
        int[] lastPosition = moveRobot(sr, sc);
        System.out.println(lastPosition[0] + " " + lastPosition[1]);

    }

    static int[] dx = new int[]{0, -1, 1, 0, 0};
    static int[] dy = new int[]{0, 0, 0, -1, 1}; // 0, 상 하 좌 우
    static int diPoint = 0;

    static int[] moveRobot(int sr, int sc) {

        visited[sr][sc] = true;

        boolean canMove = findCanMove(sr,sc);

        if(!canMove){
            int[] lastSpot = new int[]{sr,sc};
            return lastSpot;
        }

        while(true){

            int nx = sr + dx[direction[diPoint]];
            int ny = sc + dy[direction[diPoint]];

            if(nx<0 || ny<0 || nx>=R || ny>=C || map[nx][ny] == 'x'|| visited[nx][ny]){
                if(diPoint == 3){
                    diPoint = 0;
                }else{
                    diPoint++;
                }
            }else{
                int[] lastSpot = moveRobot(nx,ny);
                return lastSpot;
            }

        }


    }

    static boolean findCanMove(int cx, int cy){
        int blockCount=0;
        for(int i=1; i<5; i++){
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if(nx < 0 || ny < 0 || nx >= R || ny >= C || map[nx][ny] == 'x' || visited[nx][ny]){
                blockCount++;
            }
        }

        if(blockCount == 4){
            return false;
        }else{
            return true;
        }
    }
}

 

 

📌 알게 된 것

dx, dy 로 구현 시 x 좌표는 dx를, y좌표는 dy를 참조해야 하는데 자꾸 실수한다. 주의하자.

 

다음 칸으로 이동했으면, 이후 while문이 계속 실행되지 않도록 아래와 같이 return 문을 꼭 넣어줘야 한다. 그리고 이렇게 해주어야 재귀호출된 함수가 반환한 값을 가장 처음 호출한 함수가 받아 리턴해줄 수 있다.

 

int[] lastSpot = moveRobot(nx,ny);
return lastSpot;