https://www.acmicpc.net/problem/17144
문제 접근
R * C 크기의 격자판에서 T초 동안 미세먼지의 확산과 공기청정기의 작동이라는 두 가지 현상이 반복될 때, T초 후 남아있는 미세먼지의 총량을 계산하는 문제이다.
이 문제는 각 단계별로 주어진 조건에 따라 상태를 변화시키는 전형적인 시뮬레이션 문제이다.
위 문제의 핵심은 두 가지이다.
1. 동시 확산 : 모든 칸의 미세먼지가 동시에 확산되는 현상을 어떻게 처리할 것인지
2. 공기 순환 : 공기청정기 바람에 의해 미세먼지가 정해진 경로로 한 칸씩 이동하는 것을 어떻게 구현할 것인가.
위 두가지를 T번 반복하여 최종 상태를 구하는 것이 목표이다.
제약 조건
- 보드 크기 : 6 <= R, C <= 50
- 시간 : 1 <= T <= 1,000
보드의 최대 크기는 2500이고, 시간은 1000이다.
한 번의 시뮬레이션(1초)에서 모든 칸을 순회하며 확산(R * C)시키고, 공기청정기를 작동(R * C)시키는 연산을 수행한다고 가정하면 총 연산량은 대략 T (RC + R*C)이다.
-> 1000 * (2500 + 2500) = 5,000,000으로 O(TRC) 복잡도의 알고리즘으로 충분히 시간 내에 해결 가능하다.
문제 설계
전체 프로세스
입력 및 초기화
R, C, T와 격자판의 초기 미세먼지 상태(int[][] matrix)를 입력받는다.
공기 청정기의 위치(airCleanerTop, airCleanerBottom)을 찾아 저장
시뮬레이션 반복
T초 동안 아래의 두 함수를 순서대로 호출하는 for문을 실행
spread(): 미세먼지 확산을 시뮬레이션한다.cleanerOn(): 공기청정기 작동을 시뮬레이션 한다.
결과 계산
T초가 지난 후 matrix 배열에 남아 있는 모든 미세먼지의 양을 합산
결과 출력
계산된 총 미세먼지 양을 출력한다.
자료구조 및 함수 정의
전역 변수
int R, C, T: 격자판 크기와 시간int[][] matrix: 각 칸의 미세먼지 양을 저장하는 2차원 배열, 공기청정기는-1로 표현된다.int airCleanerTop,airCleanerBottom: 위쪽, 아래쪽 공기청정기의 행(row) 위치int[] dr, dc: 상하좌우 방향 탐색을 위한 배열
함수
spread(): 1초 동안의 미세먼지 확산을 처리하는 함수cleanerOn(): 1초 동안의 공기청정기 작동(순환)을 처리하는 함수
설계 근거
확산 처리에 임시 배열을 사용하는 이유
문제에서 미세먼지 확산은 "모든 칸에서 동시에 일어난다"고 되어 있음 -> 병렬처리를 요구함
만약 matrix 배열을 직접 수정하면서 확산을 진행하면 이후 확산하는 미세먼지가 이미 더해진 값을 기준으로 계산하게 됨 -> 동시 조건에 위배됨
따라서 올바른 동시 확산을 구현하기 위해 다음과 같은 방법 사용
1. 읽기 전용으로 원본 matrix를 순회하며 각 칸의 결과를 계산
2. 이 계산 결과를 별도의 임시 2차원 배열(int[][] tmp)에 기록
3. 모든 칸에 대한 계산이 끝나면, tmp배열을 matrix에 덮어씌워 1초 후의 상태를 한 번에 갱신
구현 코드
초기 설정 및 메인 로직
public static void main(String[] args) throws IOException {
// 1. 입력 및 초기화
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
T = Integer.parseInt(st.nextToken());
matrix = new int[R][C];
boolean isCleanerFound = false;
for (int i = 0; i < R; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < C; j++) {
matrix[i][j] = Integer.parseInt(st.nextToken());
if (matrix[i][j] == -1 && !isCleanerFound) {
airCleanerTop = i;
airCleanerBottom = i + 1;
isCleanerFound = true;
}
}
}
// 2. 시뮬레이션 루프
for (int i = 0; i < T; i++) {
spread();
cleanerOn();
}
// 3. 결과 계산 및 출력
int totalDust = 0;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (matrix[i][j] > 0) {
totalDust += matrix[i][j];
}
}
}
System.out.println(totalDust);
}- 입력 및 초기화 :
R,C,T와 격자판 정보를 빠르게 입력받아matrix배열을 채운다. 공기청정기(-1)를 발견하면airCleanerTop,airCleanerBottom변수에 그 위치를 한번만 저장한다. - 시뮬레이션 루프 :
for (int i = 0; i < T; i++)루프를 통해T초동안spread()와cleanerOn()함수를 순서대로 호출하여 시간의 흐름에 따라 상태 변화를 반곱함 - 결과 계산 및 출력 : 루프가 끝나면, 최종 상태인
matrix배열을 순회하며-1이 아닌 모든 값을 더해 방에 남은 미세먼지의 총량을 계산하고 출력한다.
미세먼지 확산
public static void spread() {
int[][] tmp = new int[R][C];
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (matrix[r][c] == -1) {
tmp[r][c] = -1;
continue;
}
int remainingDust = matrix[r][c];
int spreadAmount = matrix[r][c] / 5;
for (int dir = 0; dir < 4; dir++) {
int nr = r + dr[dir];
int nc = c + dc[dir];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || matrix[nr][nc] == -1) {
continue;
}
tmp[nr][nc] += spreadAmount;
remainingDust -= spreadAmount;
}
tmp[r][c] += remainingDust;
}
}
matrix = tmp;
}- 임시 배열 생성 :
int[][] tmp배열을 생성, 이 배열은1초 후의 격자판 상태를 임시로 저장하는 버퍼 역할을 함 - 전체 칸 순회 : 이중 for문으로
matrix의 모든 칸을 순회하며 확산될 양을 계산 - 4방향 확산 : 안쪽 for문으로 상하좌우 인접 칸을 확인한다. 인접 칸이 격자판 범위 안이고 공기 청정기가 아니라면,
tmp배열의 해당 위치에 확산될 양(spreadAmount)을 더해준다. - 남은 먼지 계산 : 확산되고 남은 먼지(
remainingDust)를 계산하여tmp배열의 현재 위치[r][c]에 더해준다. - 상태 갱신 : 모든 칸의 계산이 끝나면
1초 후의 상태가 완성된tmp배열을matrix변수에 대입하여 상태를 한번에 갱신함
공기청정기 작동(cleanerOn)
public static void cleanerOn() {
int top = airCleanerTop;
// 위쪽 (반시계)
for (int r = top - 1; r > 0; r--) matrix[r][0] = matrix[r - 1][0];
for (int c = 0; c < C - 1; c++) matrix[0][c] = matrix[0][c + 1];
for (int r = 0; r < top; r++) matrix[r][C - 1] = matrix[r + 1][C - 1];
for (int c = C - 1; c > 1; c--) matrix[top][c] = matrix[top][c - 1];
matrix[top][1] = 0;
int bottom = airCleanerBottom;
// 아래쪽 (시계)
for (int r = bottom + 1; r < R - 1; r++) matrix[r][0] = matrix[r + 1][0];
for (int c = 0; c < C - 1; c++) matrix[R - 1][c] = matrix[R - 1][c + 1];
for (int r = R - 1; r > bottom; r--) matrix[r][C - 1] = matrix[r - 1][C - 1];
for (int c = C - 1; c > 1; c--) matrix[bottom][c] = matrix[bottom][c - 1];
matrix[bottom][1] = 0;
}- 한칸씩 당기기 위해 역으로 먼지를 한칸씩 당기는 방식으로 진행
- 위쪽 공기청정기(반시계) : 시계방향으로 움직이며 한칸씩 땡긴 후 마지막에 공기청정기에 저장되는 먼지 양을 초기화함
- 아래 공기청정기(시계) : 반시계방향으로 움직이며 한칸씩 땡긴 후 마지막에 공기청정기에 저장된 먼지 양을 초기화함
피드백
초기 접근(비효율적)
미세먼지가 있는 곳만 HashMap으로 관리하면 효율적이지 않을까?
-> 확산이 일어나면 미세먼지는 거의 모든 칸으로 퍼져나가기 때문에 HashMap의 장점이 사라진다. 또한 공기 순환처럼 위치 기반 연속 데이터 이동을 구현할 때 HashMap을 사용할 경우 구현이 매우 복잡하고 비효율적임
또한 HashMap으로 관리할 경우 key값을 2차원 배열의 i, j 좌표값을 String 형태로 가지는데
매번 참조할 때마다 i, j의 String key를 생성해 주기 때문에 시간적으로 부담이 생김(String 객체 생성 + hashCode 비교 연산)
HashMap으로 구현(TimeOut 발생)
package BOJ.gold;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;
public class gold4_17144_미세먼지_TimeOut2 {
static class Dust {
int count;
ArrayDeque<Integer> queue;
public Dust(int count, ArrayDeque<Integer> queue) {
this.count = count;
this.queue = queue;
}
}
static int R, C, T;
static int[][] matrix;
static List<String> airCleaner;
static Map<String, Dust> map;
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
static int total;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
T = Integer.parseInt(st.nextToken());
matrix = new int[R][C];
airCleaner = new ArrayList<>();
map = new HashMap<>();
total = 0;
for (int i = 0; i < R; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < C; j++) {
int num = Integer.parseInt(st.nextToken());
if (num == -1) {
airCleaner.add(i + "," + j);
} else if (num != 0) {
map.put(i + "," + j, new Dust(num, new ArrayDeque<>()));
}
}
}
for (int i = 0; i < T; i++) {
spread();
cleanerOn();
}
// 남아있는 먼지 양 구하기
for (Dust dust : map.values()) {
total += dust.count;
}
System.out.println(total);
} // main
// 미세먼지 확산
public static void spread() {
// map의 크기만큼 순회
Map<String, Dust> tmpMap = new HashMap<>();
// 복제
for(String key : map.keySet()) {
Dust dust = map.get(key);
tmpMap.put(key, dust);
}
for (String key : map.keySet()) {
// 키값으로 value 값을 가져옴
Dust dust = tmpMap.get(key);
int tmp = 0;
// 5미만이면 확산될 먼지가 없음
if (dust.count < 5) {
continue;
}
// 키값을 , 기준으로 쪼개 r, c 좌표 가져오기
StringTokenizer st = new StringTokenizer(key, ",");
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
// 4방향 탐색
for (int dir = 0; dir < 4; dir++) {
int nr = r + dr[dir];
int nc = c + dc[dir];
// 범위 안이거나 공기청정기가 아닌 지역이어야 함
if (nr >= 0 && nr < R && nc >= 0 && nc < C && !airCleaner.contains(nr + "," + nc)) {
// 임시 맵에 dust 생성
if (tmpMap.get(nr + "," + nc) == null) {
tmpMap.put(nr + "," + nc, new Dust(0, new ArrayDeque<>()));
}
// 해당 지역의 dust를 가져오기
Dust newDust = tmpMap.get(nr + "," + nc);
// queue에 dust의 count / 5 만큼 추가 하고 tmp값 1 증가
newDust.queue.offer(dust.count / 5);
tmp++;
}
}
// 탐색 이후 현재 지역의 먼지값 계산
int newCnt = dust.count;
newCnt -= dust.count/5 * tmp;
dust.count = newCnt;
}
map.clear();
// map으로 다시 옮겨담기
for(String key : tmpMap.keySet()) {
Dust dust = tmpMap.get(key);
map.put(key, dust);
}
// 다시 순회하면서 dust의 queue안의 dust 값 더해주기
for (Dust dust : map.values()) {
int newCnt = dust.count;
while(!dust.queue.isEmpty()) {
newCnt += dust.queue.poll();
}
dust.count = newCnt;
}
}
// 공기청정기 작동
public static void cleanerOn() {
StringTokenizer st;
// 공기청정기 위 아래 분리
String ac1 = airCleaner.get(0);
st = new StringTokenizer(ac1, ",");
int r1 = Integer.parseInt(st.nextToken());
int c1 = Integer.parseInt(st.nextToken());
String ac2 = airCleaner.get(1);
st = new StringTokenizer(ac2, ",");
int r2 = Integer.parseInt(st.nextToken());
int c2 = Integer.parseInt(st.nextToken());
// 역으로 한칸씩 당김
// 위는 반시계방향으로 먼지를 밀어냄
// 위에서 아래로
for (int r = r1 - 1; r > 0; r--) {
moveDust(r - 1, 0, r, 0);
}
// 오른쪽에서 왼쪽
for (int c = 0; c < C - 1; c++) {
moveDust(0, c + 1, 0, c);
}
// 아래에서 위로
for (int r = 0; r < r1; r++) {
moveDust(r + 1, C - 1, r, C - 1);
}
// 왼쪽에서 오른쪽으로
for (int c = C - 1; c > 1; c--) {
moveDust(r1, c - 1, r1, c);
}
map.remove(r1 + "," + c1);
// 아래쪽
for (int r = r2 + 1; r < R - 1; r++) {
moveDust(r + 1, 0, r, 0);
}
for (int c = 0; c < C - 1; c++) {
moveDust(R - 1, c + 1, R - 1, c);
}
for (int r = R - 1; r > r2; r--) {
moveDust(r - 1, C - 1, r, C - 1);
}
for (int c = C - 1; c > 1; c--) {
moveDust(r2, c - 1, r2, c);
}
map.remove(r2 + "," + 1);
}
public static void moveDust(int fromR, int fromC, int toR, int toC) {
String fromKey = fromR + "," + fromC;
String toKey = toR + "," + toC;
if (map.containsKey(fromKey)) {
Dust dustToMove = map.get(fromKey);
map.put(toKey, dustToMove);
map.remove(fromKey);
} else {
map.remove(toKey);
}
}
}회고
오랜만에 구현문제를 풀어봤는데 확실히 다른 문제들보다 설계를 코드로 구현하는 과정이 많이 어렵고 까다로운것 같다. 또한 구현문제의 경우 조건을 체크하고 설계한 코드의 시간복잡도 및 공간복잡도 계산이 다른 알고리즘 문제들보다 까다로운거 같아 문제를 더 풀어보면서 감각을 익히는 것이 중요할 것 같다.
안녕하세요