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

문제 접근

$N \times M$ 크기의 격자판에서 로봇 청소기가 정해진 복잡한 규칙에 따라 이동하며 청소한 칸의 총 개수를 계산하는 문제이다.

이 문제의 경우 상태(위치, 방향)가 매 순간 변하며, 이 변화가 다음 행동을 결정하는 전형적인 시뮬레이션(Simulation) 문제로.이 문제의 핵심은

'문제 설명에 나온 4가지 행동 규칙을 어떻게 정확하게 코드로 구현하는가'이다.
1. 현재 칸 청소 (규칙 1)
2. 주변 4칸 탐색 (규칙 2, 3의 분기점)
3. 후진 또는 정지 (규칙 2)
3. 회전 및 전진 (규칙 3)

위와 같이 대부분의 시뮬레이션 문제들은 명확한 우선순위와 순서를 가지기 때문에 순서를 파악하고 순차적인 로직을 올바르게 구현하는 것이 포인트이다.

문제 조건

• 배열 크기: $3 \le N, M \le 50$ (배열의 최대 크기: $50 \times 50 = 2500$)
• 초기 상태
  • 청소기 위치: 2차원 배열 상의 (r, c) 좌표가 주어지며 해당 좌표는 항상 0이다.
  • 방향: 0: 북, 1: 동, 2: 남, 3: 서
  • 가장자리 조건: 가장자리는 벽으로 둘러쌓여 있음
• 규칙
  • 청소: 하나의 칸은 한번만 청소됨
  • 탐색 및 이동: 한 칸에서 4방향 탐색 후 회전/전진/후진 한다.
  • 회전: 반시계 방향으로 90도 회전한다.
  • 이동제약: 청소한칸은 다시 방문가능하며 벽은 이동이 불가능하다.
  • 종료조건: 후진 시 후진하는 지역이 벽으로 되어 있는 경우 종료한다.

문제 설계

전체 프로세스

입력 및 초기화

• N, M과 2차원 matrix배열에 방의 상태(0:빈칸, 1:벽)를 입력 받는다.
• 로봇의 초기상태 (r, c, d)를 입력받는다.
• 청소한 칸의 개수를 저장할 result변수를 0으로 초기화
• 방향 벡터 dr, dc를 정의

시뮬레이션 반복(while)

• 로봇이 작동을 멈출때(break)까지 다음 로직을 무한 반복
• 1. 현재 칸 청소: matrix[r][c] == 0일 경우 matrix[r][c]를 2로 변경하고 result를 1증가시킨다(result++, 2는 청소 완료를 의미)
• 2. 주변 4칸 탐색: isValid 플래그를 만들고 4방향을 탐색하여 matrix[nr][nc] == 0 (청소 가능)이 있는지 확인
• 3. 분기
  • if(!isValid): 청소할 칸이 없는 경우
    • 후진할 칸 (nr, nc)를 계산
    • matrix[nr][nc] == 1 (벽)이면 break로 루프를 탈출한다.(작동 중지)
    • 아닌경우 r = nr, c = nc로 후진하고 continue를 통해 초기로 돌아간다.
  • else: 청소할 칸이 있는 경우
    • d = (d + 3) % 4로 반시계 방향으로 90도 회전
    • 회전한 방향의 앞 칸 (nr, nc)를 계산
    • matrix[nr][nc] == 0이면 r = nr, c = nc로 전진 (전진 못해도 초기로 돌아감)

결과 출력

while문이 종료되면 result 값을 출력한다.

시간복잡도 분석

(총 반복횟수) x (1회 반복당 연산량)으로 계산

1. 1회 반복 당 연산량(while 루프 내부)

• 현재 칸 청소: if (matrix[r][c] == 0)...: $O(1)$
• 주변 4칸 탐색: for (int i = 0; i < 4; i++)...: $O(4)$, 즉 $O(1)$
• 분기 및 이동: 후진, 회전, 전진 모두 $O(1)$

2. 총 반복 횟수(while 실행 횟수)

최대 총 반복 횟수는 이차원 배열의 모든 (행, 열)을 방문했을 경우이다.
따라서 $N \times M$인 $O(N \times M) \times O(1) = O(N \times M)$이다.

3. 최종 시간 복잡도

• 총 시간 복잡도: (총 반복 횟수) x (1회 반복 당 연산량)
• $O(N \times M) \times O(1) = O(N \times M)$
• 문제의 제약 조건이 $N, M \le 50$ 이므로, $N \times M$은 최대 2500

구현 코드

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

public class gold5_14503_로봇청소기 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		// 0: 북 1:동 2:남 3:서
		int[] dr = { -1, 0, 1, 0 };
		int[] dc = { 0, 1, 0, -1 };

		st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());

		int[][] matrix = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		int result = 0;

		// 로봇 청소기 로직
		while (true) {
			int nr;
			int nc;
			// 현재칸 청소
			if (matrix[r][c] == 0) {
				matrix[r][c] = 2;
				result++;
			}

			// 청소구역 확인
			boolean isValid = false;

			// 4방향 탐색으로 청소해야될 구역이 있는지 확인
			for (int i = 0; i < 4; i++) {
				nr = r + dr[i];
				nc = c + dc[i];

				// 청소할 수 있는 구역이 있는 경우
				if (matrix[nr][nc] == 0) {
					isValid = true;
				}
			}

			// 청소 구역이 없는 경우
			if (!isValid) {
				// 후진이 가능한지 확인
				nr = r + dr[(d + 2) % 4];
				nc = c + dc[(d + 2) % 4];

				
				// 벽이 아니어야 함
				if (!(matrix[nr][nc] == 1)) {
					//  후진 후 처음으로 이동
					r = nr;
					c = nc;
					continue;
				}
				
				// 벽인 경우 작동 중지
				else {
					break;
				}
			}
			
			// 청소 구역이 있는 경우
			else {
				// 반시계 방향 회전
				d = (d + 3) % 4;
				
				nr = r + dr[d];
				nc = c + dc[d];
				
				// 바라보는 방향 기준 앞쪽 칸이 청소되지 않았으면 한칸 전진
				if (matrix[nr][nc] == 0) {
					r = nr;
					c = nc;
				}
			}
		}

		System.out.println(result);

	}
}