[13901] 로봇

🔗 문제 링크

https://www.acmicpc.net/problem/13901

🔍 문제 설명

해빈이는 로봇을 좋아한다. 로봇을 가지고 놀던 해빈이는 로봇에게 계속해서 명령을 내려 움직이는 대신 이동할 방향을 미리 지정하여 로봇이 알아서 움직이도록 하였다. 이 로봇은 다음과 같은 규칙을 가지고 움직인다.

로봇은 사용자가 지정한 방향을 일직선으로 움직인다.
이동 중 벽이나 방문한 지역, 장애물을 만날 경우 로봇은 사용자가 지정한 다음 방향으로 움직인다.
사용자가 지정한 다음 방향이 없다면 맨 처음 방향으로 돌아가서 위의 과정을 반복한다.
로봇이 움직일 수 없을 경우 동작을 멈춘다.

입력으로 방의 크기와 장애물의 개수, 각 장애물들의 위치, 로봇의 시작 위치, 이동 방향의 순서가 주어졌을 때 로봇이 멈추는 위치를 출력하시오. 위치 (0, 0)은 왼쪽 위를 가리키며 방의 크기가 R * C일 때 오른쪽 아래 위치는 (R - 1, C - 1)이 된다. (R은 세로의 크기를 C은 가로의 크기를 말한다.)

⚠️ 제한사항

• 첫 번째 줄에는 방의 크기 R, C(3 ≤ R, C ≤ 1,000)가 입력된다

• 두 번째 줄에는 장애물의 개수 k(0 ≤ k ≤ 1,000)가 입력된다

• 다음 k개의 줄에는 각 장애물 위치 br(0 ≤ br ≤ R – 1), bc(0 ≤ bc ≤ C - 1)가 주어진다

• 그 다음 순서대로 로봇의 시작 위치 sr(0 ≤ sr ≤ R – 1), sc(0 ≤ sc ≤ C - 1)와 이동 방향의 순서(총 4개가 입력되는데 1은 위 방향, 2은 아래 방향, 3은 왼쪽 방향, 4는 오른쪽 방향을 나타낸다)가 한 줄씩 입력된다.

• 로봇의 시작위치에 장애물이 있는 경우는 없다.

---

🗝 풀이 (언어 : Java)

단순 구현으로 풀었다. DFS 방식으로 모든 방향에서 진행할 수 없을 때까지 탐색한다.

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

public class Main {

	private static final int[] dx = {-1, 1, 0, 0};
	private static final int[] dy = {0, 0, -1, 1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		int[][] matrix = new int[R][C];
		int K = Integer.parseInt(br.readLine()); //장애물 개수
		for (int i = 0; i < K; i++) {
			StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
			matrix[Integer.parseInt(st2.nextToken())][Integer.parseInt(st2.nextToken())] = -1;
		}
		StringTokenizer st3 = new StringTokenizer(br.readLine(), " ");
		int[] start = new int[] {Integer.parseInt(st3.nextToken()), Integer.parseInt(st3.nextToken())};
		StringTokenizer st4 = new StringTokenizer(br.readLine(), " ");
		int[] dir = new int[] {Integer.parseInt(st4.nextToken()) - 1, Integer.parseInt(st4.nextToken()) - 1,
			Integer.parseInt(st4.nextToken()) - 1, Integer.parseInt(st4.nextToken()) - 1};
		br.close();
		solution(matrix, start, dir);
	}

	private static void solution(int[][] matrix, int[] start, int[] dir) {
		boolean[][] visited = new boolean[matrix.length][matrix[0].length];
		dfs(matrix, visited, start, dir, 0);
	}

	private static void dfs(int[][] matrix, boolean[][] visited, int[] current, int[] dir, int dirIdx) {
		visited[current[0]][current[1]] = true; //방문 처리
		Integer nextDirIdx = getPossibleDirIdx(matrix, visited, current, dir, dirIdx);
		if (nextDirIdx == null) {
			System.out.println(current[0] + " " + current[1]);
			return;
		}
		dfs(matrix, visited, new int[] {current[0] + dx[dir[nextDirIdx]], current[1] + dy[dir[nextDirIdx]]}, dir, nextDirIdx);
	}

	private static Integer getPossibleDirIdx(int[][] matrix, boolean[][] visited, int[] current, int[] dir, int dirIdx) {
		int count = 0;
		while (true) {
			int x = current[0] + dx[dir[dirIdx]];
			int y = current[1] + dy[dir[dirIdx]];
			//현재 방향으로 진행 불가능한 경우 다음 방향 체크
			if (x < 0 || x >= matrix.length
				|| y < 0 || y >= matrix[0].length
				|| matrix[x][y] == -1 || visited[x][y]) {
				dirIdx = (dirIdx + 1) % 4;
				count++;
				if (count == 4) {
					return null;
				}
				continue;
			}
			return dirIdx;
		}
	}

}