study blog
[백준] 1726 로봇 - JAVA 본문
★★★☆
문제
https://www.acmicpc.net/problem/1726
풀이시간 : 50분
풀이
도착 지점까지의 최소값을 구해야 하므로 BFS 탐색으로 구현하였다.
1. 앞으로 한칸 ~ 세칸 까지 전진
2. 왼쪽 혹은 오른쪽으로 90도 회전
이 두가지의 경우 중 방문하지 않은 지점만 큐에 추가하면서 탐색한다.
로봇이 바라보고 있는 방향도 고려해야 하기 때문에 visited 배열을 3차원 배열로 선언하였다.
어렵지 않은 문제임에도 계속 통과하지 못했는데 전진 명령을 수행 할 때 중간에 맵이 가로막혀 있으면 break를 했어야 했는데 continue를 하는 바람에 오래 걸렸다.
코드
import java.io.*;
import java.util.*;
public class Main {
/*
로봇
골드 3
시간 : 100ms
메모리 : 12796kb
*/
static int M, N;
static int[][] map;
static Point s;
static int R,C,D;
static boolean[][][] v;
static int[] dr = {0,0,1,-1}; // 동서남북
static int[] dc = {1,-1,0,0};
public static void main(String[] args) throws Exception {
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];
v = new boolean[M][N][4];
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());
}
}
st = new StringTokenizer(br.readLine());
s = new Point( Integer.parseInt(st.nextToken())-1,
Integer.parseInt(st.nextToken())-1,
Integer.parseInt(st.nextToken())-1,0);
st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken())-1;
C = Integer.parseInt(st.nextToken())-1;
D = Integer.parseInt(st.nextToken())-1;
v[s.r][s.c][s.d] = true;
System.out.println(bfs(s));
}
private static int bfs(Point point) {
Queue<Point> q = new LinkedList<>();
q.add(point);
while(!q.isEmpty()) {
Point now = q.poll();
// 도착지인지 체크
if(now.r==R && now.c == C && now.d == D)
return now.cnt;
// go
for (int i = 1; i <= 3; i++) {
int nr = now.r + dr[now.d]*i;
int nc = now.c + dc[now.d]*i;
if(!check(nr,nc)) continue;
// 중간에 벽이 있으면 아예 끝내야 한다
if(map[nr][nc]==1) break;
if(!v[nr][nc][now.d]) {
v[nr][nc][now.d] = true;
q.add(new Point(nr,nc,now.d,now.cnt+1));
}
}
// turn 오른쪽 90도 동0 -> 남2 -> 서1 -> 북3
// 왼쪽 동0 -> 북3 -> 서1 -> 남2
int left = 0, 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(!v[now.r][now.c][left]) {
v[now.r][now.c][left] = true;
q.add(new Point(now.r,now.c,left,now.cnt+1));
}
if(!v[now.r][now.c][right]) {
v[now.r][now.c][right] = true;
q.add(new Point(now.r,now.c,right,now.cnt+1));
}
}
return -1;
}
private static boolean check(int r, int c) {
return r>=0 && r<M && c>=0 && c<N;
}
public static class Point {
int r;
int c;
int d;
int cnt;
public Point(int r, int c, int d,int cnt) {
this.r = r;
this.c = c;
this.d = d;
this.cnt = cnt;
}
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 2212 센서 - JAVA (0) | 2022.04.27 |
---|---|
[백준] 9019 DSLR - JAVA (0) | 2022.04.26 |
[백준] 11000 강의실 배정 - JAVA (0) | 2022.04.15 |
[백준] 16234 인구 이동 - JAVA (0) | 2022.01.29 |
Comments