문제 설명
로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
로봇 청소기가 있는 방은 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r,c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0,0), 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N−1,M−1)이다. 즉, 좌표 (r,c)는 북쪽에서 (r+1)번째에 있는 줄의 서쪽에서 (c+1)번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.
로봇 청소기는 다음과 같이 작동한다.
- 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
- 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
- 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
- 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
- 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
- 반시계 방향으로 90도 회전한다.
- 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
- 1번으로 돌아간다.
입력
첫째 줄에 방의 크기 𝑁과 𝑀이 입력된다. (3≤𝑁,𝑀≤50) 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 (𝑟,𝑐)와 처음에 로봇 청소기가 바라보는 방향 𝑑가 입력된다. 𝑑가 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽을 바라보고 있는 것이다.
셋째 줄부터 N𝑁개의 줄에 각 장소의 상태를 나타내는 𝑁×𝑀개의 값이 한 줄에 𝑀개씩 입력된다. 𝑖번째 줄의 𝑗번째 값은 칸 (𝑖,𝑗)의 상태를 나타내며, 이 값이 0인 경우 (𝑖,𝑗)가 청소되지 않은 빈 칸이고, 1인 경우 (𝑖,𝑗)에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.
출력
로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.
나의 경우 동 서 남 북 방향의 좌표를 확인하기 위해 dx dy 테크닉을 사용했는데, 좌표가 (행, 열)형식, 즉 ( y, x ) 형태로 사용된다는 것을 잊고 dx, dy를 그대로 사용했다가 고생한 경험이 있다. 이런 실수를 하지 않도록 확실히 확인 하는 버릇을 들여야 될 것 같았다.
풀이
입력
- 방의 크기와 로봇 청소기가 있는 칸의 좌표, 방향을 입력.
// 첫 번째 줄 처리
String[] firstLine = br.readLine().split(" ");
N = Integer.parseInt(firstLine[0]);
M = Integer.parseInt(firstLine[1]);
// 두 번째 줄 처리
String[] secondLine = br.readLine().split(" ");
r = Integer.parseInt(secondLine[0]);
c = Integer.parseInt(secondLine[1]);
d = Integer.parseInt(secondLine[2]);
A = new int[N][M];
visited = new boolean[N][M];로봇청소기 청소
- isDirection으로 동 서 남 북 방향 구분, Queue에 현재 좌표를 넣고 queue가 비워질 때까지 반복
- 현재좌표의 청소 여부와 벽 (
1)이 아닌지 확인- 청소하지 않은 곳이라면 표시하고 count++
- 벽인 경우 count를 반환
- 현재좌표의 청소 여부와 벽 (
int count = 0;
boolean isDirty; // 주변 4칸에 청소할 곳이 있는지 여부
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{x, y});
while (!q.isEmpty()) {
int now[] = q.poll();
int nowX = now[0];
int nowY = now[1];
isDirty = false;
// 현재 위치가 청소를 하지 않은 곳이라면 청소 후 Count++
if(A[nowX][nowY] == 0 && !visited[nowX][nowY]){
visited[nowX][nowY] = true;
count++;
}
// 만약 현재 위치가 벽이라면 Count를 return
else if(A[nowX][nowY] == 1){
return count;
}
....방향 전환
- 현재 위치에서 주변 동서남북을 탐색, 한 곳이라도 청소할 곳이 있다면 isDirty를 true로 표시하고 반시계 방향으로 90도 꺾은 후 for문 탈출
// 현재 위치에서 주변 4칸 탐색
for (int i = 0; i < 4; i++) {
int nextX = nowX + dx[i];
int nextY = nowY + dy[i];
//만약 주변에 청소를 하지 않은 곳이 있다면
if(A[nextX][nextY] == 0 && !visited[nextX][nextY]){
// 청소할 곳이 있다는 표시
isDirty = true;
// 반시계 방향으로 90도 꺾음
if(isDirection == 0){
isDirection = 3;
}
else if (isDirection > 0){
isDirection--;
}
// 탈출
break;
}
}로봇청소기 이동
- 만약 isDirty, 즉 주변에 청소할 곳이 있을 때 바라보는 방향의 앞 쪽에 청소되지 않은 빈 칸이 존재 한다면(0 이며 visited가 false일 때) Queue에 바라보는 방향으로 한 칸 전진한 좌표를 add
- 아닐 경우 현재 좌표를 Queue에 add하여 다시 while문 실행
- 주변에 청소되지 않은 빈 칸이 없는 경우( isDirty가 false ) 바라보는 방향을 switch로 확인하여 한 칸 후진 후 좌표를 Queue에 add하여 다시 while문으로 돌아가 탐색
- Queue가 다 비워지면 지금까지 count한 청소 영역 개수를 반환
int nX = 0;
int nY = 0;
// 만약 주변에 청소할 곳이 있다면
if(isDirty) {
nX = nowX + dx[isDirection];
nY = nowY + dy[isDirection];
// 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
if(A[nX][nY] == 0 && !visited[nX][nY]){
q.add(new int[]{nX, nY});
}
// 아닐 경우 현재위치에서 다시 탐색
else {
q.add(new int[]{nowX, nowY});
}
}
// 주변에 청소되지 않은 빈 칸이 없는 경우(isDirty == false) 나의 방향에서 한칸 후진 후 다시 탐색
else {
switch (isDirection) {
case 0:
nX = nowX + dx[2];
nY = nowY + dy[2];
break;
case 1:
nX = nowX + dx[3];
nY = nowY + dy[3];
break;
case 2:
nX = nowX + dx[0];
nY = nowY + dy[0];
break;
case 3:
nX = nowX + dx[1];
nY = nowY + dy[1];
break;
}
q.add(new int[]{nX, nY});
}
}
return count;
}
}구현한 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[][] A;
static int N,M,r,c,d;
static StringBuilder sb = new StringBuilder();
static ArrayList<Integer> buildingCount = new ArrayList<>();
static int count = 0;
static int isDirection;
// 0 = 북, 1 = 동, 2 = 남, 3 = 서
static boolean[][] visited;
static int[] dx = {-1, 0, 1, 0}; // 상, 하
static int[] dy = {0, 1, 0, -1}; // 좌, 우
//
static int number = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 첫 번째 줄 처리
String[] firstLine = br.readLine().split(" ");
N = Integer.parseInt(firstLine[0]);
M = Integer.parseInt(firstLine[1]);
// 두 번째 줄 처리
String[] secondLine = br.readLine().split(" ");
r = Integer.parseInt(secondLine[0]);
c = Integer.parseInt(secondLine[1]);
d = Integer.parseInt(secondLine[2]);
A = new int[N][M];
visited = new boolean[N][M];
for (int i = 0; i < N ; i++) {
String[] value = br.readLine().split(" ");
for (int j = 0; j < value.length; j++) {
A[i][j] = Integer.parseInt(value[j]);
}
}
isDirection = d;
count = BFS(r, c);
sb.append(count);
System.out.println(sb);
}
public static int BFS(int x, int y){
int count = 0;
boolean isDirty; //주변 4칸에 청소할 곳이 있는지 여부
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{x, y});
while (!q.isEmpty()) {
int now[] = q.poll();
int nowX = now[0];
int nowY = now[1];
isDirty = false;
// 현재 위치가 청소를 하지 않은 곳이라면 청소 후 Count++
if(A[nowX][nowY] == 0 && !visited[nowX][nowY]){
visited[nowX][nowY] = true;
count++;
}
// 만약 현재 위치가 벽이라면 Count를 return
else if(A[nowX][nowY] == 1){
return count;
}
// 현재 위치에서 주변 4칸 탐색
for (int i = 0; i < 4; i++) {
int nextX = nowX + dx[i];
int nextY = nowY + dy[i];
//만약 주변에 청소를 하지 않은 곳이 있다면
if(A[nextX][nextY] == 0 && !visited[nextX][nextY]){
// 청소할 곳이 있다는 표시
isDirty = true;
// 반시계 방향으로 90도 꺾음
if(isDirection == 0){
isDirection = 3;
}
else if (isDirection > 0){
isDirection--;
}
// 탈출
break;
}
}
int nX = 0;
int nY = 0;
// 만약 주변에 청소할 곳이 있다면
if(isDirty) {
nX = nowX + dx[isDirection];
nY = nowY + dy[isDirection];
// 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
if(A[nX][nY] == 0 && !visited[nX][nY]){
q.add(new int[]{nX, nY});
}
// 아닐 경우 현재위치에서 다시 탐색
else {
q.add(new int[]{nowX, nowY});
}
}
// 주변에 청소되지 않은 빈 칸이 없는 경우(isDirty == false) 나의 방향에서 한칸 후진 후 다시 탐색
else {
switch (isDirection) {
case 0:
nX = nowX + dx[2];
nY = nowY + dy[2];
break;
case 1:
nX = nowX + dx[3];
nY = nowY + dy[3];
break;
case 2:
nX = nowX + dx[0];
nY = nowY + dy[0];
break;
case 3:
nX = nowX + dx[1];
nY = nowY + dy[1];
break;
}
q.add(new int[]{nX, nY});
}
}
return count;
}
}결과
류세민님의 개발블로그 입니다