알고리즘 로봇(JAVA)

1006 : 로봇

제한시간: 1ms    메모리제한: 64MB
해결횟수: 345회    시도횟수: 2524회   

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

 

*명령 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로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.

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

[Copy] 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

[Copy] 9

출처 : KOI 본선 2005 고3

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111

/**************************************************************     Problem: 1006     User: a132034     Language: Java     Result: Success     Time:316 ms     Memory:17472 kb ****************************************************************/       import java.util.Scanner;     public class Main{           static boolean[][] S = new boolean[110][110];     static int[][][] Check = new int[110][110][5];           static positionInfo[] Bfs = new positionInfo[40010];     static positionInfo St = new positionInfo(), Fi = new positionInfo();       static int Count;     static int[] Gox = {0,0,0,1,-1};     static int[] Goy = {0,1,-1,0,0};           static int[][] Turn = {{0,0,0},         {0,3,4},         {0,3,4},         {0,1,2},         {0,1,2}};           public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int M = sc.nextInt();         int N = sc.nextInt();                   for(int i = 1 ; i <=M; ++i){             for(int j = 1; j <= N; ++j){                 for(int k = 1; k <=4; ++k)                     Check[i][j][k]=Integer.MAX_VALUE;             }         }                   int a = 0;         for (int i = 1; i <= M; i++) {             for (int j = 1; j <= N; j++) {                 a = sc.nextInt();                 if(a==1) S[i][j] = true;                 else S[i][j] = false;             }         }               St.x = sc.nextInt();         St.y = sc.nextInt();         St.w = sc.nextInt();         Fi.x = sc.nextInt();         Fi.y = sc.nextInt();         Fi.w = sc.nextInt();                   findMinCost(M, N);                   System.out.println(Check[Fi.x][Fi.y][Fi.w]);     }       public static void findMinCost(int M, int N){                   Bfs[1]=St;//start point setting         Check[Bfs[1].x][Bfs[1].y][Bfs[1].w]=0; //start point is 0         Count=1; // count ++;                             for(int i=1;;i++){             if(Count < i ) break;                           for (int j = 1; j <=3 ; ++j) {                 if(Bfs[i].x+Gox[Bfs[i].w]*j < 1 || Bfs[i].x + Gox[Bfs[i].w]*j > M) break;                 if(Bfs[i].y+Goy[Bfs[i].w]*j < 1 || Bfs[i].y + Goy[Bfs[i].w]*j > N) break;                                   if(S[Bfs[i].x+Gox[Bfs[i].w]*j][Bfs[i].y+Goy[Bfs[i].w]*j] == true) break;                 if(Check[Bfs[i].x+Gox[Bfs[i].w]*j][Bfs[i].y+Goy[Bfs[i].w]*j][Bfs[i].w]!=Integer.MAX_VALUE) continue;                                   Check[Bfs[i].x+Gox[Bfs[i].w]*j][Bfs[i].y+Goy[Bfs[i].w]*j][Bfs[i].w] = Check[Bfs[i].x][Bfs[i].y][Bfs[i].w]+1;                 Count++;                 Bfs[Count] = new positionInfo();                 Bfs[Count].x = Bfs[i].x + Gox[Bfs[i].w]*j;                 Bfs[Count].y = Bfs[i].y + Goy[Bfs[i].w]*j;                 Bfs[Count].w = Bfs[i].w;             }                           for(int j = 1; j <=2; ++j){                 if(Check[Bfs[i].x][Bfs[i].y][Turn[Bfs[i].w][j]] != Integer.MAX_VALUE) continue;                               Check[Bfs[i].x][Bfs[i].y][Turn[Bfs[i].w][j]] = Check[Bfs[i].x][Bfs[i].y][Bfs[i].w]+1;                 Count++;                 Bfs[Count] = new positionInfo();                 Bfs[Count].x = Bfs[i].x;                 Bfs[Count].y = Bfs[i].y;                 Bfs[Count].w = Turn[Bfs[i].w][j];             }         }               } }   //position information class positionInfo{     public int x,y,w;           public positionInfo(){x=0;y=0;w=0;} };

사실 예전에 풀었던 거라.. 기억이 너무 가물가물하다.

지금 소스를 보자니 약간 C++스타일로 풀었던 것 같다. 

기본적인 컨셉은. 

1. 모든 점에서 5가지 움직임이 가능하다. (go 또는 동 서 남 북의 방향으로의 전환) - Check변수의 좌표별 크기를 5로 하였다. 

2. 1칸을 전진할 수 없는 경우(막힌 경우) 그 이상의 칸도 전진하지 못한다. (2, 3칸)

이런 컨셉을 가지고 풀었던 것 같다... 사실 너무 오래전에 풀었던 문제라... 

2차원 배열 S는 공장 궤도 상태를 나타낸 2차원 배열로 1인 경우 true로 받았고 0인 경우(갈 수 있는 경우) false로 놓았다.

3차원 배열 Check는 1번 컨셉의 5가지 움직임을 했는지 체크하는 배열이다. - 첫 값을 Integer.MAX_VALUE로 놓았다. 

Bfs는 위치와 방향을 가진 변수 배열로 Check를 위해 만들었다. 

Check[x][y][w] 는 x,y 지점의 w방향을 바라볼 때의 최소 명령 횟수이다. 

Check[Bfs[i].x+Gox[Bfs[i].w]*j][Bfs[i].y+Goy[Bfs[i].w]*j][Bfs[i].w] = Check[Bfs[i].x][Bfs[i].y][Bfs[i].w]+1;

Check[Bfs[i].x][Bfs[i].y][Turn[Bfs[i].w][j]] = Check[Bfs[i].x][Bfs[i].y][Bfs[i].w]+1;

이 라인이 명령횟수를 증가해주는 함수이다. 

첫 번째 for loop는 이동을 위해 만들었고, 두 번째 for loop는 방향전환(왼쪽 또는 오른쪽)을 위해 만들었다. 

이때 Turn 변수를 사용하는데 현재 방향에서 전환할 수 있는 방향으로 2차원 배열로 만들었다. (0번째는 쓰지않음)

Turn[Bfs[i].w][j] -> 1, 2(동, 서)의 경우 3, 4로 방향전환이 가능

-> 3, 4(남, 북)의 경우 1, 2로 방향전환이 가능

배열이나 for loop를 예전에 풀었던 거라 1부터 시작해서 약간 헷갈릴 수도 있을 것 같으나.. 차근차근 보면 그 외에 크게 어려운 점은 없었다.