[JAVA] 백준 14503 로봇 청소기

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

14503번: 로봇 청소기

 

1. 서론

 

풀어서 좋아했는데 골5네... ㅎㅎ 슬프다. 삼성 먼 옛날 기출문제로 코드트리의 자율주행 자동차와도 정말 같은 문제이다. (심지어 입출력도 똑같음)

 

https://www.codetree.ai/frequent-problems/autonomous-driving/description

코드트리

 

테케가 더 필요한 사람이라면 들어가서 봐도 좋을지도? 그냥 별 기법없는 시뮬레이션 문제이다.

 

2. 문제 풀이

 

문제를 아주 자세하고 꼼꼼히 읽어야 한다. 안 그러면 나처럼 이상한 곳에서 헤맨다. (밑에 나올 4-1, 4-2위치 + 세부 조건들 때문에)

 

내가 만든 로봇 청소기 로직은 다음과 같다.

 

1. 현재 위치를 청소

2. 왼쪽으로 방향 전환

3. 현재 위치를 기준으로 4방을 탐색하며 빈칸이 있는지 없는 지 센다.

4-1. 3에서 센 수가 4인경우 후진할 수 있는지 체크한다.

4-1-1. 후진 방향으로 방향을 바꾼 후, 그 방향으로 이동해서 그 부분이 벽이 아니라면 2번으로

4-1-2. 벽이라면 반복을 끝낸다.

4-2. 3에서 센 수가 4가 아닌 경우 왼쪽 방향을 청소할 수 있는지 체크한다.

4-2-1. 왼쪽 방향에 청소할 공간이 있는 경우: 그 칸으로 이동, 1번으로

4-2-2. 왼쪽 방향에 청소할 공간이 없는 경우: 2번으로

 

1~4번을 반복해야 하므로 재귀를 통해서 코드를 구현했다!

(내가 재귀함수를 만들다니...)

 

문제와 다르게 네 방향 탐색을 먼저 하는 이유는 그냥 그게 더 합리적일 것 같아서였는데 나중에 문제 조건을 보니 '바라보는 방향을 유지한 채'라는 조건이 있으므로 왼쪽으로 돌리기 전에 먼저 하는 것이 편하게 할 수 있는 방법이다.

 

3. 코드 설명

 

import java.io.*;
import java.util.*;

public class Main {
	
	static int n, m, ans;
	static int[][] map;
	static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1}; //북,동,남,서
	
	public static void main(String[] args) throws Exception {
        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());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int d = 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());
        }
        
        check(r, c, d);
        System.out.println(ans);
	}
	
	public static int rotation1(int d) { //왼쪽
		if (d == 0) return 3; //북 -> 서
		if (d == 3) return 2; //서 -> 남
		if (d == 2) return 1; //남 -> 동
		if (d == 1) return 0; //동 -> 북
		return -1;
	}
	
	public static int rotation2(int d) { //후진
		if (d == 0) return 2; //북 -> 남
		if (d == 2) return 0; //남 -> 북
		if (d == 1) return 3; //동 -> 서
		if (d == 3) return 1; //서 -> 동
		return -1;
	}
	
	public static void check(int x, int y, int d) {
		if (map[x][y] == 0) {
			map[x][y] = 2; //청소한 곳 체크
			ans++;
		}

		int cnt = 0;
		for (int k = 0; k < 4; k++) { //사방 중에 이동할 수 없는 곳 체크
			int nx = x + dx[k], ny = y + dy[k];
			if (range(nx, ny) && map[nx][ny] != 0)
				cnt++;
		}
		
		if (cnt == 4) { // 사방 모두 이동할 수 없는 경우
			d = rotation2(d); //후진 방향
			int nx = x + dx[d], ny = y + dy[d];
			if (range(nx, ny) && map[nx][ny] != 1) {//후진
				d = rotation2(d);
				check(nx, ny, d);
			}
			else //후진 못하는 경우 종료
				return;
		}
		else { //이동할 수 있는 경우
			d = rotation1(d); //왼쪽으로 회전
			
			int nx = x + dx[d], ny = y + dy[d];
			if (range(nx, ny) && map[nx][ny] == 0) //청소할 수 있는 경우
				check(nx, ny, d);
			else //없는 경우
				check(x, y, d);
		}
	}
	
	public static boolean range(int nx, int ny) {
		if (nx >= 0 && nx < n && ny >= 0 && ny < m)
			return true;
		return false;
	}
}

 

문제에서 북, 동, 남, 서 순서대로 0~3으로 설정해줬기 때문에 dx ,dy를 그 순서대로 설정했다.

그리고 왼쪽으로 방향 번호를 바꿔주는 rotation1과 후진방향으로 방향을 바꿔주는 rotation2 함수를 만들었다.

그리고 위에 적은 로직대로 코드를 짰다. 

 

이 과정에서 내가 조건 다 맞춰줬는데 자꾸 오버플로우나서 보니까 실수한 게 바로... 후진 방향으로 돌린 후 갈 수 있는지 체크하고 원래 방향으로 돌려서 후진 쪽 좌표로 이동해줘야 한다는 것이었다. 후진은 말 그대로 앞을 본 채로 뒤로 가는 것이기 때문에...!! (바보)