백준 14503 로봇 청소기 - 삼성 SW 역량 테스트 기출

백준 14503 로봇 청소기  - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

14503번: 로봇 청소기

 

2. 문제 해결에 대한 아이디어

1. 단순 구현 문제긴 하나, 로봇의 움직임이 꽤나 복잡하므로 꼼꼼하게 구현해야 한다.

2. Robot 클래스를 만들어, 위치와 방향을 갖도록 했다.

3. 로봇의 움직임은 회전-> 이동의 두 단계로 구성되어 있다.

   . 먼저 회전을 시키면서 이동할 수 있는 칸이 있는지 탐색한다.

   . 이동할 수 있는 칸이 있으면 그 칸으로 이동한다.

   . 이동할 수 없는 칸(모두 청소 혹은 벽)만 있으면 후진한 후 다시 회전 및 이동을 시작한다.

   . 후진 후에도 이동할 수 있는 칸이 없다면 멈춘다.

   . 멈추고 나서는 2차원 배열 visited를 순회하며 청소되어 있는 칸을 센다.

3. 코드

package boj.로봇청소기_14503;

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

public class Main {

	static int N, M;
	static int[][] board;
	static boolean[][] visited;
	static int[] dirY = { -1, 0, 1, 0 };
	static int[] dirX = { 0, 1, 0, -1 };
	static int r, c, d;
	static Queue<Robot> q = new LinkedList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] nm = br.readLine().split(" ");
		N = Integer.parseInt(nm[0]);
		M = Integer.parseInt(nm[1]);

		String[] rcd = br.readLine().split(" ");
		r = Integer.parseInt(rcd[0]);
		c = Integer.parseInt(rcd[1]);
		d = Integer.parseInt(rcd[2]);
		q.add(new Robot(r, c, d));

		board = new int[N][M];
		visited = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			for (int j = 0; j < M; j++) {
				board[i][j] = Integer.parseInt(line[j]);
			}
		}

		clean();
		System.out.println(count());
	}

	static void clean() {
		while (!q.isEmpty()) {
			Robot now = q.poll();
			int y = now.y;
			int x = now.x;
			int d = now.d;
			visited[y][x] = true;
			// 네방향 돌렸는지 여부
			int breakCounter = 0;
			int yy, xx, dd;
			while (breakCounter < 4) {
				// 왼쪽으로 회전
				if (d == 0) {
					dd = 3;
				} else {
					dd = d - 1;
				}

				yy = y + dirY[dd];
				xx = x + dirX[dd];
				if (yy < 0 || xx < 0 || yy >= N || xx >= M || 
						visited[yy][xx] || board[yy][xx] == 1) {
					d = dd;
					breakCounter++;
				} else {

					q.add(new Robot(yy, xx, dd));
					break;
				}
			}

			// 네 방향 모두 청소되어있거나 벽임 (한바퀴 돌았음)
			if (q.isEmpty()) {
				// 후진해본다
				yy = y - dirY[d];
				xx = x - dirX[d];

				// 후진 불가능하면 끝
				if (yy < 0 || xx < 0 || yy >= N || xx >= M || board[yy][xx] == 1) {
					return;
				}
				// 가능하면 다시 시작
				else {
					q.add(new Robot(yy, xx, d));
				}
			}
		}
	}

	static int count() {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {

				if (visited[i][j])
					cnt++;
			}
		}
		return cnt;
	}
}

class Robot {
	public int y, x, d;

	public Robot(int y, int x, int d) {
		super();
		this.y = y;
		this.x = x;
		this.d = d;
	}

}

 

4. 채점 결과

 

5. 느낀 점

1. 단순 구현이라 시키는 대로 구현하면 되었다.

2. 방향 d의 값에 따라 방향이 매핑되어 있는 게 살짝 귀찮았다.