[ 백준 - 3891 ] 로봇

난이도 : S1

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

Tag : 구현

 

문제 탐색하기 

- 이동할 방향 순서가 미리 지정 됨.

- 해당 로봇음다음과 같은 규칙을 가지고 움직인다.

1. 로봇은 사용자가 지정한 방향을 일직선으로 움직임.

2. 벽, 이미 방문한곳, 장애물을 만날 경우 로봇은 사용자가 지정한 다음 방향으로 움직인다.

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

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

 

결국 4방향을 모두 확인하여 이동할 곳이 없으면 멈춘다는 것이다. 

다른 문제와 차이점은 방향을 확인하는 순서가 정해져있다는 것이다.

해당 방향 순서로 탐색을 진행하면 된다. 

 

 

시도 1 ( 성공 😲)

떠오른 문제 해결 방법

방향에 따른 커서를 둡니다. 해당 커서의 방향으로 이동을 진행하고, 해당 방향으로 이동이 불가능할 경우 커서를 다음 방향으로 이동시킵니다. 그리고 이동을 진행합니다.

한 곳에서 4방향을 모두 확인했는데 이동하지 못한다면 해당 위치를 출력합니다. 

 

 

시간복잡도⏰
특정 지점에서 최대 4가지 방향을 확인, 최대 1000*1000 공간을 이동할 수 있기 때문에 4*(1,000,000) 의 시간복잡도가 나온다.

하나의 길과 연결된 모든 길을 파악하는 최악의 경우는 마을이 모두 길로 이어졌을 때, O(n^2) = 10000이 소요된다.

1초안에 충분히 해결 가능하다.

구현 방법 

세부 구현 사항

1. 주어진 값들을 입력받는다.

2. 이동 순서를 셋팅한다.

3. 첫 위치에서 이동한다.

- 더이상 이동 못할 경우 다른 방향으로 이동할 수 있는지 확인한다.

- 이동할 수 있을 경우 이동한다.

- 이동이 불가능 할경우 종료한다.

 

 전체코드

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

class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int c = sc.nextInt();
        int[][] board = new int[r][c];
        int k = sc.nextInt();
        for (int i = 0; i < k; i++) {
            int br = sc.nextInt();
            int bc = sc.nextInt();
            board[br][bc] = 2;
        }

        int nowR = sc.nextInt();
        int nowC = sc.nextInt();
        int[] dirR = new int[4];
        int[] dirC = new int[4];

        for (int i = 0; i < 4; i++) {
            int dir = sc.nextInt();
            switch (dir) {
                case 1: {
                    dirR[i] = -1;
                    dirC[i] = 0;
                    break;
                }
                case 2: {
                    dirR[i] = 1;
                    dirC[i] = 0;
                    break;
                }
                case 3: {
                    dirR[i] = 0;
                    dirC[i] = -1;
                    break;
                }
                case 4: {
                    dirR[i] = 0;
                    dirC[i] = 1;
                    break;
                }
            }
        }

        int cur = 0;
        while (true) {
            // 현재 위치를 방문표시
            board[nowR][nowC] = 1;

            int dir = 0;
            for (dir = 0; dir < 4; dir++) {
                int nextR = nowR + dirR[cur];
                int nextC = nowC + dirC[cur];

                // 다음 위치가 벽인지 확인
                if (nextR < 0 || nextR >= r || nextC < 0 || nextC >= c) {
                    cur = (cur + 1) % 4;
                    continue;
                }
                // 다음 위치가 장애물(2) 또는 방문 지역(1)인지 확인 = 0이아님
                if (board[nextR][nextC] != 0) {
                    cur = (cur + 1) % 4;
                    continue;
                }
                // 방문 표시 후다음 위치로 이동
                board[nextR][nextC] = 1;
                nowR = nextR;
                nowC = nextC;
                break;
            }
            if (dir == 4) {
                System.out.println(nowR + " " + nowC);
                break;
            }
        }

    }
}

 

마무리

여러 변수들이 있었는데 가독성 있게 통일해준것이 코드를 안헷갈리고 짤수있었던 것 같다.

또한 방향이 주어지고 별도의 별수없이 처음부터 각 방향을 dirR, dirC배열에 넣어주었던 것이 좀 더 복잡해질 수 있는 코드를 막아준 것 같다.