로봇


백준 [1726] 로봇

문제보기
Alt text

풀이

  • bfs
  • 주의사항
    1. 아래에서 break가 아닌 continue
      if (visited[d][x][y] != 0 && visited[d][x][y] <= command + 1)
      continue;
      
    2. 2번의 명령으로 180도 회전할 수 있다.
    3. 인덱스 실수 주의

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M, ans;
	static int[][] map;
	static int[][] station;
	static int[] dx = { 0, 0, 1, -1 }; // 동서남북
	static int[] dy = { 1, -1, 0, 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 int[N][M];
		station = new int[2][3];
		ans = 987654321;

		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());
			for (int j = 0; j < 3; j++) {
				station[i][j] = Integer.parseInt(st.nextToken()) - 1;
			}
		}

		move();
		System.out.println(ans);
	}

	public static void move() {
		Queue<int[]> queue = new LinkedList<>();
		int[][][] visited = new int[4][N][M];
		queue.add(new int[] { station[0][0], station[0][1], station[0][2], 0 });

		while (!queue.isEmpty()) {
			int[] q = queue.poll();

			if (q[3] >= ans)
				continue;

			if (q[0] == station[1][0] && q[1] == station[1][1]) {
				if (q[2] == station[1][2]) {
					ans = Math.min(ans, q[3]);
				} else {
					boolean flag = false;
					if (q[2] == 0 && station[0][2] == 1) {
						flag = true;
					} else if (q[2] == 1 && station[0][2] == 0) {
						flag = true;
					} else if (q[2] == 2 && station[0][2] == 3) {
						flag = true;
					} else if (q[2] == 3 && station[0][2] == 2) {
						flag = true;
					}
					if (flag)
						q[3]++;
					ans = Math.min(ans, q[3] + 1);

				}
				continue;
			}

			for (int d = 0; d < 4; d++) {
				for (int k = 1; k <= 3; k++) {
					int x = q[0] + (dx[d] * k);
					int y = q[1] + (dy[d] * k);

					boolean chk = false;
					if (isRange(x, y) && map[x][y] == 0) {
						int command = q[3];
						if (q[2] != d) {
							if (q[2] == 0 && d == 1)
								command += 2;
							else if (q[2] == 1 && d == 0)
								command += 2;
							else if (q[2] == 2 && d == 3)
								command += 2;
							else if (q[2] == 3 && d == 2)
								command += 2;
							else
								command++;
						}
						if (visited[d][x][y] != 0 && visited[d][x][y] <= command + 1)
							continue;
						if (command + 1 >= ans)
							break;
						
						queue.add(new int[] { x, y, d, command + 1 });
						visited[d][x][y] = command + 1;
						chk = true;
					}
					if (!chk)
						break;
				}
			}
		}
	}

	public static boolean isRange(int x, int y) {
		return x >= 0 && y >= 0 && x < N && y < M;
	}
}