• Feed
  • Explore
  • Ranking
/
/
    Problem Solving

    [CodeTree] AI 로봇청소기

    기출 문제 > 2025 하반기 오후 1번 문제
    ImplementationSimulation코드트리
    h
    hyeonZIP
    2026.02.19
    ·
    7 min read

    https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/ai-robot/description

    import java.io.*;
import java.util.*;

public class Main {
    private static final int[] cy = new int[] { -1, 0, 1, 0 };// 상 우 하 좌
    private static final int[] cx = new int[] { 0, 1, 0, -1 };
    private static final int[] dy = new int[] { -1, 0, 0, 1 };// 상 좌 우 하
    private static final int[] dx = new int[] { 0, -1, 1, 0 };
    private static final int BLOCKED = -1;
    private static final int CLEAN = 0;
    private static final int MAXIMUM_CLEANING_AMOUNT = 20;
    private static final int ACCUMULATING_DUST_AMOUNT = 5;

    private static class Dust {
        private int amount;
        private boolean isPlacedRobot;

        public Dust(int amount, boolean isPlacedRobot) {
            this.amount = amount;
            this.isPlacedRobot = isPlacedRobot;
        }
    }

    private static List<int[]> robotsPosition = new ArrayList<>();
    private static StringBuilder answer = new StringBuilder();
    private static int N, K, L;
    private static Dust[][] map;

    public static void main(String[] args) throws IOException {
        init();
        sol();
        print();
    }

    private static void sol() {
        while (L-- > 0) {
            moveRobots();
            clean();
            accumulateDust();
            spreadDust();
            calculateWholeDustAmount();
        }
    }

    private static void calculateWholeDustAmount() {
        int wholeDustAmount = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (map[i][j].amount > CLEAN) {
                    wholeDustAmount += map[i][j].amount;
                }
            }
        }
        answer.append(wholeDustAmount).append("\n");
    }

    private static void spreadDust() {
        int[][] addMap = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (map[i][j].amount == CLEAN) {
                    int dustAmount = 0;

                    for (int k = 0; k < 4; k++) {
                        int py = i + dy[k];
                        int px = j + dx[k];

                        if (isOutOfRange(py, px) || map[py][px].amount == BLOCKED) {
                            continue;
                        }

                        dustAmount += map[py][px].amount;
                    }
                    addMap[i][j] = dustAmount / 10;
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                map[i][j].amount += addMap[i][j];
            }
        }
    }

    private static void accumulateDust() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (map[i][j].amount > CLEAN) {
                    map[i][j].amount += ACCUMULATING_DUST_AMOUNT;
                }

            }
        }
    }

    private static void clean() {
        for (int[] robotPosition : robotsPosition) {
            List<int[]> maximumCleaningAmountArea = getMaximumCleaningAmounArea(robotPosition[0], robotPosition[1]);

            for (int[] cleaningArea : maximumCleaningAmountArea) {
                int y = cleaningArea[0];
                int x = cleaningArea[1];

                if (map[y][x].amount > MAXIMUM_CLEANING_AMOUNT) {
                    map[y][x].amount -= MAXIMUM_CLEANING_AMOUNT;
                } else {
                    map[y][x].amount = CLEAN;
                }
            }
        }
    }

    private static List<int[]> getMaximumCleaningAmounArea(int currentY, int currentX) {
        List<int[]> maximumCleaningAmountArea = new ArrayList<>();
        int maximumCleaningAmount = Integer.MIN_VALUE;

        int index = 0;

        for (int i = 0; i < 4; i++) {
            List<int[]> cleaningArea = new ArrayList<>();
            int cleaningAmount = 0;
            int idx = index;

            cleaningArea.add(new int[] { currentY, currentX });

            for (int j = 0; j < 3; j++) {
                int nextY = currentY + cy[idx];
                int nextX = currentX + cx[idx];

                if (isOutOfRange(nextY, nextX) || map[nextY][nextX].amount == BLOCKED) {
                    idx = idx + 1 > 3 ? 0 : idx + 1;
                    continue;
                }

                cleaningAmount += map[nextY][nextX].amount > MAXIMUM_CLEANING_AMOUNT
                        ? MAXIMUM_CLEANING_AMOUNT
                        : map[nextY][nextX].amount;
                cleaningArea.add(new int[] { nextY, nextX });

                idx = idx + 1 > 3 ? 0 : idx + 1;
            }

            if (maximumCleaningAmount < cleaningAmount) {
                maximumCleaningAmount = cleaningAmount;
                maximumCleaningAmountArea = cleaningArea;
            }
            index++;
        }

        return maximumCleaningAmountArea;
    }

    private static void moveRobots() {
        List<int[]> newRobotsPosition = new ArrayList<>();
        for (int[] robotPosition : robotsPosition) {

            int currentY = robotPosition[0];
            int currentX = robotPosition[1];

            if (map[currentY][currentX].amount > CLEAN) {
                newRobotsPosition.add(new int[] { currentY, currentX });
                continue;
            }
            int[] nextPosition = bfs(currentY, currentX);

            if (nextPosition.length != 0) {
                int nextY = nextPosition[0];
                int nextX = nextPosition[1];

                newRobotsPosition.add(new int[] { nextY, nextX });

                map[currentY][currentX].isPlacedRobot = false;
                map[nextY][nextX].isPlacedRobot = true;
            } else {
                newRobotsPosition.add(new int[] { currentY, currentX });
            }
        }

        robotsPosition = newRobotsPosition;
    }

    private static int[] bfs(int currentY, int currentX) {
        if (map[currentY][currentX].amount > CLEAN) {
            return new int[] { currentY, currentX };
        }

        Deque<int[]> q = new ArrayDeque<>();
        boolean[][] visited = new boolean[N + 1][N + 1];

        q.offer(new int[] { currentY, currentX, 0 });
        visited[currentY][currentX] = true;

        int minY = Integer.MAX_VALUE;
        int minX = Integer.MAX_VALUE;
        int minDist = Integer.MAX_VALUE;

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int y = current[0];
            int x = current[1];
            int dist = current[2];

            if (dist > minDist) {
                break;
            }

            if (map[y][x].amount > CLEAN && !map[y][x].isPlacedRobot) {
                if (dist < minDist) {
                    minDist = dist;
                    minY = y;
                    minX = x;
                } else if (dist == minDist) {
                    if (y < minY || (y == minY && x < minX)) {
                        minY = y;
                        minX = x;
                    }
                }
                continue;
            }

            for (int i = 0; i < 4; i++) {
                int nextY = y + dy[i];
                int nextX = x + dx[i];

                if (isOutOfRange(nextY, nextX)
                        || visited[nextY][nextX]
                        || map[nextY][nextX].isPlacedRobot == true
                        || map[nextY][nextX].amount == BLOCKED) {
                    continue;
                }

                q.offer(new int[] { nextY, nextX, dist + 1 });
                visited[nextY][nextX] = true;
            }
        }

        if (minDist != Integer.MAX_VALUE) {
            return new int[] { minY, minX };
        }
        return new int[] {};
    }

    private static boolean isOutOfRange(int y, int x) {
        return y <= 0 || x <= 0 || y > N || x > N;
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());// 격자 크기
        K = Integer.parseInt(st.nextToken());// 로봇 청소기의 개수
        L = Integer.parseInt(st.nextToken());// 테스트 횟수

        map = new Dust[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = new Dust(Integer.parseInt(st.nextToken()), false);
            }
        }

        for (int i = 1; i <= K; i++) {
            st = new StringTokenizer(br.readLine());

            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());

            robotsPosition.add(new int[] { y, x });
            map[y][x].isPlacedRobot = true;
        }
    }

    private static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(answer));
        bw.close();
    }
}

    주요 개념

    • 구현

    • 시뮬레이

    주의할 점

    • 각각의 로봇 청소기는 순서대로 이동 거리가 가장 가까운 오염된 격자로 이동합니다.

      • 로봇 청소기의 이동 방법이 정의되어 있지 않지만 상하좌우로만 이동이 가능하도록 생각한다.

      • 초기값으로는 로봇 청소기 밑에는 먼지가 없지만, 두 번째 이동부터는 아래에 먼지가 있을 수 있다.

        • 즉, 이동하지 않을 수도 있다.

      • 또한 가장 가까운 오염된 격자가 없는 경우에 대한 처리가 나와있지 않다.

        • 동일하게 이동하지 않는 경우로 처리했다.

    - 컬렉션 아티클