[BOJ] 1726 - 로봇 JAVA

www.acmicpc.net/problem/1726

1726번: 로봇

문제

많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.

• 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
• 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

공장 내 궤도가 설치되어 있는 상태가 아래와 같이 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다. 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고, 1은 궤도가 없어 로봇이 갈 수 없는 지점이다. 로봇이 (4, 2) 지점에서 남쪽을 향하고 있을 때,  이 로봇을 (2, 4) 지점에서 동쪽으로 향하도록 이동시키는 것은 아래와 같이 9번의 명령으로 가능하다.

로봇의 현재 위치와 바라보는 방향이 주어졌을 때, 로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데 최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공장 내 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N이 빈칸을 사이에 두고 주어진다. 이때 M과 N은 둘 다 100이하의 자연수이다. 이어 M줄에 걸쳐 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어진다. 다음 줄에는 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 마지막 줄에는 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.

출력

첫째 줄에 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수를 출력한다.

예제 입력 1

5 6

0 0 0 0 0 0

0 1 1 0 1 0

0 1 0 0 0 0

0 0 1 1 1 0

1 0 0 0 0 0

4 2 3

2 4 1

예제 출력 1

9

 

 

 

 

 

 

 

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

class Pair {
    int r, c, dir, cnt;
    Pair(int r, int c, int dir, int cnt) {
        this.r = r;
        this.c = c;
        this.dir = dir;
        this.cnt = cnt;
    }
}

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int[][] map = null;
    static boolean[][][] check = null;

    static Pair begin = null;
    static Pair end = null;
    static int N, M, ans;

    // [0, 1, 2, 3, 4] = [0, 동, 서, 남, 북] 방향 맞춰줘야 한다
    static int[] rArr = {0, 0, 0, 1, -1};
    static int[] cArr = {0, 1, -1, 0, 0};

    public static void bfs() {
        Queue<Pair> que = new ArrayDeque<>();
        que.add(begin);
        check[begin.r][begin.c][begin.dir] = true;

        while(!que.isEmpty()) {
            Pair p = que.poll();
            int r = p.r, c = p.c, dir = p.dir, cnt = p.cnt;
            if(r == end.r && c == end.c && dir == end.dir) {
                ans = cnt;
                return;
            }

            // 현재 바라본 방향에서 1, 2, 3칸 이동 명령
            for(int i = 1; i <= 3; i++) {
                int nr = r + rArr[dir] * i;  // 현재 방향으로 i칸 이동
                int nc = c + cArr[dir] * i;
                if(1 <= nr && nr <= N && 1 <= nc && nc <= M) {  // 범위 체크
                    if(map[nr][nc] == 0 && !check[nr][nc][dir]) {
                        que.add(new Pair(nr, nc, dir, cnt + 1));
                        check[nr][nc][dir] = true;
                    }else if(map[nr][nc] == 1) {
                        break;  // 벽을 만나면 더 건너뛸 수 없음
                    }
                }
            }

            // 현재 방향을 제외한 모든 방향으로 이동
            // 180도 방향에 대해서는 +2 처리하고 나머진 +1
            for(int i = 1; i <= 4; i++) {  // i = 이동할 방향
                if(dir != i && !check[r][c][i]) {  // 현재 위치에서 방향만 도는 것임
                    int inst = 1;
                    if(dir == 1) {
                        if(i == 2) inst++;
                    }else if(dir == 2) {
                        if(i == 1) inst++;
                    }else if(dir == 3) {
                        if(i == 4) inst++;
                    }else if(dir == 4){
                        if(i == 3) inst++;
                    }
                    que.add(new Pair(r, c, i, cnt + inst));
                    check[r][c][i] = true;
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N+1][M+1];
        check = new boolean[N+1][M+1][5];
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int dir = Integer.parseInt(st.nextToken());
        begin = new Pair(r, c, dir, 0);

        st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        dir = Integer.parseInt(st.nextToken());
        end = new Pair(r, c, dir, 0);

        bfs();
        System.out.println(ans);
    }
}

 

접근법은 어렵지 않게 떠올릴 수 있었는데 구현에서 애를 먹었다.

 

현재 위치에서 수행할 수 있는 모든 명령을 수행해서 큐에 넣으면서 BFS를 돌리면 된다.

수행할 수 있는 명령은 아래와 같다.

1. 앞으로 이동 1 or 2 or 3칸 (3가지)

2. 현재 바라보고 있는 방향을 제외한 너머지 방향으로 방향 전환 (3가지)

이렇게 총 6가지이다.

 

이때 주의해야 할 점은, 방향전환에 사용되는 명령어의 개수가 모두 같지는 않다는 것이다.

한 번의 명령으로 90도만 회전할 수 있기 때문에 180도를 꺾어서 반대 방향을 보기 위해서는 두 번의 카운트를 세야 한다.

 

앞으로 이동하는 건 그냥 세면 되겠다만.. 이놈의 방향전환을 어떻게 해야 할지가 문제였다.

동, 서, 남 북 = 1, 2, 3, 4로 방향을 표시해야 하는데..

한 번 돌 때마다 방향을 1씩 증가or감소 시키고 1, 4에서의 증감은 4, 1로 건너뛰게 하는 식으로 하려고 했는데..

90도씩 전환하는 방향의 순서는 동쪽부터 시작한다고 했을 때 동서남북이 아니라 동남서북 순서가 되어버리기 때문이다.

 

그래서 동서남북 방향 1,2,3,4를 인덱스로 두고 dir = {0, 1, 3, 2, 4} 이렇게 배열의 원소를 가리키도록 짤까 했지만 이것 때문에 코드가 너무 더러워지고 헷갈려서... 결국 구글링으로 정답을 확인했다.

 

 

매번 느끼는 거지만 이런 식으로 구현능력이 부족해서 막히는 경우가 너무 많다.

로직 자체를 떠올리지 못하는 건 아닌데 이런 식으로 막히면 좌절감이 두 배가 되는 듯 하다.

 

 

방향 전환을 90도씩 할 때마다 명령을 한 번 수행한다는 점에 주목하자.

다시말해, 명령 횟수를 세는 기준을 "어느 방향으로 회전했는가?"가 아니라 "몇 도를 회전했는가?"로 잡는 것이다.

 

즉,

목표 방향이 동쪽이라면 이전 방향이 서쪽일 경우에 +2, 나머지는 +1

목표 방향이 서쪽이라면 이전 방향이 동쪽일 경우에 +2, 나머지는 +1

목표 방향이 남쪽이라면 이전 방향이 북쪽일 경우에 +2, 나머지는 +1

목표 방향이 북쪽이라면 이전 방향이 남쪽일 경우에 +2, 나머지는 +1

이렇게 명령 횟수를 더해주는 것이다.

 

 

 

 

 

 

풀이 2.

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

class Pair {
    int r, c, d, cnt;
    Pair(int r, int c, int d, int cnt) {
        this.r = r;
        this.c = c;
        this.d = d;
        this.cnt = cnt;
    }
}

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringBuilder sb = null;
    static StringTokenizer st = null;

    static int n, m, ans;
    static int[][] map = null;
    static boolean[][][] check = null;
    static int[] rArr = {0, 0, 0, 1, -1};  // X동서남북 맞춰줘야 함
    static int[] cArr = {0, 1, -1, 0, 0};

    static Pair start = null;
    static Pair end = null;

    public static void bfs() {
        Queue<Pair> que = new ArrayDeque<>();
        que.add(start);
        check[start.r][start.c][start.d] = true;

        while(!que.isEmpty()) {
            Pair p = que.poll();
            int r = p.r, c = p.c, d = p.d, cnt = p.cnt;
            if(r == end.r && c == end.c && d == end.d) {
                ans = cnt;
                return;
            }

            // 내 방향으로 1, 2, 3 이동
            for(int i = 1; i <= 3; i++) {
                int nr = r + rArr[d] * i;
                int nc = c + cArr[d] * i;
                if(1 <= nr && nr <= n && 1 <= nc && nc <= m) {
                    if(map[nr][nc] == 1) break;  // 벽을 만나면 더 나아갈 수 없음
                    if(!check[nr][nc][d]) {
                        check[nr][nc][d] = true;
                        que.add(new Pair(nr, nc, d, cnt+1));
                    }
                }
            }

            // 왼쪽 90도, 오른쪽 90도
            if(d == 1 || d == 2) {
                if(!check[r][c][3]) {
                    check[r][c][3] = true;
                    que.add(new Pair(r, c, 3, cnt+1));
                }
                if(!check[r][c][4]) {
                    check[r][c][4] = true;
                    que.add(new Pair(r, c, 4, cnt+1));
                }
            }else if(d == 3 || d == 4) {
                if(!check[r][c][1]) {
                    check[r][c][1] = true;
                    que.add(new Pair(r, c, 1, cnt+1));
                }
                if(!check[r][c][2]) {
                    check[r][c][2] = true;
                    que.add(new Pair(r, c, 2, cnt+1));
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n+1][m+1];
        check = new boolean[n+1][m+1][5];
        for(int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        start = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);
        st = new StringTokenizer(br.readLine());
        end = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);

        bfs();
        System.out.println(ans);
    }
}

 

생각해보니 굳이 모든 방향으로 전부 돌기 위해 애를 쓸 필요가 없었다. 그냥 현재 위치에서 왼쪽, 오른쪽으로 한 번 씩만 돌고 마무리해도 나머지 방향으로는 그 다음 턴에서 돌아줄 테니까.

 

그냥 1 or 2 or 3칸 이동 3가지 경우 + 좌 or 우 90도 2가지 경우만 수행하고 다음 반복으로 넘어가면 된다.