문제

BOJ 14503, 로봇청소기

핵심

• 입력의 크기가 $50^2$이라 구현에 초점을 맞춘다.
• 로봇 청소기가 얼마나 청소했는지 계산하는 문제이다. 로봇 청소기 위치와 방향을 담을 큐를 선언하고, 하나씩 꺼내와서 처리하는 방식으로 구현하였다. 청소기는 현재 칸의 주변 4칸 중 청소되지 않은 칸이 없는 경우와 있는 경우로 나눠서 작동한다. 따라서 청소되지 않았다면 isDirty = true로 하여 주변 청소 여부를 판단한다.

bool isDirty = false;
for (int direct = 0; direct < 4; ++direct) {
	int ny = y + dy[direct];
	int nx = x + dx[direct];
	if (room[ny][nx] == 0)
		isDirty = true;
}

1. 현재 칸이 청소되지 않은 경우, 현재 칸을 청소한다.

if (room[y][x] == 0) {
	++ans;
	room[y][x] = 2;
}

2. 현재 칸의 주변 4칸 중 청소되지 않은 빈칸이 없는 경우,
   • 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   • 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.

// 주변이 깨끗한 상태, 후진이므로 -연산 한다.
int ny = y - dy[dir];
int nx = x - dx[dir];
if (room[ny][nx] == 1)
	continue;
q.push({ny, nx, dir});

3. 현재 칸의 주변 4칸 중 청소되지 않은 빈칸이 있는 경우,
   • 반시계 방향으로 $90^\circ$ 회전한다.
   • 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈칸인 경우 한 칸 전진한다.
   • 1번으로 돌아간다.

// 주변이 더러운 상태
dir = (dir + 3) % 4;
int ny = y + dy[dir];
int nx = x + dx[dir];
if (room[ny][nx] == 0)
	q.push({ny, nx, dir});
else
	q.push({y, x, dir});

개선

• 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다고 지문에 나와 있다. 문제를 해결할 때는 로봇 청소기 위치가 배열의 범위를 벗어날 수 있다고 생각해서 경곗값을 넘어서는 값에 대해서 따로 처리를 해주었는데 위 지문을 잘 읽어보면 경곗값에 대해선 고려할 필요가 없다.
• 반시계 방향으로 회전시킬 때, dir에 -1을 차감하고 조건문을 사용해 dir이 -1이라면 3으로 바꿔주었다. 모듈러 연산을 이용하면 더 간단하게 표현할 수 있다.

int dir = (dir + 3) % 4;
// 기존
dir -= 1;
if (dir == -1) dir = 3;

코드

시간복잡도

• $O(n\times m)$

C++

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
int room[54][54];
int n, m;
int y, x, dir;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	cin >> y >> x >> dir;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j)
			cin >> room[i][j];
	}
	queue<tuple<int, int, int>> q;
	q.push({y, x, dir});
	int ans = 0;
	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		int y = get<0>(cur);
		int x = get<1>(cur);
		int dir = get<2>(cur);
		if (room[y][x] == 0) {
			++ans;
			room[y][x] = 2;
		}
		bool isDirty = false;
		for (int direct = 0; direct < 4; ++direct) {
			int ny = y + dy[direct];
			int nx = x + dx[direct];
			if (room[ny][nx] == 0)
				isDirty = true;
		}
		if (!isDirty) {
			int ny = y - dy[dir];
			int nx = x - dx[dir];
			if (room[ny][nx] == 1)
				continue;
			q.push({ny, nx, dir});
		} else {
			dir = (dir + 3) % 4;
			int ny = y + dy[dir];
			int nx = x + dx[dir];
			if (room[ny][nx] == 0)
				q.push({ny, nx, dir});
			else
				q.push({y, x, dir});
		}
	}
	cout << ans;
}

Java

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

public class Main {
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};
    static int[][] room = new int[54][54];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int y = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());
        int dir = Integer.parseInt(st.nextToken());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++)
                room[i][j] = Integer.parseInt(st.nextToken());
        }
        int ans = 0;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{y, x, dir});
        while (!q.isEmpty()) {
            var cur = q.poll();
            y = cur[0];
            x = cur[1];
            dir = cur[2];
            if (room[y][x] == 0) {
                ++ans;
                room[y][x] = 2;
            }
            boolean isDirty = false;
            for (int direct = 0; direct < 4; direct++) {
                int ny = y + dy[direct];
                int nx = x + dx[direct];
                if (room[ny][nx] == 0) {
                    isDirty = true;
                    break;
                }
            }
            if (!isDirty) {
                int ny = y - dy[dir];
                int nx = x - dx[dir];
                if (room[ny][nx] == 1)
                    continue;
                q.add(new int[]{ny, nx, dir});
            } else {
                dir = (dir + 3) % 4;
                int ny = y + dy[dir];
                int nx = x + dx[dir];
                if (room[ny][nx] == 0)
                    q.add(new int[]{ny, nx, dir});
                else
                    q.add(new int[]{y, x, dir});
            }
        }
        System.out.println(ans);
        br.close();
    }
}