[코드트리 - L13] 25년 상반기 오후 1번 미생물 연구

 

 

 

코딩테스트 기출 문제 제출: 미생물 연구 | 코드트리

 

 

문제풀이

1. 미생물 투입

• 이미 해당 위치에 다른 미생물이 있다면 새로 투입된 미생물만 남는다.
• 기존에 있던 미생물 A가 새로 투입된 B에 먹혀, 2 이상의 그룹으로 나뉜다면 A는 모두 사라진다.

2. 배양용기 이동

• 가장 넓은 영역을 가진 미생물 선택한다. 둘 이상이면, 먼저 투입된 미생물을 선택한다.
• 기존 형태를 유지한 채로 다른 미생물이랑 겹치지 않게 (최대한 작은 x , 최대한 작은 y)로 이동한다.
• 어디도 둘 수 없다면 사라진다.

3. 실험 결과

• 모든 인접한 무리쌍을 확인한다. 이 때, 두 무리 A와 B가 맞닿은 면이 둘 이상이더라도 (A, B) 쌍은 한 번만 확인합니다.
• 확인하는 두 무리가 A, B라면 (미생물 A의 영역의 넓이) × (미생물 B의 영역의 넓이) 만큼의 성과를 얻는다.
• 모든 쌍의 성과를 더한 것이 정답이다.

 

1. 미생물 투입

for (int i = sx; i < ex; i++) {
	for (int j = sy; j < ey; j++) {
		map[i][j] = t + 1;
	}
}

 

 

2. 투입 이후 2개 이상의 그룹으로 나뉘는 지 DFS로 확인

for (int i = 1; i <= t; i++) {
	if (isSplit(i)) {
		remove(i);
	}
}

private static boolean isSplit(int target) {

	boolean[][] visited = new boolean[N][N];
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!visited[i][j] && map[i][j] == target) {
				dfs(i, j, target, visited);
				cnt++;

				if (cnt >= 2)
					return true;
			}
		}
	}
	return false;
}

static void dfs(int x, int y, int target, boolean[][] visited) {

	visited[x][y] = true;

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

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

		if (!visited[nx][ny] && target == map[nx][ny]) {
			dfs(nx, ny, target, visited);
		}
	}
}

 

 

3. 배양 용기를 이동한다.

• 배양용기를 이동시키기 전, 그룹끼리 정렬하기 위해서 그룹을 형성해준다.

private static List<Group> getGroups() {

	boolean[][] visited = new boolean[N][N];
	List<Group> groups = new ArrayList<>();

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] != 0 && !visited[i][j]) {
				groups.add(bfs(i, j, visited));
			}
		}
	}

	return groups;
}

 

• 그룹을 넓이 순, 먼저 투입된 순으로 정렬한다.
• 그룹 내 가장 작은 위치인 (minX, minY)로 거리를 이동시킨다.
  • ex) (2, 3) => (0, 0) 으로 이동시켜야 한다면, 모든 다른 좌표들을 (2, 3)만큼 빼주면 모양 유지한 채 이동할 수 있다.

static void moveGroups() {
		
        List<Group> groups = getGroups();

		// 그룹 정렬
		groups.sort((a, b) -> {
			if (a.size != b.size)
				return b.size - a.size; // 큰 넓이 순
			return a.id - b.id; // 먼저 투입된 것부터
		});

		int[][] newMap = new int[N][N];

		for (Group g : groups) {

			boolean placed = false;

			// 위치 탐색
			for (int x = 0; x < N && !placed; x++) {
				for (int y = 0; y < N && !placed; y++) {

					boolean canPlace = true;

					for (int[] cell : g.cells) {

						int nx = x + (cell[0] - g.minX);
						int ny = y + (cell[1] - g.minY);

						// 범위 넘거나 이미 있다면 이동 불가
						if (nx < 0 || ny < 0 || nx >= N || ny >= N) {
							canPlace = false;
							break;
						}

						if (newMap[nx][ny] != 0) {
							canPlace = false;
							break;
						}

					}

					if (canPlace) {
						for (int[] cell : g.cells) {
							int nx = x + (cell[0] - g.minX);
							int ny = y + (cell[1] - g.minY);
							newMap[nx][ny] = g.id;
						}
						placed = true;
					}
				}
			}
		}

		map = newMap;
	}

 

 

4. 실험 결과 기록

• 이 부분은 좀 감이 안잡혀서 AI에게 물어봤다. ㅎㅎ
• 아래와 오른쪽 부분에 다른 그룹이 있는 지 체크한 후, (A 그룹 ID, B 그룹 ID) 로 쌍들을 Set에 넣는다.
• 아랫부분과 오른쪽 부분만 체크하는 이유는 2번 그룹의 오른쪽에서 (2, 3)의 쌍이 있다면, 3번 그룹의 왼쪽에서도 (3, 2) 쌍이 있기 때문에 중복된다.

static void result() {

		// 그룹별 넓이 계산
		Map<Integer, Integer> sizeMap = new HashMap<>();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] != 0) {
					sizeMap.put(map[i][j], sizeMap.getOrDefault(map[i][j], 0) + 1);
				}
			}
		}

		int result = 0;
		Set<String> seen = new HashSet<>();

		// 인접 체크
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 0)
					continue;

				int cur = map[i][j];

				// 오른쪽이 0 아닌 다른 값일 때
				if (j + 1 < N && map[i][j + 1] != 0 && map[i][j + 1] != cur) {
					int next = map[i][j + 1];

					int a = Math.min(cur, next);
					int b = Math.max(cur, next);

					String key = a + "," + b;

					if (!seen.contains(key)) {
						result += sizeMap.get(a) * sizeMap.get(b);
						seen.add(key);
					}
				}

				// 아래
				if (i + 1 < N && map[i + 1][j] != 0 && map[i + 1][j] != cur) {
					int next = map[i + 1][j];

					int a = Math.min(cur, next);
					int b = Math.max(cur, next);

					String key = a + "," + b;

					if (!seen.contains(key)) {
						result += sizeMap.get(a) * sizeMap.get(b);
						seen.add(key);
					}

				}

			}

		}
		System.out.println(result);
	}

 

 

---

•  

 

전체코드

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

public class Main {

	static class Group {
		int id;
		int size;
		int minX, minY;
		List<int[]> cells = new ArrayList<>();
	}

	static int N, Q;
	static int[][] map;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

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

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

		N = Integer.parseInt(input[0]);
		Q = Integer.parseInt(input[1]);

		map = new int[N][N];
		for (int t = 0; t < Q; t++) {

			input = br.readLine().split(" ");
			int sx = Integer.parseInt(input[0]);
			int sy = Integer.parseInt(input[1]);
			int ex = Integer.parseInt(input[2]);
			int ey = Integer.parseInt(input[3]);

			// 1. 미생물 투입
			for (int i = sx; i < ex; i++) {
				for (int j = sy; j < ey; j++) {
					map[i][j] = t + 1;
				}
			}
			// 2. 둘 이상으로 나뉘는 지 확인
			for (int i = 1; i <= t; i++) {
				if (isSplit(i)) {
					remove(i);
				}
			}

			// 3. 배양 용기 이동: 가장 넓은 미생물무터 가장 작은 x, 가장 작은 y, 둘 공간이 없으면 사라짐
			moveGroups();

			// 4. 실험 성과: 인접한 무리별 넓이 쌍 더하기
			result();

		}

	}

	private static void result() {

		// 그룹별 넓이 계산
		Map<Integer, Integer> sizeMap = new HashMap<>();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] != 0) {
					sizeMap.put(map[i][j], sizeMap.getOrDefault(map[i][j], 0) + 1);
				}
			}
		}

		int result = 0;
		Set<String> seen = new HashSet<>();

		// 인접 체크
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 0)
					continue;

				int cur = map[i][j];

				// 오른쪽이 0 아닌 다른 값일 때
				if (j + 1 < N && map[i][j + 1] != 0 && map[i][j + 1] != cur) {
					int next = map[i][j + 1];

					int a = Math.min(cur, next);
					int b = Math.max(cur, next);

					String key = a + "," + b;

					if (!seen.contains(key)) {
						result += sizeMap.get(a) * sizeMap.get(b);
						seen.add(key);
					}
				}

				// 아래
				if (i + 1 < N && map[i + 1][j] != 0 && map[i + 1][j] != cur) {
					int next = map[i + 1][j];

					int a = Math.min(cur, next);
					int b = Math.max(cur, next);

					String key = a + "," + b;

					if (!seen.contains(key)) {
						result += sizeMap.get(a) * sizeMap.get(b);
						seen.add(key);
					}

				}

			}

		}
		System.out.println(result);
	}

	private static void moveGroups() {
		List<Group> groups = getGroups();

		// 그룹 정렬
		groups.sort((a, b) -> {
			if (a.size != b.size)
				return b.size - a.size; // 큰 넓이 순
			return a.id - b.id; // 먼저 투입된 것부터
		});

		int[][] newMap = new int[N][N];

		for (Group g : groups) {

			boolean placed = false;

			// 위치 탐색
			for (int x = 0; x < N && !placed; x++) {
				for (int y = 0; y < N && !placed; y++) {

					boolean canPlace = true;

					for (int[] cell : g.cells) {

						int nx = x + (cell[0] - g.minX);
						int ny = y + (cell[1] - g.minY);

						// 범위 넘거나 이미 있다면 이동 불가
						if (nx < 0 || ny < 0 || nx >= N || ny >= N) {
							canPlace = false;
							break;
						}

						if (newMap[nx][ny] != 0) {
							canPlace = false;
							break;
						}

					}

					if (canPlace) {
						for (int[] cell : g.cells) {
							int nx = x + (cell[0] - g.minX);
							int ny = y + (cell[1] - g.minY);
							newMap[nx][ny] = g.id;
						}
						placed = true;
					}
				}
			}
		}

		map = newMap;
	}

	private static List<Group> getGroups() {

		boolean[][] visited = new boolean[N][N];
		List<Group> groups = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] != 0 && !visited[i][j]) {
					groups.add(bfs(i, j, visited));
				}
			}
		}

		return groups;
	}

	private static Group bfs(int x, int y, boolean[][] visited) {

		Queue<int[]> q = new ArrayDeque<>();
		q.add(new int[] { x, y });
		visited[x][y] = true;

		Group g = new Group();
		g.id = map[x][y];
		g.size = 0;
		g.minX = x;
		g.minY = y;

		while (!q.isEmpty()) {

			int[] cur = q.poll();
			x = cur[0];
			y = cur[1];

			g.cells.add(new int[] { x, y });
			g.size++;

			if (x < g.minX || (x == g.minX && y < g.minY)) { // x가 작거나, 같다면 y가 더 작은 것
				g.minX = x;
				g.minY = y;
			}

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

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

				if (!visited[nx][ny] && g.id == map[nx][ny]) {
					visited[nx][ny] = true;
					q.add(new int[] { nx, ny });
				}
			}

		}

		return g;
	}

	static void remove(int target) {
		for (int x = 0; x < N; x++) {
			for (int y = 0; y < N; y++) {
				if (map[x][y] == target) {
					map[x][y] = 0;
				}
			}
		}
	}

	private static boolean isSplit(int target) {

		boolean[][] visited = new boolean[N][N];
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visited[i][j] && map[i][j] == target) {
					dfs(i, j, target, visited);
					cnt++;

					if (cnt >= 2)
						return true;
				}
			}
		}

		return false;
	}

	private static void dfs(int x, int y, int target, boolean[][] visited) {

		visited[x][y] = true;

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

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

			if (!visited[nx][ny] && target == map[nx][ny]) {
				dfs(nx, ny, target, visited);
			}
		}

	}

}