문제
https://www.acmicpc.net/problem/17144
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Problem_17144 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] condition = br.readLine().split("\\s+");
int r = Integer.parseInt(condition[0]);
int c = Integer.parseInt(condition[1]);
int t = Integer.parseInt(condition[2]);
int[][] arr = new int[r][c];
int[][] outLine = new int[r+2][c+2];
int a = 0, b = 0;
for(int i=0; i<r; i++) {
String[] tmp = br.readLine().split("\\s+");
int k=0;
for(int j=0; j<c; j++) {
arr[i][j] = Integer.parseInt(tmp[k]);
k++;
if(arr[i][j]==-1) {
a = i-1;
b = i;
}
}
}
for(int i=0; i<r+2; i++) {
for(int j=0; j<c+2; j++) {
if(i==0 || i==r+1 || j==0 || j==c+1) outLine[i][j] = -1;
else outLine[i][j] = arr[i-1][j-1];
}
}
for(int k=t; k>0; k--) {
int[][] origin = outLine;
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++) {
if(origin[i+1][j+1] != 0 || origin[i+1][j+1] != -1) {
if(origin[i][j+1] != -1) {
arr[i-1][j] += origin[i+1][j+1]/5;
arr[i][j] -= origin[i+1][j+1]/5;
}
if(origin[i+1][j+2] != -1) {
arr[i][j+1] += origin[i+1][j+1]/5;
arr[i][j] -= origin[i+1][j+1]/5;
}
if(origin[i+2][j+1] != -1) {
arr[i+1][j] += origin[i+1][j+1]/5;
arr[i][j] -= origin[i+1][j+1]/5;
}
if(origin[i+1][j] != -1) {
arr[i][j-1] += origin[i+1][j+1]/5;
arr[i][j] -= origin[i+1][j+1]/5;
}
}
}
}
int[][] copy = arr;
for(int i=a-1; i>0; i--) {
arr[i][0] = copy[i-1][0];
}
for(int i=b+1; i<r-1; i++) {
arr[i][0] = copy[i+1][0];
}
for(int i=0; i<c-1; i++) {
arr[0][i] = copy[0][i+1];
arr[r-1][i] = copy[r-1][i+1];
}
for(int i=0; i<a; i++) {
arr[i][c-1] = copy[i+1][c-1];
}
for(int i=r-1; i>b; i--) {
arr[i][c-1] = copy[i-1][c-1];
}
for(int j=c-1; j>1; j--) {
arr[a][j] = copy[a][j-1];
arr[b][j] = copy[b][j-1];
}
arr[a][1] = 0;
arr[b][1] = 0;
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++) {
origin[i+1][j+1] = arr[i][j];
}
}
}
int ans = 0;
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++) {
if(arr[i][j]!=-1 && arr[i][j]!=0) ans += arr[i][j];
}
}
System.out.print(ans);
}
}우선 미세먼지량이 담겨있는 배열보다 행과열 각각 2줄씩 더 큰 배열을 하나 만든다. 미세먼지가 분포될 때 더이상 배열 인덱스가 없다면 분포가 되지 않도록 해야 하기 때문에 경계를 체크하는 용도로 사용할 것이다. 기존 미세먼지 배열을 사용해도 되겠지만 그렇게 하려면 ArrayIndexOutOfBoundsException을 관리해야 할 것이다.
-1 -1 -1 -1 -1
-1 0 2 5 -1
-1 8 1 0 -1
-1 -1 0 0 -1
-1 -1 3 0 -1
-1 -1 -1 -1 -1공기 청정기의 값도 -1로 들어가기 때문에 배열의 값이 -1일 때 로직을 수행하지 않을 수 있다.
추후 계산을 편하게 하기위해 변수 a b에 공기청정기의 행 인덱스를 저장해놓았다.
int[][] origin = outLine;
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++) {
if(origin[i+1][j+1] != 0 || origin[i+1][j+1] != -1) {
if(origin[i][j+1] != -1) {
arr[i-1][j] += origin[i+1][j+1]/5;
arr[i][j] -= origin[i+1][j+1]/5;
}
if(origin[i+1][j+2] != -1) {
arr[i][j+1] += origin[i+1][j+1]/5;
arr[i][j] -= origin[i+1][j+1]/5;
}
if(origin[i+2][j+1] != -1) {
arr[i+1][j] += origin[i+1][j+1]/5;
arr[i][j] -= origin[i+1][j+1]/5;
}
if(origin[i+1][j] != -1) {
arr[i][j-1] += origin[i+1][j+1]/5;
arr[i][j] -= origin[i+1][j+1]/5;
}
}
}
}for문을 돌면서 계속해서 계산이 이루어지고 미세먼지 분포는 계산전의 기존 총량을 가지고 계속 계산을 해야 하기 때문에 값을 변경시키지 않는 복사본 배열을 하나 생성한다.
그리고 좌우상하 위치에 대해 미세먼지를 분포시키는 계산을 해주는데 이때 outLine의 배열 인덱스와 미세먼지 배열의 인덱스를 잘 생각해서 계산하여야 한다.
int[][] copy = arr;
for(int i=a-1; i>0; i--) {
arr[i][0] = copy[i-1][0];
}
for(int i=b+1; i<r-1; i++) {
arr[i][0] = copy[i+1][0];
}
for(int i=0; i<c-1; i++) {
arr[0][i] = copy[0][i+1];
arr[r-1][i] = copy[r-1][i+1];
}
for(int i=0; i<a; i++) {
arr[i][c-1] = copy[i+1][c-1];
}
for(int i=r-1; i>b; i--) {
arr[i][c-1] = copy[i-1][c-1];
}
for(int j=c-1; j>1; j--) {
arr[a][j] = copy[a][j-1];
arr[b][j] = copy[b][j-1];
}
arr[a][1] = 0;
arr[b][1] = 0;
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++) {
origin[i+1][j+1] = arr[i][j];
}
}이제 공기청정기에 의한 이동을 구현한다.
여기서도 마찬가지로 미세먼지의 값들이 배열 이동을 위해 복사본을 만들어 배열을 2개 운용한다.
처음 이동시키는 것은 공기청정기 쪽으로 들어가는 열이다. 역순으로 진행한 이유는 배열이 이동하면서 끝부분의 값들은 인덱스를 벗어나게 되므로 사라지게 된다. 하지만 실제로는 위나 아래로 값이 이동해야 하기 때문에 역순으로 진행해야 값이 사라지는 것을 막을 수 있기 때문이다.
위 아래로 움직이는 로직은 계산방법이 달라 시계방향과 시계반대방향에 대해 분리해서 계산했지만 좌우 움직임에 대한 로직은 다를 것이 없기 때문에 같은 for문에서 계산을 수행했다.
미세먼지가 모두 이동하게되면 한번의 프로세스가 끝난 것이고 같은 프로세스를 반복하게 된다.
다음 프로세스가 반복되기 전에 처음에 만들었던 outLine배열을 방금 완료된 프로세스의 결과물들로 업데이트 시켜주면 끝이다.
맺음
크게 어려운 문제는 아니었지만 시간이 꽤 오래걸렸다. 복잡한 논리보다는 귀찮은 코드가 많아서 그랬던 것 같다.
Git
