들어가며
https://www.acmicpc.net/problem/17144
문제 지문이 꽤 길다. 디테일한 부분은 링크 타고 들어가서 확인하길 바란다.
크게 두가지를 요구하는 문제이다.
1. 미세먼지 확산
2. 공기청정기 돌리기
이런 과정을 T번 반복한 후에 총 미세먼지의 양을 정답으로 출력하면 되는 문제이다.
본론으로
솔직히 왜 골드4인지 모르겠는 시뮬레이션+구현 문제이다. 구현하면서 범위나 겹치는 부분이 없는가를 체크해야하는 부분이 너무 많아서 정말 땀 삐질삐질 흘려가며 작성했다.
public class Main {
static int[] dy = {-1, 0, 1, 0};
static int[] dx = {0, 1, 0, -1};
static int Y, X, T, ret;
static int[][] maps, visited;
static int cleanerY;
static void dustGo() {
// 동시에 퍼져야 하기에 각각 퍼지는 값을 visited 배열에 축적하고 원본배열은 마이너스
for (int i = 0; i < Y; i++) {
for (int j = 0; j < X; j++) {
if (maps[i][j] != 0) {
int dDust = maps[i][j] / 5;
for (int k = 0; k < 4; k++) {
int ny = i + dy[k];
int nx = j + dx[k];
if (!canGo(ny, nx)) {
continue;
}
visited[ny][nx] += dDust;
maps[i][j] -= dDust;
}
}
}
}
// 원본배열에 퍼진 값 더해주기
for (int i = 0; i < Y; i++) {
for (int j = 0; j < X; j++) {
maps[i][j] += visited[i][j];
}
}
}
static void cleanUp() { // 위쪽은 반시계방향
//왼쪽부분 아래로 땡기기
for (int i = cleanerY - 1; i >= 0; i--) {
if (maps[i + 1][0] == -1) {
maps[i][0] = 0;
continue;
}
maps[i + 1][0] = maps[i][0];
maps[i][0] = 0;
}
// 윗부분 왼쪽으로 한칸씩
for (int i = 0; i < X - 1; i++) {
maps[0][i] = maps[0][i + 1];
maps[0][i + 1] = 0;
}
// 오른쪽부분 위로 땡기기
for (int i = 1; i <= cleanerY; i++) {
maps[i - 1][X - 1] = maps[i][X - 1];
maps[i][X - 1] = 0;
}
// 아래부분 오른쪽으로 땡기기
for (int i = X - 2; i >= 1; i--) {
maps[cleanerY][i + 1] = maps[cleanerY][i];
maps[cleanerY][i] = 0;
}
}
static void cleanDown() { // 아래쪽은 시계방향
int cleanerDownY = cleanerY + 1;
// 왼쪽부분 위로 땡기기
for (int i = cleanerDownY + 1; i <= Y - 1; i++) {
if (maps[i - 1][0] == -1) {
maps[i][0] = 0;
continue;
}
maps[i - 1][0] = maps[i][0];
maps[i][0] = 0;
}
// 아랫부분 왼쪽으로 땡기기
for (int i = 1; i <= X - 1; i++) {
maps[Y - 1][i - 1] = maps[Y - 1][i];
maps[Y - 1][i] = 0;
}
// 오른쪽부분 아래로 땡기기
for (int i = Y - 2; i >= cleanerDownY; i--) {
maps[i + 1][X - 1] = maps[i][X - 1];
maps[i][X - 1] = 0;
}
// 위쪽부분 오른쪽으로 땡기기
for (int i = X - 2; i >= 1; i--) {
maps[cleanerDownY][i + 1] = maps[cleanerDownY][i];
maps[cleanerDownY][i] = 0;
}
}
static boolean canGo(int y, int x) {
if (y < 0 || x < 0 || y >= Y || x >= X || maps[y][x] == -1) {
return false;
}
return true;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
Y = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken());
T = Integer.parseInt(st.nextToken());
maps = new int[Y][X];
cleanerY = 0;
for (int i = 0; i < Y; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < X; j++) {
int num = Integer.parseInt(st.nextToken());
if (num == -1 && cleanerY == 0) { // 공기청정기는 위의 y값만 저장
cleanerY = i;
}
maps[i][j] = num;
}
}
while (T-- > 0) {
visited = new int[Y][X];
dustGo();
cleanUp();
cleanDown();
}
for (int i = 0; i < Y; i++) {
for (int j = 0; j < X; j++) {
if (maps[i][j] == 0 || maps[i][j] == -1) {
continue;
}
ret += maps[i][j];
}
}
System.out.println(ret);
}
}
동시에 확산?
특히 문제에서 미세먼지가 동시에 확산된다는 것을 처음에 신경안쓰고 했다가, 자꾸 덮어씌어져서 고생좀 했다..ㅎㅎ
그래서 원본 배열 maps의 감소와 확산을 분리시켜주기 위해서 visited 배열에 확산값을 축적한다음, 다 탐색 이후 한번에 더해주었다. 주석을 적어놓았다.
static void dustGo() {
// 동시에 퍼져야 하기에 각각 퍼지는 값을 visited 배열에 축적하고 원본배열은 마이너스
for (int i = 0; i < Y; i++) {
for (int j = 0; j < X; j++) {
if (maps[i][j] != 0) {
int dDust = maps[i][j] / 5;
for (int k = 0; k < 4; k++) {
int ny = i + dy[k];
int nx = j + dx[k];
if (!canGo(ny, nx)) {
continue;
}
visited[ny][nx] += dDust;
maps[i][j] -= dDust;
}
}
}
}
// 원본배열에 퍼진 값 더해주기
for (int i = 0; i < Y; i++) {
for (int j = 0; j < X; j++) {
maps[i][j] += visited[i][j];
}
}
}시계방향, 반시계 방향 구현
아래의 사진처럼 공기청정기 로직 구현하는게 너무너무 어려웠다!!!! 배열의 회전은 구현해봤어도, 이렇게 일정 부분만 회전하는 것을 구현하니 머리가 찌끈찌끈 했다..ㅎㅎ.
마무리하며
정말정말 왜 골드4인지 이해가 안가는 문제였다.. 너무 어려웠다. 내가 시뮬레이션 문제를 많이 안풀어본 탓이겠지..
코테 경향이 점점 구현이나 시뮬레이션 위주로 변해가고 있다고 들려온다. 그럴수록 이런 인덱스 기반의 구현을 잘 할수 있지 않아야겠는가!!! 시뮬레이션 문제는 정말 많이 풀어보며 감각을 키우는 게 답인 것 같다. 파이팅 🔥