[백준 14503: JAVA] 로봇 청소기

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

14503번: 로봇 청소기

---

[1회차] 11월 12일, 랜덤 문제 돌리기 

문제 접근 방법 (사용 자료구조, 알고리즘)

 

로직(쌉구현)
(0) 현재 칸 청소 ( map에 2로 표현)
(1) 현재 방향을 기준으로 왼쪽 방향의 칸부터 탐색하며 해당 칸이 0인(청소가 가능한 구역) 칸이 존재하는지 확인
   - 존재한다면 2-1 의 조건에 부합하므로 방향과 칸만 이동시키고 청소기 클래스에 있는 isFind를 true 로 설정 후 반복문 종료
(2) isFind 가 true 일 경우, false로 바꿔주고 이후 실행문을 실행하지 않음
(3) 네 방향이 모두 청소되어 있거나 벽인 경우이므로 후진이 가능한지 탐색
   - 가능하다면 방향 유지시킨채로 좌표만 이동
   - 불가능하다면 반복문 종료

 

 

메모리 & 시간

 

 

 

코드

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

public class Main {
	static int N, M, map[][];
	static int dir[][] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
	static Machine v;
	
	static class Machine{
		int x, y, d, cnt;
		boolean isFind;

		public Machine(int x, int y, int d, int cnt, boolean isFind) {
			this.x = x;
			this.y = y;
			this.d = d;
			this.cnt = cnt;
			this.isFind = isFind;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		
		st = new StringTokenizer(in.readLine());
		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		v = new Machine(x, y, d, 0, false);
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		while(true) {
			// 현재 벽 청소 
			if(map[v.x][v.y] != 2) {
				map[v.x][v.y] = 2;
				v.cnt += 1;
			}
			
			// 4방향 반복문
			for (int i = 3; i >= 0; i--) {
				d = (v.d + i) % 4;
				
				int dx = v.x + dir[d][0];
				int dy = v.y + dir[d][1];
				
				if(map[dx][dy] == 0) {
					v = new Machine(dx, dy, d, v.cnt, true);
					break;
				}
			}
			
			if(v.isFind) {
				v.isFind = false;
				continue;
			}
            
			// 4방향 모두 청소했거나 벽인 경우 => 후진 확인
			d = (v.d + 2) % 4;
			if(map[v.x + dir[d][0]][v.y + dir[d][1]] == 1) {
				break;
			} else {
				v = new Machine(v.x + dir[d][0], v.y + dir[d][1], v.d, v.cnt, v.isFind);
			}
		}
			
		System.out.println(v.cnt);
	}
}

 

 

 

 

문제를 푼 시간 (문제 해석 + 문제 접근 + 코드 구현)

문제 해석	문제 접근	코드 구현
10분	10분	30분

 

 

 

 

주의해야 할 점이 널리다 널린 문제

1. 청소기의 초기 위치 (r, c) 가 그대로인지 (r - 1, c - 1)로 넣어야 하는지 헤깔렸음...

2. 청소한 곳을 1로 넣으면 안됨, 어짜피 벽이나 청소를 한 곳이나 똑같지 않나 라고 생각했는데 이 조건 때문에 맨 처음에 틀림

네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

이 경우 이미 청소를 한 곳이더라도 이동할 수 있어야 함... 그래서 청소한 곳은 다른 숫자(2)로 표시를 함

3. 한 번 청소한 곳은 청소를 할 수 없다는 조건에서 청소한 구역 카운트를 하는 조건문을 써주어야 함...