문제 설명
구현 문제로, 미세먼지를 확산시키는 과정은 일반적으로 그래프 탐색에서 사용하는 방법으로 코드를 구현하면 된다. 다만, 자신이 확산시키는 것과 인접한 칸에서 확산되어서 오는 값을 합할 때, 현재 누적값으로 확산하는 것이 아닌 원래 가지고 있던 값을 확신시켜야 한다. 이어서, 바람의 방향대로 한칸씩 값을 밀어야 하는데 바람이 처음 나오는 칸이 0이 되기 때문에 역순으로 반복해서 구현했다.
문제 풀이(정답)
import java.util.*;
import java.io.*;
public class Main {
static int[][][] map;
static int[][] cleaner = new int[2][2];
static Queue<Node> dust = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
map = new int[r][c][2];
int temp = 0;
for (int i = 0; i < r; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < c; j++) {
map[i][j][0] = Integer.parseInt(st.nextToken());
if (map[i][j][0] == -1) {
// 공기 청정기의 위치
cleaner[temp][0] = i;
cleaner[temp][1] = j;
temp++;
} else if (map[i][j][0] != 0) {
dust.add(new Node(i, j));
}
}
}
// 공기 청정기 위아래 확인
if (cleaner[0][1] < cleaner[1][1]) {
temp = cleaner[0][1];
cleaner[0][1] = cleaner[1][1];
cleaner[1][1] = temp;
}
// n초 후 새로운 Q를 넣기전 먼지가 확산된 상태 list
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
int result = 0;
for (int i = 0; i < t; i++) {
Set<Node> check = new HashSet<>();
while (!dust.isEmpty()) {
Node current = dust.poll();
// 값이 업데이트(먼지) 되야하는 list int divideValue = map[current.getR()][current.getC()][0] / 5;
int cnt = 0;
for (int j = 0; j < 4; j++) {
int nr = current.getR() + dr[j];
int nc = current.getC() + dc[j];
if (nr >= 0 && nr < r && nc >= 0 && nc < c && map[nr][nc][0] != -1) {
map[nr][nc][1] += divideValue;
check.add(new Node(nr, nc));
cnt++;
}
}
map[current.getR()][current.getC()][0] -= (divideValue * cnt);
if (map[current.getR()][current.getC()][0] > 0) {
check.add(new Node(current.getR(), current.getC()));
}
}
for (Node node : check) {
int nr = node.getR();
int nc = node.getC();
map[nr][nc][0] += map[nr][nc][1];
map[nr][nc][1] = 0;
}
// 공기청정기 작동 (상단 반시계방향)
int upper = cleaner[0][0];
for (int j = upper - 1; j > 0; j--) {
map[j][0][0] = map[j - 1][0][0];
}
for (int j = 0; j < c - 1; j++) {
map[0][j][0] = map[0][j + 1][0];
}
for (int j = 0; j < upper; j++) {
map[j][c - 1][0] = map[j + 1][c - 1][0];
}
for (int j = c - 1; j > 1; j--) {
map[upper][j][0] = map[upper][j - 1][0];
}
map[upper][1][0] = 0; // 공기청정기에서 나오는 바람
// 공기청정기 작동 (하단 시계방향)
int lower = cleaner[1][0];
for (int j = lower + 1; j < r - 1; j++) {
map[j][0][0] = map[j + 1][0][0];
}
for (int j = 0; j < c - 1; j++) {
map[r - 1][j][0] = map[r - 1][j + 1][0];
}
for (int j = r - 1; j > lower; j--) {
map[j][c - 1][0] = map[j - 1][c - 1][0];
}
for (int j = c - 1; j > 1; j--) {
map[lower][j][0] = map[lower][j - 1][0];
}
map[lower][1][0] = 0; // 공기청정기에서 나오는 바람
for (int j = 0; j < r; j++) {
for (int k = 0; k < c; k++) {
if(map[j][k][0] > 0){
if(i == t-1){
result += map[j][k][0];
}else{
dust.add(new Node(j, k));
}
}
}
}
}
System.out.println(result);
br.close();
}
static class Node {
int r;
int c;
public Node(int r, int c) {
this.r = r;
this.c = c;
}
int getR() {
return this.r;
}
int getC() {
return this.c;
}
}
}미세먼지 확산
...
map = new int[r][c][2];
...
Set<Node> check = new HashSet<>();
while (!dust.isEmpty()) {
Node current = dust.poll();
// 값이 업데이트(먼지) 되야하는 list
int divideValue = map[current.getR()][current.getC()][0] / 5;
int cnt = 0;
for (int j = 0; j < 4; j++) {
int nr = current.getR() + dr[j];
int nc = current.getC() + dc[j];
if (nr >= 0 && nr < r && nc >= 0 && nc < c && map[nr][nc][0] != -1) {
map[nr][nc][1] += divideValue;
check.add(new Node(nr, nc));
cnt++;
}
}
map[current.getR()][current.getC()][0] -= (divideValue * cnt);
if (map[current.getR()][current.getC()][0] > 0) {
check.add(new Node(current.getR(), current.getC()));
}
}
for (Node node : check) {
int nr = node.getR();
int nc = node.getC();
map[nr][nc][0] += map[nr][nc][1];
map[nr][nc][1] = 0;
} - 입력받은 row, col의 크기와 한 차원을 추가해 3차원 배열로 선언했다. 이유는 다음과 같다.
map[r][c][0]는 현재 미세먼지 값, 즉 해당 칸이 확산할 때 사용할 미세먼지의 값이다.map[r][c][1]는 다른 인접한 칸으로 인해 확산된 값을 누적해서 더한 값이다.
- 이전에 입력시, dust에 Node 객체로 미세먼지가 있는 위치를 add 해두었기 때문에 q가 빌때까지 반복한다.
- 4방향으로 미세먼지 확산 연산을 해준 이후, 미세먼지 값이 있는 칸을 hashSet에 넣어
map[r][c][1]확산을 통해 얻은 값과map[r][c][0]확산하고 남은 값을 더한다.
공기청정기 동작
// 공기청정기 작동 (상단 반시계방향)
int upper = cleaner[0][0];
for (int j = upper - 1; j > 0; j--) {
map[j][0][0] = map[j - 1][0][0];
}
for (int j = 0; j < c - 1; j++) {
map[0][j][0] = map[0][j + 1][0];
}
for (int j = 0; j < upper; j++) {
map[j][c - 1][0] = map[j + 1][c - 1][0];
}
for (int j = c - 1; j > 1; j--) {
map[upper][j][0] = map[upper][j - 1][0];
}
map[upper][1][0] = 0; // 공기청정기에서 나오는 바람
// 공기청정기 작동 (하단 시계방향)
int lower = cleaner[1][0];
for (int j = lower + 1; j < r - 1; j++) {
map[j][0][0] = map[j + 1][0][0];
}
for (int j = 0; j < c - 1; j++) {
map[r - 1][j][0] = map[r - 1][j + 1][0];
}
for (int j = r - 1; j > lower; j--) {
map[j][c - 1][0] = map[j - 1][c - 1][0];
}
for (int j = c - 1; j > 1; j--) {
map[lower][j][0] = map[lower][j - 1][0];
}
map[lower][1][0] = 0; // 공기청정기에서 나오는 바람- 공기청정기가 나온 방향은 0이 되기 때문에 공기청정기로 들어오는 쪽부터 연산을 해서 한칸씩 값을 밀어서 미세먼지 값을 업데이트 한다.
결과 출력 및 다음 초 연산 준비
for (int j = 0; j < r; j++) {
for (int k = 0; k < c; k++) {
if(map[j][k][0] > 0){
if(i == t-1){
result += map[j][k][0];
}else{
dust.add(new Node(j, k));
}
}
}
}
System.out.println(result); - 반복해서 현재 result에 값을 누적해서 저장한다. 현재 실행중인 로직이 마지막 연산일 때는 해당 연산을, 아닐 경우에는 다음 초에서 확인할 미세먼지의 위치를 node객체로 dust(queue)에 추가한다.
결과
정답은 맞았지만 다른 사람들의 제출 결과를 보니 메모리와 시간이 비교적 높은 것을 알 수 있었다. 그래서 다른 코드들을 참고해서 좀 더 개선된 코드를 만들어봤다.
코드 개선
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
int[][] map = new int[r][c];
int[][] cleaner = new int[2][2];
int temp = 0;
for (int i = 0; i < r; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < c; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == -1) {
cleaner[temp][0] = i;
cleaner[temp][1] = j;
temp++;
}
}
}
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
while (t-- > 0) {
int[][] check = new int[r][c];
// 확산 상태 채크
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (map[i][j] > 0) {
check[i][j] = map[i][j];
}
}
}
// 확산
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (check[i][j] > 0) {
for (int k = 0; k < 4; k++) {
int nr = i + dr[k];
int nc = j + dc[k];
if (nr >= 0 && nr < r && nc >= 0 && nc < c && map[nr][nc] != -1) {
map[nr][nc] = map[nr][nc] + check[i][j] / 5;
map[i][j] = map[i][j] - (check[i][j] / 5);
}
}
}
}
}
int upper = cleaner[0][0]; // ex 2
for (int i = upper - 1; i > 0; i--) {
map[i][0] = map[i - 1][0];
}
for (int i = 0; i < c - 1; i++) {
map[0][i] = map[0][i + 1];
}
for (int i = 0; i< upper; i++){
map[i][c-1] = map[i+1][c-1];
}
for(int i = c-1; i>1; i--){
map[upper][i] = map[upper][i-1];
}
map[upper][1] =0;
int lower = cleaner[1][0];
for (int j = lower + 1; j < r - 1; j++) {
map[j][0] = map[j + 1][0];
}
for (int j = 0; j < c - 1; j++) {
map[r - 1][j] = map[r - 1][j + 1];
}
for (int j = r - 1; j > lower; j--) {
map[j][c - 1] = map[j - 1][c - 1];
}
for (int j = c - 1; j > 1; j--) {
map[lower][j] = map[lower][j - 1];
}
map[lower][1] = 0;
}
int result = 0;
for(int i=0; i< r; i++){
for(int j=0; j< c; j++){
if(map[i][j] != -1){
result += map[i][j];
}
}
}
System.out.println(result);
br.close();
}
}
- 대부분의 연산 과정은 동일하지만 일단 Queue를 사용하지 않고 매번 반복문을 통해 미세먼지가 있는 부분을 찾아서 확산하도록 코드를 변경했다.
if (nr >= 0 && nr < r && nc >= 0 && nc < c && map[nr][nc] != -1) {
map[nr][nc] = map[nr][nc] + check[i][j] / 5;
map[i][j] = map[i][j] - (check[i][j] / 5);
}- 추가로 3차원 배열을 사용하지 않고 매초마다 현재 미세먼지 값을 측정하는 2차원 배열을 만들어, 해당 배열을 사용해 미세먼지가 있는 위치 및 확산에 사용할 미세먼지의 값을 계산하는데 이용해 간결하게 코드를 수정했다.
결론
공기청정기 작동시키는 동작에서 생각보다 오래 시간이 걸렸다. 코드를 개선해보며 결과적으로, 가장 먼저 작성했더 코드에 비해
메모리는 약 1/7배 , 시간은 2000ms 넘게 감소시켰다. 맞은 것도 물론 중요하지만, 좀 더 효율적인 코드를 작성하는 습관을 익혀야겠다.
