문제
N x M 격자에서 로봇 청소기가 주어진 규칙에 따라 이동하며 청소할 때, 청소한 칸의 총 개수를 구하라.
입력
첫째 줄에 N, M(3 ≤ N, M ≤ 50), 둘째 줄에 로봇 위치 (r, c)와 방향 d(0:북, 1:동, 2:남, 3:서), 셋째 줄부터 N줄에 격자 상태(0:빈칸, 1:벽)가 주어진다.
출력
로봇 청소기가 청소하는 칸의 개수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 3 1 1 0 1 1 1 1 0 1 1 1 1 | 1 |
풀이
로봇 청소기의 동작 규칙을 재귀 함수로 시뮬레이션한다.
- 현재 위치가 청소되지 않은 칸(0)이면 청소(2로 표시)하고 카운트를 증가시킨다
- 현재 방향에서 반시계 방향(왼쪽)으로 회전하며 4방향을 확인한다
- 청소되지 않은 빈 칸이 있으면 그 방향으로 전진하여 재귀 호출한다
- 4방향 모두 청소할 수 없으면 현재 방향을 유지한 채 후진한다
- 후진할 곳이 벽이면 작동을 멈춘다
핵심 아이디어: 방향 전환 시 (d+3)%4로 반시계 회전을 구현하고, 후진은 (d+2)%4 방향으로 이동하되 원래 방향을 유지한다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day68BOJ14503로봇청소기구현 {
static int N, M, ans;
static int[] dr = { -1, 0, 1, 0 }, dc = { 0, 1, 0, -1 };
static int[][] map;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
ans = 0;
st = new StringTokenizer(br.readLine());
int rdx = Integer.parseInt(st.nextToken());
int cdx = Integer.parseInt(st.nextToken());
int dir = Integer.parseInt(st.nextToken());
map = new int[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());
}
}
clean(rdx, cdx, dir);
System.out.println(ans);
br.close();
}
private static void clean(int r, int c, int d) {
if (map[r][c] == 0) {
map[r][c] = 2;
ans++;
}
boolean flag = false;
int tmp = d;// 원본 임시 저장, 후진용
for (int i = 0; i < 4; i++) {
int nd = (d + 3) % 4;
int nr = r + dr[nd];
int nc = c + dc[nd];
if (map[nr][nc] == 0) {
clean(nr, nc, nd);
flag = true;
break;
} // 왼쪽방향 우선 탐색 후 방향이 결정되면 해당방향으로 진행
d = (d + 3) % 4; // 조건문에서 반복이 종료되지 않으면, 방향변경
}
// 다음 방향을 잡지 못하고, 4회 왼쪽으로 돌고 종료되었으면
if (!flag) {
int nd = (tmp + 2) % 4;
int nr = r + dr[nd];
int nc = c + dc[nd];
if (map[nr][nc] != 1)
clean(nr, nc, tmp);
}
}
}복잡도
- 시간: O(N * M)
- 공간: O(N * M)