1. 문제 설명
로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램으로,
로봇 청소기가 있는 방은 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r,c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0,0), 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N-1, M-1)이다. 즉, 좌표 (r, c)는 북쪽에서 (r+1)번째에 있는 줄의 서쪽에서 (c+1)번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.
로봇 청소기는 다음과 같이 작동한다.
현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
반시계 방향으로 90도 회전한다.
바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
1번으로 돌아간다.
2. 입력
첫째 줄에 방의 크기 N과 M이 주어진다. (3 ≤ N, M ≤ 50)
둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다.
( d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다. )
셋째 줄부터 N개의 줄에 각 장소의 상태를 나타내는 N x M개의 값이 한 줄에 M개씩 입력된다.
청소가 되지 않은 빈 칸은 0, 벽은 1로 주어진다.
방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다.
로봇 청소기가 있는 칸은 항상 빈 칸이다.
3. 출력
로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.
4. 문제 풀이
처음에 이 문제를 제대로 이해하지 못 했을 때는 bfs로 해서 그냥 쭉 살펴보고 청소되지 않은 빈칸이 없을 때 후진하면 되지 않나? 라고 생각했었는데 이는 완전 잘못된 이해였기에 실패하였다. 그냥 bfs 를 돌리면 모든 연결된 곳을 돌아버리기 때문에 벽으로 막혀있지 않는 한 모든 0을 채워버린다.
그래서 이는 bfs가 아닌 dfs로 방향을 중시하면서 가야한다는 것이였다.
즉 이 규칙이 첫번째 keyPoint 였지만 제대로 이해하지 못했었던 것이다.
현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
반시계 방향으로 90도 회전한다.
바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
1번으로 돌아간다.
현재의 방향을 기준으로 반시계 방향으로 90도씩 회전하면서 청소되지 않은 빈칸을 찾아야한다는 것을 기억해야한다. 그리고 두번째 keyPoint는 주변 모든 4칸을 전부 청소할 수 없을 경우 후진하는데 이 후진의 기준은 현재 로봇청소기가 바라보고 있는 방향이며 그 후진한 곳이 벽이라면 작동을 멈춰야한다는 것이다.
이 2가지의 keyPoint를 잘 기억하고 코드에 녹이면 되는 문제였다.
5. 코드
//백준 - 로봇청소기
//dfs
//정해진 방향과
//후진관련
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class exam02_1 {
static class Robot{
int x;
int y;
public Robot(int x, int y) {
this.x = x;
this.y = y;
}
}
final static int[][] dirs = {{-1,0},{0,1},{1,0},{0,-1}};
static int[][] room;
static int clean,N,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());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int dir = Integer.parseInt(st.nextToken());
room = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
room[i][j] = Integer.parseInt(st.nextToken());
}
}
clean = 1;
dfs(x,y,dir);
System.out.println(clean);
System.out.println(Arrays.deepToString(room));
}
private static void dfs(int x, int y, int direction) {
room[x][y] = -1;
for (int i = 0; i < 4; i++) {
direction = (direction+3) % 4;
int nx = x + dirs[direction][0];
int ny = y + dirs[direction][1];
//방의 범위를 벗어나는 경우
if(nx < 0 || nx >= N || ny < 0 || ny >= M ){
continue;
}
//청소되지 않은 빈칸이 아닌 경우
if(room[nx][ny] != 0){
continue;
}
clean++;
dfs(nx,ny,direction);
//여기에서 리턴을 해주어야 밑의 후진 로직을 타지 않는다.
return;
}
//네 방향 모두 청소되지 않은 빈칸이 아닌 경우
//바라보는 방향을 그대로 유지한 채로 한 칸 후진한다.
int back = (direction+2) % 4;
int bx = x + dirs[back][0];
int by = y + dirs[back][1];
//후진이 가능할 경우 후진한 포지션을 기준으로 dfs
if(bx >= 0 && bx < N && by >= 0 && by < M && room[bx][by] != 1 ){
dfs(bx,by,direction);
}
//후진한 위치에 벽이 있었다면 그대로 끝나게 된다.
}
}