[Baekjoon] 1726_로봇

Gold III

문제(출처: https://www.acmicpc.net/problem/1726)

---

< 로봇 >

 

문제 풀이 

 

먼저 현재 위치에서 동서남북으로 이동해 본다. 한 번 이동할 때 최대 3칸 이동할 수 있으므로 1칸, 2칸, 3칸을 이동시켜 본다. 중간에 1이 있으면 이동할 수 없다는 것을 고려해야 한다. 

 

만약 동서남북으로 이동 가능하다면 현재 방향에서 이동 가능한 방향으로 바꿔줘야 하므로 명령의 횟수를 구해준다.

이때, 방향 번호로만 명령의 수를 구할 경우 동에서 북으로 가는 경우 2번으로 구해지지만 실제로는 1번인 것을 고려해야 한다.

 

이동한 곳이 최종 원하는 위치라면 원하는 방향으로 바라보도록 계산해주어야 한다. 최소 명령 횟수라는 보장이 없으므로 중간에 그만두지 않고 전체 다 계산 후 최솟값을 찾아준다.

 

이동한 곳이 최종 원하는 위치가 아니라면 그 위치에 방문한 적이 있는지 확인한다. 방문을 한 적이 없거나, 방문을 했었지만 명령의 횟수가 그때보다 적다면 queue에 추가해 준다. 

 

 my solution (Java)

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 _1726_ { // 로봇
	static int arr[][], visited[][], m, n, x2, y2, dir2;
	static int dx[] = { 0, 0, 1, -1 };
	static int dy[] = { 1, -1, 0, 0 };

	public static class Robot {
		int x, y, dir, depth;

		public Robot(int x, int y, int dir, int depth) {
			this.x = x;
			this.y = y;
			this.dir = dir;
			this.depth = depth;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());

		arr = new int[m][n];
		visited = new int[m][n];

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < n; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				visited[i][j] = -1;
			}
		}

		st = new StringTokenizer(bf.readLine());
		int x1 = Integer.parseInt(st.nextToken()) - 1;
		int y1 = Integer.parseInt(st.nextToken()) - 1;
		int dir1 = Integer.parseInt(st.nextToken()) - 1;

		st = new StringTokenizer(bf.readLine());
		x2 = Integer.parseInt(st.nextToken()) - 1;
		y2 = Integer.parseInt(st.nextToken()) - 1;
		dir2 = Integer.parseInt(st.nextToken()) - 1;

		int result = 0;

		if (x1 == x2 && y1 == y2) {
			result = dirCalc(dir2, dir1, 0);
		} else {
			result = bfs(x1, y1, dir1);
		}

		System.out.println(result);
	}

	private static int bfs(int a, int b, int dir) {
		Queue<Robot> queue = new LinkedList<>();
		queue.add(new Robot(a, b, dir, 0));
		visited[a][b] = 0;
		boolean flag = false;
		int cnt = -1;

		while (!queue.isEmpty()) {
			Robot robot = queue.poll();
			for (int i = 0; i < 4; i++) {
				flag = false;
				for (int j = 1; j <= 3; j++) {
					int x = robot.x + (dx[i] * j);
					int y = robot.y + (dy[i] * j);
					if (x >= 0 && x < m && y >= 0 && y < n && arr[x][y] == 0) {
						flag = true;
						int depth = dirCalc(robot.dir, i, robot.depth);
						Robot newRobot = new Robot(x, y, i, depth + 1);
						if (x == x2 && y == y2) {
							depth = dirCalc(dir2, i, depth) + 1;
							if (cnt == -1 || cnt > depth) {
								cnt = depth;
							}
						}
						if (visited[x][y] == -1 || visited[x][y] > newRobot.depth) {
							visited[x][y] = newRobot.depth;
							queue.add(newRobot);
						}
					} else {
						flag = false;
					}
					if (!flag)
						break;
				}
			}
		}
		return cnt;
	}

	public static int dirCalc(int x, int y, int depth) {
		if ((x == 2 && y == 3) || (x == 3 && y == 2) || (x == 1 && y == 0) || (x == 0 && y == 1)) {
			depth += 2;
		} else if (x != y) {
			depth += 1;
		}
		return depth;
	}
}

 

Main

변수)
m, n : 세로, 가로길이
arr : 궤도 설치 상태
visited : 방문했을 때의 명령 횟수
x1, y1, dir1 : 현재 위치, 방향
x2, y2, dir2 : 원하는 위치, 방향
result : 최소 명령 횟수

 

- 세로 길이(m), 가로길이(n) 입력

- 궤도 설치 상태 입력 후 저장(arr) 및 방문했을 때의 명령 횟수를 저장하는 visited 배열 -1로 초기화

- 현재 위치와 방향, 원하는 위치와 방향 입력

- 현재 위치와 원하는 위치가 일치하다면 방향만 계산/ 일치하지 않다면 bfs 함수 호출

- 최소 명령 횟수(result) 출력

 

bfs

-  Queue에 Robot <x 위치, y 위치, 방향, 명령 횟수> 저장

- 시작 위치의 명령 횟수는 0이므로 visited에 0으로 저장

- queue가 빌 때까지 반복

: 동서남북으로 이동 -> 1칸, 2칸, 3칸 이동 -> 범위 안이며, 궤도가 깔려있다면

: dirCalc 호출하여 그 방향으로 이동하기 위한 명령 수 계산

: Robot 객체 만든 후 아직 방문하지 않았거나, 방문을 했지만 명령 수가 더 적다면 queue에 추가

: 만약 로봇이 원하는 위치에 도달했다면 방향을 일치시키기 위해 dirCalc 호출하여 명령 수 계산 후 최솟값으로 값 update

: 만약 2칸 이동을 못하면 3칸도 이동 못하므로 flag를 이용하여 판단

- cnt 반환

 

dirCalc

- (동-서), (남-북) 방향으로 바꾸기 위해 명령+2 반환, 나머지는 명령+1 반환

 

 

---

---