[BJ]G5 14503 로봇청소기

[BJ]G5 14503 로봇청소기

 

 

문제링크

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

14503번: 로봇 청소기

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=ku0Go1rzyEs 

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

/**
 * @author 은서파
 * @since 2021. 10. 27.
 * @see https://www.acmicpc.net/problem/14503
 * @performance 11840	80
 * @category #시뮬레이션
 * @memo
 */

public class BJ_G5_14503_로봇청소기 {

	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	
	// 방향에 따른 delta 정리
	static int [][] deltas = {{-1, 0},{0, 1},{1, 0},{0, -1}};
	
	static int N, M;
	static int [][] map;
	public static void main(String[] args) throws IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		
		// 청소기의 초기 위치 정보
		tokens = new StringTokenizer(input.readLine());
		int cr = Integer.parseInt(tokens.nextToken());
		int cc = Integer.parseInt(tokens.nextToken());
		int cd = Integer.parseInt(tokens.nextToken());
		
		// 지도 정보
		map = new int [N][M];
		for(int r=0; r<N; r++) {
			tokens = new StringTokenizer(input.readLine());
			for(int c=0; c<M; c++) {
				map[r][c] = Integer.parseInt(tokens.nextToken());
			}
		}
		// 입력 완료!
		
		Clearner clearner = new Clearner(cr, cc, cd);
		// 청소기를 현재 위치에 배치한다 - 청소 진행
		clearner.clean(cr, cc);
		
		// 갈때 까지 청소 시켜보자.
		outer: while(true) {
			// 4방 탐색으로 가보기
			for(int d=0; d<deltas.length; d++) {
				// 회전 해보기
				clearner.turn();
				// 해당 방향으로 갈 수 있나?
				int nr = clearner.row + deltas[clearner.dir][0];
				int nc = clearner.col + deltas[clearner.dir][1];
				
				// 거기가 공백이면서 아직 미청소 구역이면 가보기!!
				if(map[nr][nc]==0) {
					clearner.clean(nr, nc);
					// 나머지 방향은 볼 필요 없다.
					continue outer;
				}
			}//for
			
			// continuer를 못했다 - 후진 후 다시 시도!
			if(!clearner.backword()) {
				break outer;
			}
		}
		System.out.println(clearner.cleaned);
	}

	static class Clearner{
		int row, col, dir,cleaned;
		
		public Clearner(int row, int col, int dir) {
			this.row = row;
			this.col = col;
			this.dir = dir;
		}
		
		// 청소기의 동작 처리 - 청소, 회전, 후진
		public void clean(int r, int c) {
			this.row = r;
			this.col = c;
			map[r][c]=2; // 청소가 완료되 지역 표시
			cleaned++;
		}
		
		// 회전 - 왼쪽 즉 반 시계 방향으로 회전
		public void turn() {
			dir--;
			if(dir==-1) {
				dir=3;
			}
		}
		
		// 후진
		public boolean backword() {
			this.row -=deltas[this.dir][0];
			this.col -=deltas[this.dir][1];
			// 새로운 좌표로 갈 수 있으면 가보자!!
			if(map[this.row][this.col]==1) {
				return false;
			}
			return true;
		}
	}
	
	// REMOVE_START
	private static String src = "11 10\r\n" +
								"7 4 0\r\n" +
								"1 1 1 1 1 1 1 1 1 1\r\n" +
								"1 0 0 0 0 0 0 0 0 1\r\n" +
								"1 0 0 0 1 1 1 1 0 1\r\n" +
								"1 0 0 1 1 0 0 0 0 1\r\n" +
								"1 0 1 1 0 0 0 0 0 1\r\n" +
								"1 0 0 0 0 0 0 0 0 1\r\n" +
								"1 0 0 0 0 0 0 1 0 1\r\n" +
								"1 0 0 0 0 0 1 1 0 1\r\n" +
								"1 0 0 0 0 0 1 1 0 1\r\n" +
								"1 0 0 0 0 0 0 0 0 1\r\n" +
								"1 1 1 1 1 1 1 1 1 1";
	// REMOVE_END
}