[BOJ-14503] 로봇 청소기 -Java

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

14503번: 로봇 청소기

package 시뮬레이션_review;

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

public class boj_14503_로봇청소기 {
	static int N, M, map[][];
	static int dx[] = { 0, -1, 0, 1 }; //동 북 서 남 
	static int dy[] = { 1, 0, -1, 0 };

	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());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		if(d==0 || d==2) d++;
		else d--;
		
		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());
			}
		}
		System.out.println(solve(r, c, d));
	}

	private static int solve(int r, int c, int d) {
		int cnt = 0;
		boolean one = true;

		loop: while (true) {
			// 현재 위치 청소
			if (one) { // 1번을 거쳐야 한다면
				cnt++;
				map[r][c] = -1;
			}
			// 왼쪽 확인
			for (int i = 0; i < 4; i++) {
				if (++d == 4)
					d = 0; // 방향 왼쪽으로
				int nr = r + dx[d];
				int nc = c + dy[d];

				if (nr < 0 || nc < 0 || nr >= N || nc >= M || map[nr][nc] == -1 || map[nr][nc] == 1)
					continue;
				// 청소 가능 하다면
				r = nr;
				c = nc;
				one = true;
				continue loop;
			}
			//이까지 왔으면 4방향 다 확인한거임 
			one=false; //바로 2번으로 갈 수 있게 처리
			r=r-dx[d]; //방향 유지한채 한칸 후진 
			c=c-dy[d]; 
			if (r < 0 || c < 0 || r >= N || c >= M ||  map[r][c] == 1) return cnt;
		}
	}
}

소요시간 : 35분

 

시키는 것만 하면 딱 정답이 나오는 문제입니다.

 

로직 보기 전에 방향만 잡고 들어가면 될 것 같습니다.

문제에서 동,서,남,북기준으로 자신의 진행방향 기준 왼쪽으로 회전한다고 적혀있습니다.

 

그렇다면 dx , dy를 ( 동 , 북, 서, 남 )으로 잡아준다면 방향을 0~3까지 늘려가면 알아서 왼쪽으로 회전하는 효과를 얻을 수 있습니다. 

 

그래서 문제 상 0 1 2 3 을 -> 1 0 3 2로 바꿔줍니다.  ( 동, 북, 서, 남)이 될 수 있게

 

 

로직을 살펴보면

 

 

1. 현재 위치를 청소 + 청소한 cnt 늘려주기

  (boolean을 이용해 1번을 실행할 것인지 안 할 것인지 정했습니다. 만약 2번에서 바로 2번으로 가는 것이면 실행 x)

 

2. 현재 위치에서 현재 방향을 기준으로 왼쪽부터 차례대로 탐색

   a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재하면, 그 방향으로 회전 + 전진 + 1번부터 실행

   - 이때 one이라는 플래그에 true를 줘서 1번을 실행할 수 있게 해 줍니다.

   b. 왼쪽 방향에 공간이 없다면 그 방향으로 회전하고 2번으로 돌아간다.

   - 포문에서 알아서 돌아줍니다

   c. 4방향 모두 청소가 되어있거나, 벽이면 방향 유지하고 한 칸 후진 + 2번

    - 만약 위의 포문을 통고하고 밑으로 내려왔다면 4방향 모두 청소 or벽이기 때문에 한 칸 후진을 하고 

      one 플래그에는 false를 줘서 바로 2번으로 오게 해 줍니다.

   d. 4방향 모두 청소 or벽 + 뒤쪽 방향이 벽이라 후진할 수 없으면 끝