[백준/14503/Java] 로봇청소기

 

 

문제:

www.acmicpc.net/problem/14503

14503번: 로봇 청소기

 

문제를 먼저 풀고 오시는 것을 추천합니다.
이 문제의 풀이는 BFS 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다.

 

 

문제분석

로봇청소기의 작동방식을 이해하고 그대로 정확히 구현하는 것이 중요합니다.

 

로봇청소기는 바라보는 방향이 있으며, 동, 서, 남, 북 중 하나로 이동할 수 있습니다.

또한, 이미 청소되어 있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없습니다.

 

로봇청소기는 다음과 같이 작동합니다.

1. 현재 위치를 청소합니다.

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

  a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행합니다.

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

  c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아갑니다.

  d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춥니다.

 

 

입력

첫째 줄에 세로 크기 N과 가로 크기 M이 주어집니다.

둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어집니다.

  d = 0 : 북쪽

  d = 1 : 동쪽

  d = 2 : 남쪽

  d = 3 : 서쪽

셋째 줄부터 N개의 줄에 장소의 상태가 주어지며 빈칸은 0, 벽은 1로 주어집니다.

지도의 첫 행, 마지막 행, 첫 열, 나머지 열에 있는 모든 칸은 벽입니다.

로봇 청소기가 청소하는 칸의 상태는 항상 빈 칸입니다.

 

출력

로봇 청소기가 청소하는 칸의 개수를 출력한다.

 

풀이

로봇청소기는 현재 칸 청소를 먼저 합니다.

그리고 진행방향의 왼쪽부터 시작하여 네 방향 중 청소가 가능한 칸을 찾습니다.

청소가 가능한 칸을 만나면 그 칸을 이동하고 청소부터 반복합니다.

여기서 왼쪽 방향은 북쪽 0을 제외하고 -1을 하면 구할 수 있는 값입니다.

  d = 0 : 북쪽의 왼쪽 방향은 서쪽 3입니다.

  d = 1 : 동쪽의 왼쪽 방향은 북쪽 0입니다.

  d = 2 : 남쪽의 왼쪽 방향은 동쪽 1입니다.

  d = 3 : 서쪽의 왼쪽 방향은 남쪽 2입니다.

 

네 방향 청소가 모두 되어 있거나 벽으로 되어 있어서 이동할 수 없으면 진행하던 방향의 반대방향으로 후진합니다.

  d = 0 : 북쪽의 후진방향은 남쪽입니다. (i+1, j)

  d = 1 : 동쪽의 후진방향은 서쪽입니다. (i, j-1)

  d = 2 : 남쪽의 후진방향은 북쪽입니다. (i-1, j)

  d = 3 : 서쪽의 후진방향은 동쪽입니다. (i, j+1)

 

더이상 이동할 곳이 없고 후진도 불가능하면 종료합니다.

 

 

예제풀이

문제에 있는 예제는 시작하자마자 끝나거나 지도가 커서 풀이해보기에 너무 큽니다.

그래서 제가 크기를 줄여서 4x4 크기로 예제를 만들어보았습니다.

 

 

 

 

시작

우측 상단 노란색이 시작지점이고 남쪽 방향을 바라보도록 하였습니다.

0은 청소 가능이며, 1은 벽입니다.

 

방문배열은 따로 사용하지 않고 청소한 곳을 지도배열에서 2로 변경하였습니다.

 

 

한 칸 이동

남쪽 방향의 왼쪽 방향부터 청소할 곳을 찾습니다.

동쪽, 북쪽은 길이 없고 서쪽은 벽입니다. 따라서, 남쪽 방향으로 이동하게 됩니다.

 

두번째 칸 이동

남쪽 방향의 왼쪽 방향부터 청소할 곳을 찾습니다.

동쪽은 길이 없고 북쪽은 이미 청소한 곳입니다. 따라서, 서쪽 방향으로 이동하게 됩니다.

 

네번째 칸까지 이동

진행 방향의 왼쪽 방향으로 청소할 곳을 탐색하면서 이동하다보면 길이 막히게 됩니다.

 

 

 

후진

더이상 진행할 곳이 없으므로 진행방향인 남쪽의 반대방향 북쪽으로 한 칸 후진합니다.

그러나 더 이상 이동할 곳이 없어서 작동을 중지합니다.

 

 

소스

입력받은 정보는 A배열에 저장하였고 방문배열을 따로 선언하지 않았습니다.

진행방향의 왼쪽부터 검색하도록 하는 getNextD 함수를 선언하여 사용하였습니다.

북쪽을 제외하고 -1을 하면 됩니다.

청소할 때마다 이동수를 더하여 ANS 변수에 저장합니다.

 

이동하지 않았으면 진행방향의 반대방향으로 한 칸 후진합니다.

큐가 모두 비게 되면 더 이상 이동할 곳이 없으므로 이동수를 출력하고 종료합니다.

 

bfs 함수 안에 있는 주석처리된 print 구문으로 A 배열이 변화하는 값을 확인할 수 있습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static int N, M;

	public static int[][] A;

	public static int ANS = 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.valueOf(st.nextToken());
		M = Integer.valueOf(st.nextToken());

		A = new int[N][M];

		st = new StringTokenizer(br.readLine());
		int r = Integer.valueOf(st.nextToken());
		int c = Integer.valueOf(st.nextToken());
		int d = Integer.valueOf(st.nextToken());
		Vacuum vacuum = new Vacuum(r, c, d);

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				A[i][j] = Integer.valueOf(st.nextToken());
			}
		}

		bfs(vacuum);

		System.out.println(ANS);
	}

	private static void bfs(Vacuum v) {
		Queue<Vacuum> q = new LinkedList<Vacuum>();

		q.add(v);
		while (q.isEmpty() == false)
		{
			v = q.remove();
			
			// 왼쪽 방향 설정
			int r = v.r;
			int c = v.c;
			
			if (A[r][c] == 0) ANS++;	// 청소가 가능하면 청소칸수 증가
			A[r][c] = 2;	// 청소기가 지나간 자리 설정
			
//			for (int i = 0; i < N; i++) {
//				System.out.println(Arrays.toString(A[i]));
//			}
//			System.out.println(v);
//			System.out.println();
			
			// 네방향 검색
			boolean find = false;
			int nextD = v.d;
			for (int i = 0; i < 4; i++) {
				if (find == true) {
					break;
				}
				nextD = getNextD(nextD); 
				if (nextD == 0 && r > 0 && A[r-1][c] == 0) { // 북쪽
					q.add(new Vacuum(r-1, c, nextD));
					find = true;
				}
				else if (nextD == 1 && c < M - 1 && A[r][c+1] == 0) { // 동쪽
					q.add(new Vacuum(r, c+1, nextD));
					find = true;
				}
				else if (nextD == 2 && r < N - 1 && A[r+1][c] == 0) { // 남쪽
					q.add(new Vacuum(r+1, c, nextD));
					find = true;
				}
				else if (nextD == 3 && c > 0 && A[r][c-1] == 0) { // 서쪽
					q.add(new Vacuum(r, c-1, nextD));
					find = true;
				}
			}
			
			if (find == false)
			{
				// 네방향 모두 청소가 할 곳이 없으면 한 칸 후진
				int d = v.d;
				if (d == 0 && r < N-1 && A[r+1][c] != 1) { // 북쪽 -> 남쪽
					q.add(new Vacuum(r+1, c, d));
				}
				else if (d == 1 && c > 0 && A[r][c-1] != 1) { // 동쪽 -> 서쪽
					q.add(new Vacuum(r, c-1, d));
				}
				else if (d == 2 && r > 0 && A[r-1][c] != 1) { // 남쪽 -> 북쪽
					q.add(new Vacuum(r-1, c, d));
				}
				else if (d == 3 && c<M-1 && A[r][c+1] != 1) { // 서쪽 -> 동쪽
					q.add(new Vacuum(r, c+1, d));
				}
			}
		}
	}

	private static int getNextD(int d) {
		if (d == 0)
			return 3;
		return d - 1;
	}
}

class Vacuum {
	int r; // i 좌표
	int c; // j 좌표
	int d; // 방향

	Vacuum(int r, int c, int d) {
		set(r, c, d);
	}

	public void set(int r, int c, int d) {
		this.r = r;
		this.c = c;
		this.d = d;
	}

	@Override
	public String toString() {
		return "(" + r + ", " + c + ", " + d + ")";
	}
}