백준_14503_로봇청소기

📖 목차

👆 링크
🤞 문제
👌 코드
🖖 풀이
🖐 Git gist 주소

📌 링크

https://www.acmicpc.net/problem/14503

📝 문제

  로봇청소기가 N × M 크기의 영역에서 청소하는 영역의 개수를 구하는 문제이다.

  영역은 벽과 빈 칸으로 이루어져 있으며, 로봇청소기는 동 서 남 북 네 방향의 빈 영역만 청소 가능하다. 로봇 청소기는 아래 규칙과 같이 작동한다.

  또한, 로봇청소기는 이미 청소되어 있는 칸은 청소하지 않으며, 벽을 통과할 수 없다.

11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

💻 코드

package backJoon_4991_robotCleaner;
import java.util.*;
/*
 * 
 * 백준알고리즘
 * 14503. 로봇 청소기
 * https://www.acmicpc.net/problem/14503
 * 2021-05-31
 * 
 * */
public class Practice {
	static Scanner sc = new Scanner(System.in);
	static int N, M;
	static int firstY, firstX, firstD;
	static int[][] map;
	static boolean[][] cleaned;
	static int[] dy = {-1, 0, 1, 0};//북동남서
	static int[] dx = {0, 1, 0, -1};
	static int answer = 1;
	
	public static void main(String[] args) {
		//N,M,y,x,d 입력
		readInput();
		
		clear(firstY, firstX, firstD);
		
		System.out.println(answer);
	}

	private static void clear(int y, int x, int d) {
		//청소
		cleaned[y][x] = true;
		int cnt = 0;
		int bd = d;
		
		while(cnt < 4) {
			cnt++;
			//현재위치 기준 왼쪽
			d = (d + 3) % 4;
            
			//다음방향 확인
			int ny = y + dy[d];
			int nx = x + dx[d];
			
			if(isArrange(ny, nx) && !cleaned[ny][nx] && map[ny][nx] == 0) {
				//System.out.println(answer+" >> "+ny+", "+nx+", "+d);
				answer++;
				clear(ny, nx, d);
				//break; //break를 하면 ▼다시 아래로직까지 타게된다.
				return;
			}
		}
		
        	//현재 방향을 그대로 유지한 채(bd) 한칸 뒤로 간 위치(by, bx)
		int by = y - dy[bd];
		int bx = x - dx[bd];
        
		//네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
		if(isArrange(by, bx) && map[by][bx] == 1) return;
		
		//네 방향 모두 청소가 이미 되어있거나 벽인 경우, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
		clear(by, bx, bd);
	}

	private static boolean isArrange(int ny, int nx) {
		return ny >= 0 && nx >= 0 && ny < N && nx < M;
	}

	private static void readInput() {
		N = sc.nextInt();
		M = sc.nextInt();
		firstY = sc.nextInt();
		firstX = sc.nextInt();
		firstD = sc.nextInt();
		map = new int[N][M];
		cleaned = new boolean[N][M];
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
			}
		}
	}

}

✍ 풀이

👉 1. 모든 경우의 수를 계산하지 않는 DFS

  모든 경우의 수를 계산해야 할 때, DFS(Depth First Search)으로 문제를 풀곤 한다. 하지만 이 문제의 경우에는 오직 한 가지 경우의 수로 정해져있다. 무조건 현재 방향의 왼쪽부터 탐색하기 때문에 경로가 정해져 있는 것이다.

  한마디로, 이 문제는 답정너란 소리다.

private static void clear(int y, int x, int d) {
    ...
    
    while(cnt < 4) {
	if(isArrange(ny, nx) && !cleaned[ny][nx] && map[ny][nx] == 0) {
		answer++;
		clear(ny, nx, d);
		//break; //break를 하면 ▼다시 아래로직까지 타게된다.
		return;
	}
    }  
    	//현재 방향을 그대로 유지한 채(bd) 한칸 뒤로 간 위치(by, bx)
	...
}

  따라서 DFS 메소드인 clear()가 종료될 때마다 return으로 해당 메소드를 빠져나와야 한다. return이 아닌 break 사용 시, while문만 빠져나오기 때문에 clear()가 종료되지 않아 while문 아래에 있는 로직까지 진행되어 버린다.

👉 2. 조건에 명시된 '방향 설정'이 중요하다.

  현재 방향의 왼쪽을 어떻게 설정해줄 것인가가 중요하다.

그림과 같이 방향은 북쪽 = 0, 동쪽 = 1, 남쪽 = 2, 서쪽 = 3 으로 정해져있다.

static int[] dy = {-1, 0, 1, 0};
static int[] dx = {0, 1, 0, -1};

0부터 3까지 북동남서순이기 때문에 dy, dx변수역시 동일하게 맞춰준다.

✔  조건 2-2에 따라 현재 방향 기준 왼쪽이므로, 다음 방향을 정하는 식은 d = (d + 3) % 4 로 표현할 수 있다. 처음 식을 생각하기 어려울 땐, 일정한 규칙에 따라 d = d - 1 (단, d = 0일 경우 다음 방향은 3으로 설정) 이런 방법도 가능하다.


✔  현재 방향을 유지한 채 뒤로 한칸 후진해야 한다는 조건 2-3을 헷갈리지 않도록 해야한다. 나는 이 조건을 잘못 이해해서, 한칸 후진할 때 방향을 반대로 설정해 스택오버플로우 에러를 내버리고 말았다(...)


💡  네 방향으로 탐색할 때 주의해야 할 점이 있다.

for(int d = 0; d < 4; d++) {
	nd = (coord.d + 3) % 4;
	...

  위처럼 할 시 for문을 아무리 돌아도 nd에는 똑같은 값이 들어가게 된다. for문을 도는 동안 변하지 않는 변수인 coord.d에 계속 똑같은 연산을 해주게 되기 때문이다.

d = (d + 3) % 4;

  따라서 계산 전과 후는 같은 변수를 써야 한다. 이렇게 되면 원래 방향이었던 d의 값은 for문을 돌며 변하게 된다.

private static void clear(int y, int x, int d) {
	//청소
	cleaned[y][x] = true;
	int cnt = 0;
	int bd = d;
        ...

  하지만 후진할 때 원래 방향을 유지해야 하므로, DFS함수 초반에 미리 원래의 방향 변수d를 bd에 저장해놔야 한다.

👩‍💻 Git gist 주소

https://gist.github.com/ysyS2ysy/cbed33a6dc7cefef297e4a726dc8feca