728x90
반응형
[백준 14503] 로봇 청소기(Java)
https://www.acmicpc.net/problem/14503
14503번: 로봇 청소기
첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽
www.acmicpc.net
해결 방법
1트
문제를 읽고 작동이 멈출때 까지 loop를 사용하면 되어서 BFS로 접근해서 해결했습니다.
저는 방향을 돌리는 것이 수식으로 생각이 나지 않아서 조건문을 모두 만들어서 해결했습니다.
조건대로 구현을 했는데!
틀렸습니다. ㅠ0ㅠ
2트
디버깅을 통해 틀린 이유는 바로 청소한 부분을 다시 지나갈 수 있다는것을 간과했기 때문입니다.
따라서 청소할 부분을 찾아 회전을 시켜야합니다.
풀이
public class Quiz14503 {
static int n;
static int m;
static int startX;
static int startY;
static int front;
static int[][] map;
static int[] ud = {1, -1, 0, 0};
static int[] lr = {0, 0, 1, -1};
public static void main(String[] args) throws IOException {
/**
* 1. 현재 칸이 청소되지 않은 경우, 현재 칸 청소
* 2. 근처 4칸이 모두 깨끗한 경우
* 2.1) 바라보는 방향을 유지하고 한칸 후진
* 2.2) 후진 못하면 멈춤
* 3. 4칸 중 더러운 곳이 있으면
* 3.1) 반시계 방향으로 90도 회전
* 3.2) 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈칸인 경우 1칸 전진
* 3.3) 1번 실행
*
* 로봇 청소기가 작동을 멈출때 까지 청소하는 칸의 갯수
*/
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());
startX = Integer.parseInt(st.nextToken());
startY = Integer.parseInt(st.nextToken());
// 0: 북, 1: 동, 2: 남, 3: 서
front = 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());
}
}
int bfs = bfs();
System.out.print(bfs);
br.close();
}
private static int bfs() {
Queue<Robot> queue = new ArrayDeque<>();
queue.add(new Robot(startX, startY, front));
int count = 0;
while(!queue.isEmpty()) {
Robot poll = queue.poll();
int x = poll.getX();
int y = poll.getY();
int direction = poll.getDirection();
// 현재 칸이 청소가 안되어 있으면 청소
if(map[x][y] == 0) {
map[x][y] = -1; // 청소 완료
count++;
}
// 근처 4칸이 모두 깨끗하면
if(!rangeCheck(x, y)) {
// 북을 바라보면 남으로 이동
if(direction == 0) {
// 후진 가능
if(map[x+1][y] != 1) {
// 바라보는 방향을 유지하고 한칸 후진
queue.add(new Robot(x + 1, y, direction));
}
// 후진 불가
else {
return count;
}
}
// 동을 바라보면 서로 이동
else if(direction == 1) {
// 후진 가능
if(map[x][y-1] != 1) {
// 바라보는 방향을 유지하고 한칸 후진
queue.add(new Robot(x, y - 1, direction));
}
// 후진 불가
else {
return count;
}
}
// 남을 바라보면 북으로 이동
else if(direction == 2) {
// 후진 가능
if(map[x-1][y] != 1) {
// 바라보는 방향을 유지하고 한칸 후진
queue.add(new Robot(x - 1, y, direction));
}
// 후진 불가
else {
return count;
}
}
// 서를 바라보면 동으로 이동
else if(direction == 3) {
// 후진 가능
if(map[x][y+1] != 1) {
// 바라보는 방향을 유지하고 한칸 후진
queue.add(new Robot(x, y + 1, direction));
}
// 후진 불가
else {
return count;
}
}
}
// 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우
else {
while (true) {
// 방향 전환
switch (direction) {
case 0:
direction = 3;
break;
case 1:
direction = 0;
break;
case 2:
direction = 1;
break;
case 3:
direction = 2;
break;
}
// 북
if (direction == 0) {
// 앞쪽 칸이 청소되지 않은 빈칸 인경우 한칸 전진
if (x - 1 >= 0 && x - 1 < n) {
if (map[x - 1][y] == 0) {
queue.add(new Robot(x - 1, y, direction));
break;
}
}
}
// 동
else if (direction == 1) {
// 앞쪽 칸이 청소되지 않은 빈칸 인경우 한칸 전진
if (y + 1 >= 0 && y + 1 < m) {
if (map[x][y + 1] == 0) {
queue.add(new Robot(x, y + 1, direction));
break;
}
}
}
// 서
else if (direction == 3) {
// 앞쪽 칸이 청소되지 않은 빈칸 인경우 한칸 전진
if (y - 1 >= 0 && y - 1 < m) {
if (map[x][y - 1] == 0) {
queue.add(new Robot(x, y - 1, direction));
break;
}
}
}
// 남
else if (direction == 2) {
// 앞쪽 칸이 청소되지 않은 빈칸 인경우 한칸 전진
if (x + 1 >= 0 && x + 1 < n) {
if (map[x + 1][y] == 0) {
queue.add(new Robot(x + 1, y, direction));
break;
}
}
}
}
}
}
return count;
}
private static boolean rangeCheck(int x, int y) {
for(int i = 0; i < 4; i++) {
int newX = x + ud[i];
int newY = y + lr[i];
// map을 벗어나는 경우
if(newX < 0 || newY < 0 || newX >= n || newY >= m) continue;
// 1칸이라도 청소할 곳이 있으면
if(map[newX][newY] == 0) {
return true;
}
}
// 4칸 모두 깨끗한 경우
return false;
}
static class Robot {
private int x;
private int y;
private int direction;
public Robot(int x, int y, int direction) {
this.x = x;
this.y = y;
this.direction = direction;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public int getDirection() {
return direction;
}
}
}
맞았습니다!!
더 좋은 방법이 없을까? 🤔
코드가 너무 지저분하고 가독성이 떨어지는 것으로 느꼈습니다.
따라서 더 좋은 방법을 찾기위해서 다른 사람의 풀이를 조사해보았습니다.
[백준] 14503 - 로봇 청소기 (java)
문제 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로
velog.io
동, 서, 남, 북
먼저 로봇이 반시계 방향으로 도는 것과 뒤로가는 것에 대해서 식을 정의 했습니다.
이러한 특징을 이용해서 다음과 같이 코드를 작성할 수 있습니다.
// 북(0), 남(2), 서(1), 동(4)
static int[] ns = {-1, 0, 1, 0};
static int[] we = {0, 1, 0, -1};
// 후진
direction = (direction + 2) % 4;
int newX = ns[direction];
int newY = we[direction];
// 방향 돌리기
direction = (direction + 3) % 4;
int newX = ns[direction];
int newY = we[direction];DFS
그리고 생각해보니 로봇은 한 번 방향이 정해지면 방향에 따라서 이동합니다.
그래서 DFS 방식의 재귀를 사용하는 것이 더 좋을 것이라 판단했습니다. 👍
풀이2
public class Quiz14503_2 {
static int n;
static int m;
static int startX;
static int startY;
static int front;
static int[][] map;
// 북(0), 남(2), 서(1), 동(4)
static int[] ns = {-1, 0, 1, 0};
static int[] we = {0, 1, 0, -1};
// 청소한 블록 갯수
static int count = 0;
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());
startX = Integer.parseInt(st.nextToken());
startY = Integer.parseInt(st.nextToken());
// 0: 북, 1: 동, 2: 남, 3: 서
front = 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());
}
}
// dfs 수행
dfs(startX, startY, front);
System.out.print(count);
br.close();
}
private static void dfs(int x, int y, int direction) {
// 현재 칸이 청소 X
if(map[x][y] == 0) {
// 청소
map[x][y] = -1;
count++;
}
// 주위(4칸)가 다 깨끗한지
if(isClean(x, y)) {
// 후진
int newDirection = (direction + 2) % 4;
int newX = x + ns[newDirection];
int newY = y + we[newDirection];
// 범위 체크
if(newX < 0 || newY < 0 || newX >= n || newY >= m) return;
// 후진 불가
if(map[newX][newY] == 1) return;
// 방향은 유지해야함
dfs(newX, newY, direction);
}
// 주위(4칸)에 더러운 칸이 있는 경우
else {
// 최대 4번 회전 가능
for(int i = 0; i < 4; i++) {
// 회전
direction = (direction + 3) % 4;
int newX = x + ns[direction];
int newY = y + we[direction];
if (newX < 0 || newY < 0 || newX >= n || newY >= m) return;
// dfs(newX, newY, direction);
// 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈칸인 경우 한 칸 전진
if (map[newX][newY] == 0) {
dfs(newX, newY, direction);
break;
}
}
}
}
// 주위(4칸)가 다 깨끗한지
private static boolean isClean(int x, int y) {
for(int i = 0; i < 4; i++) {
int newX = x + ns[i];
int newY = y + we[i];
if(newX < 0 || newY < 0 || newX >= n || newY >= m) continue;
// 더러운 곳이 1곳이라도 있으면
if(map[newX][newY] == 0) {
return false;
}
}
return true;
}
}
이전보다 훨씬 코드가 간결해지고 가독성이 좋아진것 같습니다! 👍
728x90
반응형
'0 + 알고리즘(Algorithm) > 0 + 백준' 카테고리의 다른 글
| [백준 7569] 토마토(Java) (0) | 2023.04.17 |
|---|---|
| [백준 2644] 촌수계산(Java) (0) | 2023.04.17 |
| [백준 5014] 스타트링크(Java) (0) | 2023.04.17 |
| [백준 1987] 알파벳(Java) (0) | 2023.04.16 |
| [백준 2468] 안전 영역(Java) (0) | 2023.04.16 |