[백준/자바] 14503번: 로봇 청소기

문제

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

풀이

• 로봇 청소기가 있는 방은 $N \times M$ 크기
• $1 \times 1$ 크기의 정사각형 칸으로 나누어져 있다.
  • 각각의 칸은 벽 또는 빈 칸이다.
• 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다.
• 방의 각 칸은 좌표 $(r, c)$로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 $(0, 0)$, 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 $(N-1, M-1)$이다.
• 처음에 빈 칸은 전부 청소되지 않은 상태이다.
• 로봇 청소기는 다음과 같이 작동한다.

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우

• 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
• 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.

3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우

• 반시계 방향으로 $90^\circ$ 회전한다.
• 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
• 1번으로 돌아간다.

단순 구현, 시뮬레이션 문제입니다.
위처럼 요구하는 것이 좀 있을 때에는 내가 구현해야할 내용을 정리해 가면서 풀면, 쉽게 해결할 수 있습니다.

클래스 선언

	static class Pos {
		int r, c, d;
		
		public Pos (int r, int c, int d) {
			this.r = r; // r
			this.c = c; // c
			this.d = d; // 바라보고 있는 방향
		}
	}

• 로봇 청소기의 현재 위치를 관리하기 위해 클래스를 선언했습니다.

입력

	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()); // 세로
		
		st = new StringTokenizer(br.readLine());
		sr = Integer.parseInt(st.nextToken()); // 시작 r좌표
		sc = Integer.parseInt(st.nextToken()); // 시작 c 좌표
		sd = Integer.parseInt(st.nextToken()); // 시작 방향
		
		p = new Pos(sr, sc, sd); // 시작 상태 선언
		
        // 지도 초기화
		map = new int[n][m];
		visited = new boolean[n][m];
		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());
			}
		}

• 로봇 청소기의 현재 상태를 관리하기 쉽게 하기 위해, 전역 변수로 선언하였습니다.

시뮬레이션

	private static void action() {
		while (true) {
			// 현재 칸이 청소되지 않은 경우, 현재 칸을 청소한다.
			if (!visited[p.r][p.c]) {
				visited[p.r][p.c] = true;
				++cnt; // 청소한 칸 개수
			}

			// 현재 칸의 주변 4칸 탐색
			boolean isDirty = false;
			for (int i = 0; i < 4; i++) {
				int nr = p.r + dr[i];
				int nc = p.c + dc[i];

				if (!isIn(nr, nc)) continue;
				
				if (!visited[nr][nc] && map[nr][nc] == 0) {
					isDirty = true;
					break;
				}
			}

• 문제의 조건을 보면 주변 4칸을 탐색 후, 주변에 더러운 칸이 있냐 없냐에 따라 실행해야 하는 조건이 다릅니다.
• 이 점을 이용해서 주변 4칸을 탐색해서 더러운 곳이 있는지, 없는지부터 판별해 줍니다.

			// 주변 4칸 중 더러운 칸이 없는 경우
			if (!isDirty) {
				// 바라보는 방향을 유지한 채로 한 칸 후진
				int nr = p.r - dr[p.d];
				int nc = p.c - dc[p.d];
				
				// 뒤쪽 칸이 벽 or 범위 밖이라 후진할 수 없다면 작동을 멈춘다.
				if (!isIn(nr, nc) || map[nr][nc] == 1) break;
				
				p.r = nr;
				p.c = nc;
			} 

• 인접한 칸 중에 더러운 칸이 없는 경우
• 뒤로 후진
• 뒤로 이동할 수 없으면 종료
• 아니라면 후진한 값을 업데이트해 줍니다.

			// 주변 4칸 중 더러운 칸이 있는 경우 
			else {
				// 반시계 방향으로 90도 회전
				p.d = (p.d + 3) % 4;
				
				// 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진
				int nr = p.r + dr[p.d];
				int nc = p.c + dc[p.d];
				
				if (isIn(nr, nc) && map[nr][nc] == 0 && !visited[nr][nc]) {
					p.r = nr;
					p.c = nc;
				}
			}

• 인접한 칸 중에 더러운 칸이 있는 경우
• 반시계 방향으로 90도 회전해 줍니다.
• 바라보는 방향 기준 앞 칸이 청소되지 않았다면 전진
• 아니라면 아무 행동도 하지 않고 다시 1번으로 돌아갑니다.

출력

		cnt = 0;
		action();
		
		System.out.println(cnt);

• 결국 후진을 못하게 되므로, 종료가 됩니다.
• 그렇게 되면 업데이트된 cnt 값을 출력하면 끝입니다.

생각보다 복잡해 보일 수 있지만, 문제에서 요구하는 것들을 하나씩 써내려 가면서 코드를 작성하면 쉽게 해결할 수 있습니다 😏

코드

import java.util.*;
import java.io.*;

public class Main_14503 {
	
	static class Pos {
		int r, c, d;
		
		public Pos (int r, int c, int d) {
			this.r = r;
			this.c = c;
			this.d = d;
		}
	}
	
	static StringBuilder sb = new StringBuilder();
	static int n, m, cnt;
	static int sr, sc, sd;
	static int[][] map;
	static boolean[][] visited;
	
	static Pos p;
	
	static final int[] dr = { -1, 0, 1, 0 };
	static final int[] dc = { 0, 1, 0, -1 };
	
	private static void action() {
		while (true) {
			// 현재 칸이 청소되지 않은 경우, 현재 칸을 청소한다.
			if (!visited[p.r][p.c]) {
				visited[p.r][p.c] = true;
				++cnt;
			}

			// 현재 칸의 주변 4칸 탐색
			boolean isDirty = false;
			for (int i = 0; i < 4; i++) {
				int nr = p.r + dr[i];
				int nc = p.c + dc[i];

				if (!isIn(nr, nc)) continue;
				
				if (!visited[nr][nc] && map[nr][nc] == 0) {
					isDirty = true;
					break;
				}
			}
			
			// 주변 4칸 중 더러운 칸이 없는 경우
			if (!isDirty) {
				// 바라보는 방향을 유지한 채로 한 칸 후진
				int nr = p.r - dr[p.d];
				int nc = p.c - dc[p.d];
				
				// 뒤쪽 칸이 벽 or 범위 밖이라 후진할 수 없다면 작동을 멈춘다.
				if (!isIn(nr, nc) || map[nr][nc] == 1) break;
				
				p.r = nr;
				p.c = nc;
			} 
			// 주변 4칸 중 더러운 칸이 있는 경우 
			else {
				// 반시계 방향으로 90도 회전
				p.d = (p.d + 3) % 4;
				
				// 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진
				int nr = p.r + dr[p.d];
				int nc = p.c + dc[p.d];
				
				if (isIn(nr, nc) && map[nr][nc] == 0 && !visited[nr][nc]) {
					p.r = nr;
					p.c = nc;
				}
			}
		}
	}
	
	private static boolean isIn(int r, int c) {
		return 0 <= r && r < n && 0 <= c && c < m ;
	}
	
	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());
		
		st = new StringTokenizer(br.readLine());
		sr = Integer.parseInt(st.nextToken());
		sc = Integer.parseInt(st.nextToken());
		sd = Integer.parseInt(st.nextToken());
		
		p = new Pos(sr, sc, sd);
		
		map = new int[n][m];
		visited = new boolean[n][m];
		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());
			}
		}
		
		cnt = 0;
		action();
		
		System.out.println(cnt);
	}

}