[JAVA] boj 1726 로봇

문제 링크 : https://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

문제 풀이

너비 우선 탐색으로 풀면 간단히 해결되는 문제였다.

 

문제 조건에 맞게 입력을 받는다. 회전하는 방향이 시계방향으로 90도 또는 반시계방향으로 90도 이므로 구현하기 편하게 입력된 방향을 새로 설정해 주었다. 시계방향으로 회전하는 것을 기준으로 동: 1 서:2 남:3 북:4 로 입력되는 방향으로 서:0 북:1 동:2 남:3 순서로 변경하였다.

 

로봇이 이동하는 방법에는 시계방향으로 회전, 반시계방향으로 회전 또는 1~3만큼 이동하는 것이 있으므로

시계방향으로 회전하는 경우, 반시계방향으로 회전하는 경우, 바라보고 있는 방향으로 1만큼 또는 2만큼 또는 3만큼 이동하는 경우를 queue에 담고 반복하였다. 회전하는 경우에는 특별히 고려해줘야 하는 경우가 없지만 이동하는 경우에는 벽으로 가로막혀 있거나 map을 벗어나면 이동할 수 없으므로 for문을 통해 이동하는 거리만큼 반복을 하여 queue에 담고 만약 벽에 막혀있거나 map을 벗어나는 경우는 그 이상 이동은 할 수 없으므로 queue에 담지 않고 break하여 탈출한다.

 

queue에서 요소를 하나씩 꺼낸 후 다이나믹 프로그래밍과 비슷하게 해당 위치에 왔을때 걸린 횟수를 체크해주었다. 다음 같은 지점에 도착하였을 때(방향도 고려해 줘야하기 때문에 3차원 배열을 이용하였다.) 이전에 방문하였을 때 보다 이동거리가 많다면 더 고려할 필요가 없었다.

코드

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 Main_BJ_1726_로봇 {
  static int M, N, ans;
  static int [][] map;
  static int [][] D = {{0, -1},{-1, 0},{0, 1},{1, 0}}; // 서북동남 순
  static int sX, sY, sD;
  static int eX, eY, eD;
  static int [][][] visited;
  
  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+1][N+1];
    visited = new int[M+1][N+1][4];
    
    for (int i = 1 ; i <= M ; i++) {
      for (int j = 1 ; j <= N ; j++) {
        for (int k = 0 ; k < 4 ; k++) {
          visited[i][j][k] = Integer.MAX_VALUE;
        }
      }
    }
    
    for (int i = 1 ; i <= M ; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 1 ; j <= N ; j++) {
        map[i][j] = Integer.parseInt(st.nextToken());
      }
    }
    
    st = new StringTokenizer(br.readLine());
    
    sX = Integer.parseInt(st.nextToken());
    sY = Integer.parseInt(st.nextToken());
    sD = Integer.parseInt(st.nextToken());
    
    st = new StringTokenizer(br.readLine());
    
    eX = Integer.parseInt(st.nextToken());
    eY = Integer.parseInt(st.nextToken());
    eD = Integer.parseInt(st.nextToken());
    
    // 주어지는 순서는 동 서 남 북 이므로 1 -> 2, 2 -> 0, 3 -> 3, 4 -> 1
    
    if(sD == 1) sD = 2;
    else if(sD == 2) sD = 0;
    else if (sD == 4) sD = 1;
    
    if(eD == 1) eD = 2;
    else if(eD == 2) eD = 0;
    else if (eD == 4) eD = 1;
    
    ans = Integer.MAX_VALUE;
    
    bfs();
    
    System.out.println(ans);
  }
  
  static void bfs() {
    Queue<int []> queue = new LinkedList<>();
    
    queue.offer(new int [] {sX, sY, sD ,0});
    
    while(!queue.isEmpty()) {
      int [] now = queue.poll();
      if (visited[now[0]][now[1]][now[2]] <= now[3]) continue;
      visited[now[0]][now[1]][now[2]] = now[3];
      
      if (now[0] == eX && now[1] == eY && now[2] == eD) {
        ans = Math.min(ans, now[3]);
        continue;
      }
      
      // 왼쪽으로 회전
      queue.offer(new int [] {now[0], now[1], (now[2]+3)%4, now[3]+1});
      
      // 오른쪽으로 회전
      queue.offer(new int [] {now[0], now[1], (now[2]+1)%4, now[3]+1});
      
      // 바라보고 있는 방향으로 전진
      for (int i = 1 ; i <= 3 ; i++) {
        int nx = now[0] + D[now[2]][0]*i;
        int ny = now[1] + D[now[2]][1]*i;
        
        if (nx < 1 || ny < 1 || nx > M || ny > N || map[nx][ny] == 1) break;
        queue.offer(new int [] {nx, ny, now[2], now[3]+1});
      }
    }
  }
}