[백준] 14503 로봇 청소기

문제 출처: https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

 

1. 입력

: 첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 50)

: 둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다.

: d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.

: 셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다.

: 빈 칸은 0, : 벽은 1로 주어진다.

: 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.

: 로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.

 

2. 출력

: 로봇 청소기가 청소하는 칸의 개수를 출력한다.

 

3. 풀이

: 로봇 청소기가 돌아다닐 맵과 청소를 한 자리를 표시해줄 방문배열을 만든다.

: 규칙에 따라 이동할 수 있도록 한다.

: 이때, 주어진 숫자에 따른 방향은 숫자가 증가하면 오른쪽으로 회전하기 때문에 왼쪽으로 회전하기 위해서는 (기존방향+3)%4를 해주어야 한다.

: 또한 지도의 첫 행, 마지막 행, 첫 열, 마지막 열을 이미 벽으로 주어지기 때문에 따로 범위체크를 할 필요가 없다.

 

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

public class 로봇청소기 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int N, M;
	static boolean[][] v;
	static int[][] map;

	static class Point {
		int r, c, d;

		public Point(int r, int c, int d) {
			super();
			this.r = r;
			this.c = c;
			this.d = d;
		}

	}

	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N][M];
		v = new boolean[N][M];
		st = new StringTokenizer(br.readLine());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());

		Point robot = new Point(r, c, d);

		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());
			}
		}
		int cnt = 1;
		v[robot.r][robot.c] = true;
		out: while (true) {
			int nd = robot.d;
			int nr = robot.r;
			int nc = robot.c;
			for (int i = 0; i < 4; i++) {
				nd = (nd + 3) % 4;
				nr = robot.r + dr[nd];
				nc = robot.c + dc[nd];
				if (map[nr][nc] == 1 || v[nr][nc])
					continue;
				robot.r = nr;
				robot.c = nc;
				robot.d = nd;
				v[robot.r][robot.c] = true;
				cnt++;
				continue out;
			}

			robot.r -= dr[robot.d];
			robot.c -= dc[robot.d];
	
			if (map[robot.r][robot.c] == 1)
				break out;

		}

		System.out.println(cnt);

	}
}