문제 링크
https://www.acmicpc.net/problem/14503
풀이
청소기가 더 이상 움직일 수 없는 조건은 주변 칸이 전부 청소된 상태이고, 후진할 수 없는 경우이다.
while문을 실행하여 더 이상 움직일 수 없는 경우에 대해서 -1 값으로 처리했다.
move 함수는 로봇 청소기가 r, c, d값에 따라 한번 움직이는 함수이다. return값는 각 상황에 따른 새롭게 이동해야 하는 위치와 좌표가 반환된다.
move 함수에서 문제의 조건대로 함수를 실행한다.
개선할 점은 청소할 영역이 한가지만 남았는데, 로봇청소기가 해당 방향을 발견할때까지 뱅뱅 도는 경우이다
로봇 청소기가 *에 있을 때 0인 곳으로만 이동할 수 있는데 저 방향을 발견할때까지 계속 도는 경우가 있다.
어차피 청소하는 칸의 개수만 구하는 것이기 때문에 move 함수를 계속 실행시키는 것이 아니라 한 방향으로만 가야한다면 해당 방향을 바로 갈 수 있도록 return 값을 수정하는 것이 더 효율적인 코드라고 생각된다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_14503_로봇청소기 {
static int N, M, res, map[][];
static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; //북 동 남 서
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokens = new StringTokenizer(br.readLine());
N = Integer.parseInt(tokens.nextToken());
M = Integer.parseInt(tokens.nextToken());
map = new int[N][M];
tokens = new StringTokenizer(br.readLine());
//처음 위치와 방향
int r = Integer.parseInt(tokens.nextToken());
int c = Integer.parseInt(tokens.nextToken());
int d = Integer.parseInt(tokens.nextToken());
for (int i = 0; i < N; i++) {
tokens = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
//0 청소되지 않은 칸, 1 벽
map[i][j] = Integer.parseInt(tokens.nextToken());
}
}
res = 0;
while (r != -1 && c != -1 && d != -1) {
int[] temp = move(r, c, d);
r = temp[0];
c = temp[1];
d = temp[2];
}
System.out.println(res);
}
private static int[] move(int r, int c, int d) {
//현재 칸 확인
if (checkNowArea(r, c)) {
//청소되지 않았다면 청소
res++;
map[r][c] = -1; //청소되었다고 표시
}
//주변 4칸 확인
if (checkAroundArea(r, c)) {//다 청소된 경우
//후진 가능한지 확인
int[] temp = isBack(r, c, d);
//후진 가능하다면 후진, 후진 불가능이면 작동 멈춤
if (r == temp[0] && c == temp[1] && d == temp[2]) {
//후진 불가능한 경우 멈춤
return new int[]{-1, -1, -1};
}
//후진 가능한 경우
return new int[]{temp[0], temp[1], temp[2]};
} else {//청소되지 않은 칸이 있는 경우
//방향 반시계로 90도 회전 -> 3 더하고 모듈러
d = (d + 3) % 4;
//앞쪽 칸이 청소되지 않은 빈칸이면 전진하고 다시 움직임
int nx = r + dir[d][0];
int ny = c + dir[d][1];
if (isRange(nx, ny) && map[nx][ny] == 0) {//청소되지 않은 칸인 경우
return new int[]{nx, ny, d}; //한칸 전진
}
//그냥 방향만 바꾸고 제자리
return new int[]{r, c, d};
}
}
private static int[] isBack(int r, int c, int d) {
//현재 위치에서 후진 할 수 있는지 확인
//현재 방향의 반대 방향 선택. 2를 더하고 모듈러
int nd = (d + 2) % 4;
int nx = r + dir[nd][0];
int ny = c + dir[nd][1];
//뒤로 갈 수 있고, 벽이 아닌 경우
if (isRange(nx, ny) && map[nx][ny] != 1) return new int[]{nx, ny, d};
return new int[]{r, c, d};
}
private static boolean checkAroundArea(int r, int c) {
//주변에 0이 없다면 true
for (int d = 0; d < 4; d++) {
int nx = r + dir[d][0];
int ny = c + dir[d][1];
if (isRange(nx, ny) && map[nx][ny] == 0)
return false;
}
return true;
}
private static boolean isRange(int x, int y) {
if (x < 0 || y < 0 || x >= N || y >= M) return false;
return true;
}
private static boolean checkNowArea(int r, int c) {
if (map[r][c] == 0) return true; //청소되지 않은 칸이라면 true
return false;
}
}