[BOJ] 1726. 로봇(BFS).java

#. Problem

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

* The copyright in this matter is in BOJ

 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

로봇의 이동을 제어하는 명령을 먼저 확인해보자.

명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.

로봇은 최대 3칸 이동할 수 있다.

명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

로봇은 특정 위치에서

해당 방향으로 최대 3칸 이동하거나, 회전을 할 수 있다.

생각해주어야 하는 Point.!

1. 특정 위치로 이동해서 올 수 있는 방법은 총 4가지이다.

   동쪽으로 오는 경우, 서쪽으로 오는 경우, 남쪽으로..

   그러므로 visit 상태 처리는 Map을 4가지 방향으로 체크해줄 수 있는

   3차원 배열을 사용해주어야 한다. visited[방향][행][열]

2. 방향전환

오른쪽, 왼쪽으로 90도 회전이라도 하면 사실 헷갈려서 꼬이기 쉽다.

조금 쉽게 생각해보자면

- 북쪽에서 남쪽으로 회전하고 싶다면

  오른쪽으로 180도 회전하거나, 왼쪽으로 180도 회전하거나 두 번의 명령이 필요하다.

- 왼쪽으로 90도 회전하는 경우는 오른쪽으로 270도 회전하는 것과 같다.

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ1726 {
 
    static int M, N, map[][];
    static int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1}; 
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        M = Integer.parseInt(st.nextToken()); // 세로
        N = Integer.parseInt(st.nextToken()); // 가로
        map = new int[M][N];
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        Robot[] position = new Robot[2];
        for (int i = 0; i < 2; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken());
            // 방향 세팅
            if(c == 1) c = 1; // 동
            else if(c == 2) c = 3; // 서
            else if(c == 3) c = 2; // 남
            else if(c == 4) c = 0; // 북
                    
            position[i] = new Robot(a, b, c, 0); 
        }
        
        System.out.println(process(position[0], position[1]));
    }
 
    private static int process(Robot start, Robot end) {
 
        boolean[][][] visited = new boolean[4][M][N];
        Queue<Robot> q = new LinkedList<>();
        visited[start.dir][start.r][start.c] = true;
        q.add(new Robot(start.r, start.c, start.dir, start.cnt));
        
        while(!q.isEmpty()) {
            
            Robot now = q.poll();
            // 도착 지점에 도달
            if(now.r == end.r && now.c == end.c && now.dir == end.dir) return now.cnt;
            
            // 해당 방향으로 이동(최대 3 칸) 
            for (int i = 1; i <= 3; i++) {
                int rr = now.r + dr[now.dir] * i;
                int cc = now.c + dc[now.dir] * i;
                // 범위를 초과하거나 갈 수 없는 곳이라면 break
                if(rr < 0 || cc < 0 || rr >= M || cc >= N || map[rr][cc] == 1) break;
                // 해당 방향으로 이미 방문한 곳이라면
                if(visited[now.dir][rr][cc]) continue;
                
                visited[now.dir][rr][cc] = true;
                q.add(new Robot(rr, cc, now.dir, now.cnt + 1));
            }
            
            // 방향을 전환
            for (int d = 1; d < 4; d++) {
                int cnt = d != 3 ? d : 1;
                int ndir = (now.dir + d) % 4; 
                
                // 해당 방향으로 이미 방문한 곳
                if(visited[ndir][now.r][now.c]) continue;
                
                visited[ndir][now.r][now.c] = true;
                q.add(new Robot(now.r, now.c, ndir, now.cnt + cnt));    
            }
        }
        
        return -1;
    }
 
    static class Robot {
        int r, c, dir, cnt;
 
        public Robot(int r, int c, int dir, int cnt) {
            this.r = r;
            this.c = c;
            this.dir = dir;
            this.cnt = cnt;
        }
    }
}
 

line 36~39) 회전을 편하게 하기 위해 임으로 방향을 설정.(북동남서)

line 49) 각 방향에 따른 이동 상태를 저장하기 위해 3차원 visit 배열 선언

line 61~71) 해당 방향으로 최대 3칸 이동

line 65) 범위를 초과하거나 갈 수 없는 곳이라면 더이상 갈 필요가 없다.(여기서 실수했었다는..!)

line 67) 해당 방향으로 이미 방문했더라도 이후 방향으로 3칸 이내라면 더 가볼 수 있으므로 continue

line 74~83) 방향 전환

line 75) 오른쪽으로 270도 회전할 경우 왼쪽으로 하나의 명령으로 회전할 수 있으므로 명령 수는 1로