14503 번 문제 풀이

using Java 11

14503 문제 보기

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 설정 해놓은 거 잊어서 런타임 에러가 나길래,,, 재귀함수를 열심히 뜯었는데 그게 문제가 아니었다. 😂