[BOJ] 백준 14503 - 로봇 청소기
14503 번 문제 풀이
using Java 11
package BOJ;
import java.io.*;
import java.util.*;
public class boj14503 {
public static int[] dx = {-1, 0, 1, 0};
public static int[] dy = {0, 1, 0, -1};
public static int N, M, r, c, d, cnt = 0;
public static int[][] map;
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());
map = new int[N][M];
st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
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());
}
}
cleaner(r, c, d);
System.out.println(cnt);
System.exit(0);
}
public static boolean isValid(int row, int col) {
if(row < 0 || col < 0 || row >= N || col >= M) return false;
return true;
}
public static void cleaner(int r, int c, int d) {
if(map[r][c] == 0) {
cnt++;
map[r][c] = 2;
}
int i;
int direction = d;
for(i = 0; i < 4; i++) {
direction += 3;
int nextR = r + dx[direction % 4];
int nextC = c + dy[direction % 4];
if(isValid(nextR, nextC) && map[nextR][nextC] == 0) {
cleaner(nextR, nextC, direction % 4);
break;
}
}
if(i == 4) {
int nextR = r + dx[(d+2) % 4];
int nextC = c + dy[(d+2) % 4];
if(isValid(nextR, nextC) && map[nextR][nextC] != 1) {
cleaner(nextR, nextC, d);
}
}
}
}
📍 문제 해석 오류
2-c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
2-d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.
주어진 문제의 일부이다.
네 방향 모두 청소가 되어 있을 때, 뒤쪽방향이 벽이 아니면 후진 하고 벽이라면 작동을 멈추라고 되어있다. 분명 벽이 아닐때만 움직이는게 맞는데 또 그 다음 제시에서는 청소 되어있는 칸은 또 청소하지 않는 다고 한다.
if(i == 4) { int nextR = r + dx[(d+2) % 4]; int nextC = c + dy[(d+2) % 4]; if(isValid(nextR, nextC) && map[nextR][nextC] != 1) { cleaner(nextR, nextC, d); } }
❌❌ (map[nextR][nextC] == 0) ❌❌
제시 두 개를 합쳐서 생각해서 청소 되어있는 곳은 아예 방문하지도 못하게 코드를 작성했다.
⭕️⭕️ (map[nextR][nextC] != 1) ⭕️⭕️
청소 했던 곳은 방문은 하되 청소가 이미 되어있으니 카운트만 올리지 말란 소리였다.
📍 재귀호출 실수하지말자
처음에 아무 생각 없이 재귀 호출 하다가 stack overflow를 냈다.
for문으로 네 방향 검사 하고 if문으로 한번만 호출하면 되는데 네 뱡향 다 들어가서 depth 체크 하다가 오버플로우가 발생했다. 그러지말자 제발, 안되는 거 알면서 왜 그랬을까~
📍 방향 설정
문제에서 왼쪽 방향으로(반시계방향으로) 검사하라고 주어졌다.
그런데 direction number는 0 에서 4 까지 시계 방향으로 줬다. (북 > 동 > 남 > 서)
나는 자연스럽게 시계 방향으로 탐색해서 또,, 오래,, 걸렸다.
방향 바뀐 걸 알고 dx,dy 배열을 반시계로 재배열 했다가 또 시간을 엄청 쏟았다.
배열은 문제에서 주어진 숫자 순서 그대로여야 하기 때문에 변경하면 입력에 대한 잘못된 처리를 하게된다. 해결방안은 direction + 3 해서 % 4 나머지 연산 시 한 자리씩 덜 가게 하면 된다. (+4 하면 4자리 옮기는 것 == 제자리 / +3 하면 한 자리 덜 가는 것 == 뒤로 한 칸 == 반시계로 한 칸) 마찬가지로 후진 시에도 direction + 2 해주면 된다.
for(i = 0; i < 4; i++) { direction += 3; int nextR = r + dx[direction % 4]; int nextC = c + dy[direction % 4]; if(isValid(nextR, nextC) && map[nextR][nextC] == 0) { cleaner(nextR, nextC, direction % 4); break; } }
쉬운 문젠데 이상하게 해맸다. 잔실수를 줄이고 꼼꼼하게 짜야하는데 항상 이상한 곳에서 시간을 허비하는 것 같다.
이번 문제로는 방향을 설정할때 자주 빠지는 함정에 대해 얻어 간다.
+ 그리고 백준 제출할 때 pakage 설정은 없애야하고 class 이름은 Main 이어야 한다. 아니면 각각 런타임 에러, 컴파일 에러가 난다. pakage 설정 해놓은 거 잊어서 런타임 에러가 나길래,,, 재귀함수를 열심히 뜯었는데 그게 문제가 아니었다. 😂
Author And Source
이 문제에 관하여([BOJ] 백준 14503 - 로봇 청소기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@since1909/BOJ14503저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)