[BOJ] 14503: 로봇청소기 (JAVA)

14503번: 로봇 청소기

 

풀이

 

지난번 신협 코테에서 비슷한 문제가 나왔던 기억이 있어 풀어봤는데, 너무 오래걸렸다.
일단 문항 해석에서 난항을 겪었는데 어디서 난항을 겪었냐면 ..

2. 현재 칸의 주변 4칸 중 청소되지 않은 빈칸이 없는 경우,
 2-1. 바라보는 방향을 유지한 채 한 칸 후진할 수 있으면 한 칸 후진하고 1번으로 돌아간다.(난 여기서 맨 처음 방향을 유지하는 걸로 해석했다.)

그리고 반시계방향으로 돈다는 사실을 ^^ 계속해서 시계방향으로 돈다고 착각하고 문제를 풀고 있었다. (문제를 잘 읽자.)
방향이야 인지한 즉시 해결했지만, 후진할 때 방향과 관련해서 계속 문제가 있었다.
이게 결국 4번 회전했는데, 주변이 이미 다 청소한 경우! 에만 후진을 하는거니까
4번 회전하는 동안 계속 방향을 반시계방향으로 돌려줘야 한다.

 

package 백준renew;

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

public class 골드5_14503_로봇청소기 {
	static int N, M, ans;
	static int rX, rY, rR;
	static int map[][];
	static int goX[] = {-1, 0, 1, 0};
	static int goY[] = {0, 1, 0, -1};
	static class Robot{
		int x;
		int y;
		int r;
		Robot(int x, int y, int r){
			this.x = x;
			this.y = y;
			this.r = r;
		}
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		rX = Integer.parseInt(st.nextToken());
		rY = Integer.parseInt(st.nextToken());
		rR = 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());
			}
		}
		
		BFS(rX, rY, rR);
		
		ans = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 2) {
					ans++;
				}
			}
		}
		
		sb.append(ans);
		
		bw.write(sb.toString());bw.flush();bw.close();
		
	}
	static void BFS(int x, int y, int r) {
		Queue<Robot> q = new LinkedList<>();
		q.offer(new Robot(x, y, r));
		map[x][y] = 2;
		
		while(!q.isEmpty()) {
			int clean = 0;
			Robot ro = q.poll();
			int nowX = ro.x;
			int nowY = ro.y;
			int nowR = ro.r;
			int newX, newY, newR;
			for(int i=0; i<4; i++) {
				//nowR을 덮어씌워야 다음 탐색에 적용이 된다.
				nowR = (nowR+3)%4; //반시계방향으로 돌아간다고 했으니까.
				newX = ro.x + goX[nowR];
				newY = ro.y + goY[nowR];
				
				if(newX >=0 || newX < N || newY >=0 || newY < M) {
					if(map[newX][newY] == 0) {
						q.offer(new Robot(newX, newY, nowR));
						map[newX][newY] = 2;
						break;
					}else {
						clean++;
					}
				}
				
			}
			
			if(clean == 4) {
				newR = (ro.r+2)%4;
				newX = ro.x + goX[newR];
				newY = ro.y + goY[newR];
				
				if(map[newX][newY]!=1) {
					q.offer(new Robot(newX, newY, nowR));
					map[newX][newY] = 2;
				}
			}
		}
	}
}