[백준 1726] 로봇 (JAVA)
문제
풀이
BFS로 해결할 수 있습니다. 4방향이 있기때문에 4방향에 맞춰 방문처리를 하면됩니다.
코드
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 {
static int N, M;
static boolean[][] map;
static Loc destination;
static int[][] dt = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
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());
map = new boolean[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
if (Integer.parseInt(st.nextToken()) == 1) {
map[i][j] = true;
}
}
}
st = new StringTokenizer(br.readLine());
Loc start = new Loc(Integer.parseInt(st.nextToken()) - 1,
Integer.parseInt(st.nextToken()) - 1, change(Integer.parseInt(st.nextToken())));
st = new StringTokenizer(br.readLine());
destination = new Loc(Integer.parseInt(st.nextToken()) - 1,
Integer.parseInt(st.nextToken()) - 1, change(Integer.parseInt(st.nextToken())));
System.out.println(bfs(start));
br.close();
}
public static int bfs(Loc start) {
boolean[][][] visited = new boolean[4][N][M];
Queue<Loc> q = new LinkedList<>();
visited[start.way][start.x][start.y] = true;
q.offer(start);
int time = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int s = 0; s < size; s++) {
Loc loc = q.poll();
if (destination.sameCheck(loc)) {
return time;
}
// 이동
int dx = loc.x;
int dy = loc.y;
for (int i = 0; i < 3; i++) {
dx += dt[loc.way][0];
dy += dt[loc.way][1];
if (!check(dx, dy) || map[dx][dy]) {
break;
}
if (!visited[loc.way][dx][dy]) {
visited[loc.way][dx][dy] = true;
q.offer(new Loc(dx, dy, loc.way));
}
}
// 회전
int[] rotate = rotate(loc.way);
for (int way : rotate) {
if (!visited[way][loc.x][loc.y]) {
visited[way][loc.x][loc.y] = true;
q.offer(new Loc(loc.x, loc.y, way));
}
}
}
time++;
}
return -1;
}
public static int[] rotate(int way) {
int[] result = new int[2];
result[0] = (way + 1) % 4;
result[1] = way - 1;
if (result[1] == -1) result[1] = 3;
return result;
}
public static int change(int way) {
int result;
if (way == 1) result = 2;
else if (way == 2) result = 0;
else if (way == 3) result = 3;
else result = 1;
return result;
}
public static boolean check(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < M;
}
public static class Loc {
int x, y, way;
public Loc(int x, int y, int way) {
this.x = x;
this.y = y;
this.way = way;
}
public boolean sameCheck(Loc loc) {
return this.x == loc.x && this.y == loc.y && this.way == loc.way;
}
}
}
Author And Source
이 문제에 관하여([백준 1726] 로봇 (JAVA)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@solser12/백준-1726-로봇-JAVA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)