[코드트리 - L13] 25년 하반기 오후 1번 AI 로봇청소기

코딩테스트 기출 문제 해설: AI 로봇청소기 | 코드트리

코딩테스트 기출 문제 AI 로봇청소기의 상세 해설과 예시 코드를 제공합니다. 다양한 접근 방식과 최적화 전략을 학습하세요.

www.codetree.ai

문제

L번 동안 아래 함수들을 수행해 총 먼지양 구하는 문제

1. 청소기 이동

이동 거리가 가장 가까운 오염된 격자로 이동
가까운 격자가 여러 개일 경우, 행 번호가 곳으로 이동하고, 행 번호도 같을 경우 열 번호가 작은 격자로 이동한다.

2. 청소하기

현재위치, 왼쪽, 위쪽, 오른쪽 격자를 청소할 수 있다. ( 예시: ㅓ, ㅗ, ㅏ, ㅜ 모양)
위 4가지 격자의 먼지 합 중 가장 큰 방향에서 청소를 시작한다.
각 칸당 청소할 수 있는 최대 먼지량은 20

3. 먼지 축적

먼지가 있는 모든 격자에 +5

4. 먼지 확산

깨끗한 격자에 (주변 4방향 격자의 먼지량의 합 / 10)의 값만 큼 확산된다.

제출 코드

주의할 점

map[i][j] > 0 인 부분만 계산해야한다. ( -1은 벽)
청소한 후에 청소기를 다음으로 이동할 수 있게 다시 큐에 넣어주어야 한다.
bfs 함수에서 null을 리턴할 때 또한 처리해주어야 한다.

1. 청소기 이동

static void moveDust() {

	occupied = new boolean[N][N];
	for (Node v : vaccume) {
		occupied[v.x][v.y] = true;
	}

	// 로봇 청소기에서 => 각 먼지별이동 거리
	for (int i = 0; i < K; i++) {
		Node node = vaccume.poll();

		// 이동할 청소기 false로 변경
		occupied[node.x][node.y] = false;
		Node near = bfs(node.x, node.y);

		if (near != null) {
			occupied[near.x][near.y] = true;
			vaccume.offer(new Node(near.x, near.y));
		} else {
			// 이동 못하면 원위치
			occupied[node.x][node.y] = true;
			vaccume.offer(node);
		}
	}
}

static Node bfs(int x, int y) {

		PriorityQueue<Dust> pq = new PriorityQueue<>();
		pq.offer(new Dust(x, y, 0));

		boolean[][] visited = new boolean[N][N];
		visited[x][y] = true;

		while (!pq.isEmpty()) {

			Dust cur = pq.poll();

			// 발견 시 바로 반환
			if (map[cur.x][cur.y] > 0) {
				return new Node(cur.x, cur.y);
			}

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];

				if (nx < 0 || ny < 0 || nx >= N || ny >= N)
					continue;

				if (!visited[nx][ny] && !occupied[nx][ny] && map[nx][ny] >= 0) {
					visited[nx][ny] = true;
					pq.offer(new Dust(nx, ny, cur.dist + 1));

				}
			}

		}

		return null;
	}

2. 청소하기

static void clean() {

		// 주변에서 가장 큰 먼지량 방향에서 청소시작

		for (int i = 0; i < vaccume.size(); i++) {
			Node node = vaccume.poll();

			int maxSum = -1;
			int bestDir = 0;

			// 방향별 합을 계산
			for (int d = 0; d < 4; d++) {

				int sum = Math.min(20, map[node.x][node.y]);

				// 오른쪽
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];

				if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] > 0) {
					sum += Math.min(20, map[nx][ny]);
				}

				// 아래쪽
				int dir = (d + 1) % 4;
				nx = node.x + dx[dir];
				ny = node.y + dy[dir];

				if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] > 0) {
					sum += Math.min(20, map[nx][ny]);
				}
				// 위쪽
				dir = (d + 3) % 4;
				nx = node.x + dx[dir];
				ny = node.y + dy[dir];

				if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] > 0) {
					sum += Math.min(20, map[nx][ny]);
				}

				if (sum > maxSum) {
					maxSum = sum;
					bestDir = d;
				}

			}

			// bestDir로 청소
			Set<String> cleaned = new HashSet<>();

			// 현재
			cleaned.add(node.x + "," + node.y);

			// 전방
			int nx = node.x + dx[bestDir];
			int ny = node.y + dy[bestDir];

			if (nx >= 0 && nx < N && ny >= 0 && ny < N)
				cleaned.add(nx + "," + ny);

			// 오른쪽
			nx = node.x + dx[(bestDir + 1) % 4];
			ny = node.y + dy[(bestDir + 1) % 4];

			if (nx >= 0 && nx < N && ny >= 0 && ny < N)
				cleaned.add(nx + "," + ny);

			// 왼쪽
			nx = node.x + dx[(bestDir + 3) % 4];
			ny = node.y + dy[(bestDir + 3) % 4];

			if (nx >= 0 && nx < N && ny >= 0 && ny < N)
				cleaned.add(nx + "," + ny);

			// 청소
			for (String s : cleaned) {
				String[] sp = s.split(",");
				int x = Integer.parseInt(sp[0]);
				int y = Integer.parseInt(sp[1]);

				if (map[x][y] > 0) {
					map[x][y] -= Math.min(20, map[x][y]);
				}
			}

			// 다시 넣기(중요!)
			vaccume.offer(node);
		}

	}

Set 대신 바로 제거해도 괜찮다.

// bestDir로 청소
// 현재
if (map[node.x][node.y] > 0)
map[node.x][node.y] -= Math.min(20, map[node.x][node.y]);

// 전방
int nx = node.x + dx[bestDir];
int ny = node.y + dy[bestDir];

if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] > 0)
	map[nx][ny] -= Math.min(20, map[nx][ny]);

// 오른쪽
nx = node.x + dx[(bestDir + 1) % 4];
ny = node.y + dy[(bestDir + 1) % 4];

if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] > 0)
	map[nx][ny] -= Math.min(20, map[nx][ny]);

// 왼쪽
nx = node.x + dx[(bestDir + 3) % 4];
ny = node.y + dy[(bestDir + 3) % 4];

if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] > 0)
	map[nx][ny] -= Math.min(20, map[nx][ny]);

3. 먼지 축적

static void addDust() {

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] > 0) {
					map[i][j] += 5;
				}
			}
		}
	}

4. 먼지 확산

static void spread() {

		int[][] tmp = new int[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				tmp[i][j] = map[i][j];
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 0) {
					int sum = 0;
					for (int d = 0; d < 4; d++) {
						int nx = i + dx[d];
						int ny = j + dy[d];

						if (nx < 0 || ny < 0 || nx >= N || ny >= N)
							continue;

						if (map[nx][ny] > 0) {
							sum += map[nx][ny];
						}
					}

					if (sum > 0)
						tmp[i][j] += (int) sum / 10;
				}
			}
		}
		map = tmp;
	}

전체 코드


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static class Dust implements Comparable<Dust> {
		int x, y, dist;

		Dust(int x, int y, int dist) {
			this.x = x;
			this.y = y;
			this.dist = dist;
		}

		@Override
		public int compareTo(Dust o) {
			if (this.dist != o.dist) {
				return this.dist - o.dist; // 거리 우선
			}
			if (this.x != o.x) {
				return this.x - o.x; // 행
			}
			return this.y - o.y; // 열
		}

	}

	static class Node implements Comparable<Node> {
		int x, y;

		Node(int x, int y) {
			this.x = x;
			this.y = y;
		}

		@Override
		public int compareTo(Node o) {
			if (this.x != o.x) {
				return this.x - o.x; // 행 기준
			}
			return this.y - o.y; // 열 기준
		}

	}

	static int N, K, L;
	static int[][] map;
	static Queue<Node> vaccume;
	static boolean[][] occupied;
	static int[] dx = { 0, 1, 0, -1 }; // 시계방향(우하좌상)
	static int[] dy = { 1, 0, -1, 0 };

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input;

		input = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		K = Integer.parseInt(input[1]); // 청소기 수
		L = Integer.parseInt(input[2]); // 테스트 수

		map = new int[N][N];

		// 먼지 있거나, 없거나 + 물건
		for (int i = 0; i < N; i++) {
			input = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(input[j]);
			}
		}

		// 로봇 청소기 위치
		vaccume = new ArrayDeque<>();
		for (int i = 0; i < K; i++) {
			input = br.readLine().split(" ");
			int x = Integer.parseInt(input[0]) - 1;
			int y = Integer.parseInt(input[1]) - 1;
			vaccume.offer(new Node(x, y));
		}

		while (L > 0) {
			moveDust();
			clean();
			addDust();
			spread();
			L--;
			System.out.println(totalDust());

		}

	}

	private static int totalDust() {

		int sum = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] > 0) {
					sum += map[i][j];
				}
			}
		}

		return sum;
	}

	static void moveDust() {

		occupied = new boolean[N][N];
		for (Node v : vaccume) {
			occupied[v.x][v.y] = true;
		}

		// 로봇 청소기에서 => 각 먼지별이동 거리
		for (int i = 0; i < K; i++) {

			Node node = vaccume.poll();

			// 이동할 청소기 false로 변경
			occupied[node.x][node.y] = false;
			Node near = bfs(node.x, node.y);

			if (near != null) {
				occupied[near.x][near.y] = true;
				vaccume.offer(new Node(near.x, near.y));
			} else {
				// 이동 못하면 원위치
				occupied[node.x][node.y] = true;
				vaccume.offer(node);
			}

		}

	}

	static Node bfs(int x, int y) {

		PriorityQueue<Dust> pq = new PriorityQueue<>();
		pq.offer(new Dust(x, y, 0));

		boolean[][] visited = new boolean[N][N];
		visited[x][y] = true;

		while (!pq.isEmpty()) {

			Dust cur = pq.poll();

			// 발견 시 바로 반환
			if (map[cur.x][cur.y] > 0) {
				return new Node(cur.x, cur.y);
			}

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];

				if (nx < 0 || ny < 0 || nx >= N || ny >= N)
					continue;

				if (!visited[nx][ny] && !occupied[nx][ny] && map[nx][ny] >= 0) {
					visited[nx][ny] = true;
					pq.offer(new Dust(nx, ny, cur.dist + 1));

				}
			}

		}

		return null;
	}

	static void clean() {

		// 주변에서 가장 큰 먼지량 방향에서 청소시작

		for (int i = 0; i < vaccume.size(); i++) {
			Node node = vaccume.poll();

			int maxSum = -1;
			int bestDir = 0;

			// 방향별 합을 계산
			for (int d = 0; d < 4; d++) {

				int sum = Math.min(20, map[node.x][node.y]);

				// 오른쪽
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];

				if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] > 0) {
					sum += Math.min(20, map[nx][ny]);
				}

				// 아래쪽
				int dir = (d + 1) % 4;
				nx = node.x + dx[dir];
				ny = node.y + dy[dir];

				if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] > 0) {
					sum += Math.min(20, map[nx][ny]);
				}
				// 위쪽
				dir = (d + 3) % 4;
				nx = node.x + dx[dir];
				ny = node.y + dy[dir];

				if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] > 0) {
					sum += Math.min(20, map[nx][ny]);
				}

				if (sum > maxSum) {
					maxSum = sum;
					bestDir = d;
				}

			}

			// bestDir로 청소
			// 현재
			if (map[node.x][node.y] > 0)
				map[node.x][node.y] -= Math.min(20, map[node.x][node.y]);
			// 전방
			int nx = node.x + dx[bestDir];
			int ny = node.y + dy[bestDir];

			if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] > 0)
			    map[nx][ny] -= Math.min(20, map[nx][ny]);

			// 오른쪽
			nx = node.x + dx[(bestDir + 1) % 4];
			ny = node.y + dy[(bestDir + 1) % 4];

			if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] > 0)
			    map[nx][ny] -= Math.min(20, map[nx][ny]);

			// 왼쪽
			nx = node.x + dx[(bestDir + 3) % 4];
			ny = node.y + dy[(bestDir + 3) % 4];

			if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] > 0)
			    map[nx][ny] -= Math.min(20, map[nx][ny]);
				
			// 다시 넣기(중요!)
			vaccume.offer(node);
		}

	}

	static void addDust() {

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] > 0) {
					map[i][j] += 5;
				}
			}
		}
	}

	static void spread() {

		int[][] tmp = new int[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				tmp[i][j] = map[i][j];
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 0) {
					int sum = 0;
					for (int d = 0; d < 4; d++) {
						int nx = i + dx[d];
						int ny = j + dy[d];

						if (nx < 0 || ny < 0 || nx >= N || ny >= N)
							continue;

						if (map[nx][ny] > 0) {
							sum += map[nx][ny];
						}
					}

					if (sum > 0)
						tmp[i][j] += (int) sum / 10;
				}
			}
		}
		map = tmp;
	}

}

저작자표시 비영리 변경금지 (새창열림)

'알고리즘' 카테고리의 다른 글

[코드트리 - L13] 25년 상반기 오후 1번 미생물 연구 (1)	2026.04.09
[코드트리 - L12] 25년 상반기 오전 1번 민트초코우유 (1)	2026.04.08
[코드트리 - L12] 25년 하반기 오전 1번 문제 - 택배 하차 (0)	2026.04.07
[알고리즘] 시간 복잡도 & 공간 복잡도 (0)	2026.04.05
[백준 - G3] 20058. 마법사 상어와 파이어스톰 (5)	2026.03.28

문제

제출 코드

1. 청소기 이동

2. 청소하기

3. 먼지 축적

4. 먼지 확산

전체 코드

'알고리즘' 카테고리의 다른 글

티스토리툴바