문제 링크👉🏻 https://www.acmicpc.net/problem/14503
👀 문제 접근
로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수 구하기
테두리가 벽으로 둘러싸여 있는 n * m 크기의 방을 청소한다.
청소기는 바라보는 방향이 있으며, 이 방향은 동(1), 서(3), 남(2), 북(0) 중 하나이다.
첫 줄에 n 과 m 을 입력하고, 두 번째 줄에는 청소기의 시작 위치와 방향을, 그 다음 줄부터는 방의 상태를 입력한다.
로봇 청소기는 다음과 같이 작동한다.
-
현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
→ 청소 여부를 확인 후, 청소가 돼 있지 않으면 해당 좌표의 map 값을 2로 변경한다.
여기서 2는 청소 완료했음을 나타내기위해 내가 임의로 정한 값이다.
-
현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
→ 먼저 4방향 좌표를 순회하면서 청소가 전부 돼 있는지 확인 한다.
- 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
- 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
-
현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
- 반시계 방향으로 90°회전한다.
- 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
- 1번으로 돌아간다.
🔎 해결 방식
해결 방식으로 가장 먼저 떠오른 것은 BFS로 접근하여 문제 요구사항을 충족하는 코드를 작성하는 것이었다.
BFS를 활용해 문제를 어떻게 해결해 나갈 것인지 고려한다.
이 문제의 핵심은 방향과 자표 이동이다. 문제에서 전진을 하는 경우, 후진을 하는 경우가 있기 때문에 각 방향마다 전진, 후진일 경우 좌표를 어디로 이동시켜야 할지에 대한 고민이 필요했다.
map[x][y]라 할 때
- 방향이 북쪽일 때(⬆️)
- 방향이 0일 경우, 북쪽을 향한다. ⇒ 배열 인덱스 0에 북쪽 좌표 이동 값을 저장한다.
- 북쪽 전진은 x를 -1한 값이다.
- 북쪽 후진은 x를 +1한 값이다.
- 방향이 동쪽일 때(➡️)
- 방향이 1일 경우, 동쪽을 향한다. ⇒ 배열 인덱스 1에 동쪽 좌표 이동 값을 저장한다.
- 동쪽 전진은 y를 +1한 값이다.
- 동쪽 후진은 y를 -1한 값이다.
- 방향이 남쪽일 때(⬇️)
- 방향이 2일 경우, 남쪽을 향한다. ⇒ 배열 인덱스 2에 남쪽 좌표 이동 값을 저장한다.
- 남쪽 전진은 x를 +1한 값이다.
- 남쪽 후진은 x를 -1한 값이다.
- 방향이 서쪽일 때(⬅️)
- 방향이 3일 경우, 서쪽을 향한다. ⇒ 배열 인덱스 3에 서쪽 좌표 이동 값을 저장한다.
- 서쪽 전진은 y를 -1한 값이다.
- 서쪽 후진은 y를 +1한 값이다.
정리한 것을 토대로 전진X, 전진Y, 후진X, 후진Y의 배열값을 어떻게 저장할지 생각해보면,
전진X = {-1, 0, 1, 0} 전진Y = {0, 1, 0, -1}
후진X = {1, 0, -1, 0} 후진Y = {0, -1, 0, 1} 이렇게 된다.
주변 4칸이 모두 청소 돼 있는 경우
- 후진 가능
- 현재 방향에서 후진할 수 있으면 후진한다.
q.offer(new int[]{현재방향, 현재 X + 후진X[현재방향], 현재Y + 후진Y[현재방향]})
- 후진 불가
- 현재 방향에서 후진하면 벽인 경우
count를 리턴한다.
주변 4칸 중 청소되지 않은 곳이 있는 경우
- 반시계 방향으로 90°회전
다음방향 = (현재 방향 + 3) % 4- 방향에서 전진할 경우 청소되지 않은 방일 때
q.offer(new int[] {다음방향, 현재X + 전진X[다음방향], 현재Y + 전진Y[다음방향]})
- 방향에서 전진할 경우 청소되지 않은 방일 때
q.offer(new int[] {다음방향, 현재X, 현재Y})
💻 구현 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
private final int[] goX = {-1, 0, 1, 0};
private final int[] goY = {0, 1, 0, -1};
private final int[] backX = {1, 0, -1, 0};
private final int[] backY = {0, -1, 0, 1};
private int n;
private int m;
private int[][] map;
private Queue<int[]> q;
public Main(int n, int m) {
this.n = n;
this.m = m;
map = new int[n][m];
q = new LinkedList<>();
}
public void initMap(int[][] map) { this.map = map; }
public boolean isFullCleanedUp(int[] curr) {
int count = 0;
for(int i = 0; i < 4; i++) {
int nx = curr[1] + goX[i];
int ny = curr[2] + goY[i];
if(map[nx][ny] != 0) count++;
}
if(count == 4) return true;
return false;
}
public int cleanUp(int x, int y, int d) {
q.offer(new int[]{d, x, y});
int count = 0;
while(!q.isEmpty()) {
int[] curr = q.poll();
if(map[curr[1]][curr[2]] == 0) {
map[curr[1]][curr[2]] = 2;
count++;
}
if(isFullCleanedUp(curr)) {
int nextX = curr[1] + backX[curr[0]];
int nextY = curr[2] + backY[curr[0]];
if(map[nextX][nextY] == 1) return count;
q.offer(new int[]{curr[0], nextX, nextY});
continue;
}
int nextDir = (curr[0] + 3) % 4;
int nextX = curr[1] + goX[nextDir];
int nextY = curr[2] + goY[nextDir];
if(map[nextX][nextY] == 0) {
q.offer(new int[]{nextDir, nextX, nextY});
continue;
}
q.offer(new int[]{nextDir, curr[1], curr[2]});
}
return count;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int n = Integer.parseInt(input[0]);
int m = Integer.parseInt(input[1]);
Main main = new Main(n, m);
input = br.readLine().split(" ");
int x = Integer.parseInt(input[0]);
int y = Integer.parseInt(input[1]);
int d = Integer.parseInt(input[2]);
int[][] map = new int[n][m];
for(int i = 0; i < n; i++) {
input = br.readLine().split(" ");
for(int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(input[j]);
}
}
main.initMap(map);
int answer = main.cleanUp(x, y, d);
System.out.println(answer);
}
}✨ 마무리
문제 풀이를 시작할 때 전진하는 경우는 생각하지 않고 후진하는 경우만 고려한채로 진행했다. 문제를 꼼꼼히 읽지 않고 풀이를 진행하다보니 내 풀이에 어떤 문제가 있는지 확인하는데 꽤 오랜 시간이 걸렸다.
문제를 다시 읽으며 후진하는 경우까지도 고려해야 하는 것을 알아냈고, 문제점을 찾아내니 금방 정답을 도출해낼 수 있었다.
