[백준 1726 - JAVA] 로봇

1726번: 로봇

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

아래 사항과 방문 처리만 주의한다면 문제없이 풀 수 있다.

1. 방향이 동서남북 순서
2. 시작점과 도착점이 같을 수 있다 -> 그러면 답이 0
3. 2칸 이상 이동시 이동중 벽을 만날 경우 이동할 수 없다.

 

풀이 방법

1. 입력받는 시작, 도착 위치가 1부터 이기때문에 1을 빼준뒤 저장한다.

2. 시작점을 넣고 BFS를 시작하고, 방문 배열은 위치에 방향을 포함하여 3차원으로 처리한다.

   1. 이동 명령 먼저 수행하고, 벽이 있을 경우 break, 방문한곳은 continue

   2. 회전 명령은 단순 switch문으로 처리

import java.io.*;
import java.util.*;

public class Main {

	static class Robot {
		int x, y, d;

		public Robot(int x, int y, int d) {
			this.x = x;
			this.y = y;
			this.d = d;
		}
	}
	
	public static int N, M;
	public static Robot start, end;
	public static int[][] map;
	public static boolean[][][] v;
	public static int[] dx = {0, 0, 1, -1};
	public static int[] dy = {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());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		v = new boolean[4][N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for (int i = 0; i < 2; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken())-1;
			int y = Integer.parseInt(st.nextToken())-1;
			int d = Integer.parseInt(st.nextToken())-1;
			if (i == 0)
				start = new Robot(x, y, d);
			else
				end = new Robot(x, y, d);
		}
		if (isAnswer(start.x, start.y, start.d))
			System.out.println(0);
		else 
			System.out.println(bfs());
	}
	
	
	public static int bfs() {
		Queue<Robot> que = new LinkedList<>();
		que.offer(start);
		v[start.d][start.x][start.y] = true;
		int cnt = 0;
		
		while(!que.isEmpty()) {
			int size = que.size();
			cnt++;
			for (int s = 0; s < size; s++) {
				Robot cur = que.poll();
				for (int i = 1; i <= 3; i++) {
					int nx = cur.x+dx[cur.d]*i;
					int ny = cur.y+dy[cur.d]*i;
					
					if (!isBoundary(nx, ny) || map[nx][ny] == 1) break;
					if (v[cur.d][nx][ny]) continue;
					if (isAnswer(nx, ny, cur.d)) return cnt;
					
					que.offer(new Robot(nx, ny, cur.d));
					v[cur.d][nx][ny] = true;
				}
				for (int i = 0; i < 2; i++) {
					int nd = turn(cur.d, i);
					if (v[nd][cur.x][cur.y]) continue;
					if (isAnswer(cur.x, cur.y, nd)) return cnt;
					
					que.offer(new Robot(cur.x, cur.y, nd));
					v[nd][cur.x][cur.y] = true;
				}
			}
		}
		return cnt;
	}
	
	public static boolean isAnswer(int x, int y, int d) {
		return x == end.x && y == end.y && d == end.d; 
 	}
	
	public static int turn(int d, int order) {		
		switch (d) {
		case 0:
			return (order == 0)? 3:2;
		case 1:
			return (order == 0)? 2:3;
		case 2:
			return (order == 0)? 0:1;
		case 3:
			return (order == 0)? 1:0;
		}
		return 0;
	}
	
	public static boolean isBoundary(int nx, int ny) {
		return nx >= 0 && nx < N && ny >= 0 && ny < M;
	}
}