[Baekjoon] 15426_GlitchBot

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

---

< GlitchBot >

 

문제 풀이 

 

모든 명령어를 수정해 보면서 목표 목적지에 도달할 때를 구한다.

 

my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class _15426_ { // GlitchBot
	static int dx[] = { 1, 0, -1, 0 };
	static int dy[] = { 0, 1, 0, -1 };
	static int x, y;
	static boolean flag;

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

		y = Integer.parseInt(st.nextToken());
		x = Integer.parseInt(st.nextToken());

		int n = Integer.parseInt(bf.readLine());

		String arr[] = new String[n];
		for (int i = 0; i < n; i++) {
			arr[i] = bf.readLine();
		}

		flag = false;
		for (int i = 0; i < n; i++) {
			search(arr, i, 0, 0, 0, 0, "");
		}
	}

	private static void search(String[] arr, int i, int a, int b, int dir, int idx, String cmd) {
		if (flag) {
			return;
		}
		if (idx == arr.length) {
			if (a == x && y == b) {
				flag = true;
				System.out.println((i + 1) + " " + cmd);
			}
			return;
		}
		if (i == idx) {
			if (arr[i].equals("Left")) {
				search(arr, i, a, b, (dir + 1) > 3 ? 0 : dir + 1, idx + 1, "Right"); // right
				search(arr, i, a + dx[dir], b + dy[dir], dir, idx + 1, "Forward"); // forward
			} else if (arr[i].equals("Right")) {
				search(arr, i, a, b, (dir - 1) < 0 ? 3 : dir - 1, idx + 1, "Left"); // left
				search(arr, i, a + dx[dir], b + dy[dir], dir, idx + 1, "Forward"); // forward
			} else {
				search(arr, i, a, b, (dir + 1) > 3 ? 0 : dir + 1, idx + 1, "Right"); // right
				search(arr, i, a, b, (dir - 1) < 0 ? 3 : dir - 1, idx + 1, "Left"); // left
			}
		} else {
			if (arr[idx].equals("Left")) {
				search(arr, i, a, b, (dir - 1) < 0 ? 3 : dir - 1, idx + 1, cmd); // left
			} else if (arr[idx].equals("Right")) {
				search(arr, i, a, b, (dir + 1) > 3 ? 0 : dir + 1, idx + 1, cmd); // right
			} else {
				search(arr, i, a + dx[dir], b + dy[dir], dir, idx + 1, cmd); // forward
			}
		}
	}
}

변수)
dx, dy : 상, 우, 하, 좌
x, y : 목적지
flag : 목적지 도달 여부
n : 명령어 수
arr : 명령어

 

목적지와 명령어 수, 명령어를 입력받는다. 명령어를 탐색하며 search 함수를 호출한다.

 

search(명령어 배열, 수정 번호, 현재 위치, 방향, 현재 명령어 번호, 수정 사항)

1) 수정을 통해 목적지에 도달했다면 종료한다. 

2) 모든 명령어를 수행했다면 목적지에 도달했는지 확인 후 종료한다. 목적지에 도달했다면 수정하는 번호와 수정 사항을 출력한다.

3) 수정 번호와 현재 명령어 번호가 일치하다면 현재 명령어와 다른 명령어를 수행하며 search 함수를 호출한다.

4) 수정 번호와 현재 명령어 번호가 일치하지 않다면 현재 명령어를 수행하며 search 함수를 호출한다.

---

---