1726. 로봇 (골드3)
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 19066 | 5203 | 3549 | 26.481% |
문제
많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.
- 명령 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
풀이
- dx, dy, 방향 (동 -> 서 -> 남 -> 북) 3차 방문 배열
1.1. dx, dy, 방향, 명령횟수 클래스 작성 - BFS 사용 => 사방전파
2.1. 전진이동 (1~3칸 이동)
2.1.1. x,y축 방향*칸의 갯수대로 이동
2.1.2. 중간에 벽이 있으면 더 이상 전진 못함
2.1.3. x,y,방향의 방문배열 값이 0이면 방문 체크
2.2. 회전 : right, left 변수로 오른쪽, 왼쪽 돌면 무슨 방향이 나오는지 바꾸기
| 방향 | left 회전 | right 회전 |
|---|---|---|
| 동(0) | 북(3) | 남(2) |
| 서(1) | 남(2) | 북(3) |
| 남(2) | 동(0) | 서(1) |
| 북(3) | 서(1) | 동(0) |
2.2.1. 방문 [x][y][left], 방문[x][y][right] 확인해서 체크
public class Search_1726 {
public static int N, M;
public static int[][] arr; // 위치배열
public static int[][] cnt; // 횟수배열
public static int[][][] visited; // 방문배열 - 방향까지 작성
public static Queue<Point> que = new LinkedList<Point>();
public static int sx, sy, sd, ex, ey, ed;
// 동, 서 , 남, 북
public static int[] dx = { 0, 0, 1, -1 };
public static int[] dy = { 1, -1, 0, 0 };
public static class Point {
public int x;
public int y;
public int d; // 방향
public int cnt; // 각 위치에 도달하기 위한 명령 횟수
public Point(int x, int y, int d, int cnt) {
this.x = x;
this.y = y;
this.d = d;
this.cnt = cnt;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N][M];
cnt = new int[N][M];
visited = new int[N][M][4]; // x축, y축, 방향
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
sx = Integer.parseInt(st.nextToken())-1;
sy = Integer.parseInt(st.nextToken())-1;
sd = Integer.parseInt(st.nextToken())-1;
st = new StringTokenizer(br.readLine());
ex = Integer.parseInt(st.nextToken())-1;
ey = Integer.parseInt(st.nextToken())-1;
ed = Integer.parseInt(st.nextToken())-1;
BFS();
}
public static void BFS() {
// 시작위치, 방향, 명렬횟수 큐에 넣기
que.offer(new Point(sx, sy, sd, 0));
visited[sx][sy][sd] = 1; // 첫방문
while (!que.isEmpty()) {
Point now = que.poll();
// 목적지에 방향까지 일치하면 사용된 명령횟수 출력하고 종료
if(now.x==ex && now.y==ey && now.d==ed) {
System.out.println(now.cnt);
return;
}
// 1칸~3칸까지 전진이동 가능
for(int i=1; i<=3; i++) {
// 바라보는 방향으로 주어진 칸에 따라 전진이동
int nx = now.x + dx[now.d]*i;
int ny = now.y + dy[now.d]*i;
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (arr[nx][ny]==1) break; // 한칸씩 나아가면서 중간에 벽이 있으면 앞으로 진행 불가
if(visited[nx][ny][now.d]==0) { //방문한 적이 없는 위치와 방향이면
visited[nx][ny][now.d] = 1; // 방문체크
// 방향과 명령횟수는 기존의 것 계속 이어서 사용
que.offer(new Point(nx, ny, now.d, now.cnt+1));
}
}
int left = 0;
int right = 0;
// 동서남북에서 왼쪽으로 돌렸을 때 방향, 오른쪽으로 돌렸을 떄 방향 검사
switch(now.d) {
// 동 왼쪽: 북, 오른쪽: 남
case 0: left=3; right=2; break;
// 서 왼쪽: 남, 오른쪽: 북
case 1: left=2; right=3; break;
// 남 왼쪽: 북, 오른쪽: 남
case 2: left=0; right=1; break;
// 북 왼쪽: 북, 오른쪽: 남
case 3: left=1; right=0; break;
}
// 현재방향에서 왼쪽으로 돌았을 때 방문 체크
if(visited[now.x][now.y][left]==0) {
visited[now.x][now.y][left] = 1;
que.offer(new Point(now.x, now.y, left,now.cnt+1 ));
}
// 현재방향에서 오른쪽으로 돌았을 때 방문 체크
if(visited[now.x][now.y][right]==0) {
visited[now.x][now.y][right] = 1;
que.offer(new Point(now.x, now.y, right,now.cnt+1 ));
}
}
// 목적지 찾을 수 없으면 -1
System.out.println(-1);
}
}
* BFS 사용
* 클래스에 기존 값을 넣어가면서 값을 계속해서 이어나간다. => 방향, 명령횟수
