[Javascript] BOJ_17144. 미세먼지 안녕!

🦍 문제

17144번: 미세먼지 안녕!

 

---

🐈 문제 풀이 

1. 무엇을 구해야 할까?

- 미세먼지의 확산, 공기청정기의 공기 순환 작업을 반복하며 주어진 t초 이후, 방에 남아있는 미세먼지의 양

 

2. 어떻게 구해야 할까?

2.1. 미세먼지 확산

2.2. 공기청정기 공기 순환

위 두 기능에 대한 함수를 정의한 후, [미세먼지 확산 -> 공기청정기 공기 순환]의 흐름을 t초간 반복시키면 된다.

 

2.1 미세먼지 확산

/**
 * 먼지 확산 알고리즘
 * @param {Object} idx : 공기청정기의 좌표를 담고 있는 배열 idx
 */
function doDustMove(idx) {
  // 임시 배열 생성
  const tmpArr = Array(R)
    .fill(0)
    .map(() => Array(C).fill(0));

  // 공기청정기 위치 설정
  for (let i = 0; i < 2; ++i) {
    tmpArr[idx[i][0]][idx[i][1]] = -1;
  }

  // 먼지 확산
  for (let i = 0; i < R; ++i) {
    for (let j = 0; j < C; ++j) {
      if (arr[i][j] > 0) {
      
      	// diffusion : 사방으로 확산될 먼지의 양
        let diffusion = Math.floor(arr[i][j] / 5);
        
        // cnt : 확산이 이루어진 방향의 수
        let cnt = 0;
        for (let k = 0; k < 4; ++k) {
          let nr = i + dr[k];
          let nc = j + dc[k];
          if (nr >= 0 && nr < R && nc >= 0 && nc < C) {
          
          	// 공기청정기가 있는 방향이 아니라면 확산 진행
            if (arr[nr][nc] !== -1) {
              ++cnt;
              tmpArr[nr][nc] += diffusion;
            }
          }
        }
        
        // 해당 칸(i,j)에서 다른 칸으로 확산이 이루어진 만큼 해당 칸의 먼지 양 감소
        tmpArr[i][j] += arr[i][j] - diffusion * cnt;
      }
    }
  }

  // 기존 배열 갱신
  for (let i = 0; i < R; ++i) {
    arr[i] = [...tmpArr[i]];
  }
}

 - 미세먼지 확산 기능의 구현은 다음과 같다.

    1. 미세먼지 확산 후의 상태를 저장할 임시 배열 생성

    2. 임시 배열에서 공기청정기의 위치를 지정 => 공기청정기 방향으로 먼지 확산이 이루어지면 안되므로 고려하기 위함

    3. 반복문을 통한 먼지 확산

    4. 기존의 방 안 먼지 상태를 저장하고 있는 배열을 임시 배열로 덮어쓰기

 

2.2 공기청정기 공기 순환

/**
 * 공기청정기 순환 알고리즘
 * @param {Ojbect} idx : 공기청정기의 좌표를 담고 있는 배열 idx
 * @param {Number} dir : 공기청정기의 상부, 하부를 구분할 변수 dir
 */
function doCirculate(idx, dir) {
  let [r, c] = idx[dir];

  // 공기청정기 상부 순환
  if (dir === 0) {
    while (r - 1 >= 0) {
      if (arr[r][c] === -1) {
        arr[r - 1][c] = 0;
        --r;
        continue;
      }
      arr[r][c] = arr[r - 1][c];
      --r;
    }
    while (c + 1 < C) {
      arr[r][c] = arr[r][c + 1];
      ++c;
    }
    while (r + 1 <= idx[dir][0]) {
      arr[r][c] = arr[r + 1][c];
      ++r;
    }
    while (c - 1 > 0) {
      arr[r][c] = arr[r][c - 1];
      --c;
    }
    arr[r][c] = 0;
  }

  // 공기청정기 하부 순환
  else if (dir === 1) {
    while (r + 1 < R) {
      if (arr[r][c] === -1) {
        arr[r + 1][c] = 0;
        ++r;
        continue;
      }
      arr[r][c] = arr[r + 1][c];
      ++r;
    }
    while (c + 1 < C) {
      arr[r][c] = arr[r][c + 1];
      ++c;
    }
    while (r - 1 >= idx[dir][0]) {
      arr[r][c] = arr[r - 1][c];
      --r;
    }
    while (c - 1 > 0) {
      arr[r][c] = arr[r][c - 1];
      --c;
    }
    arr[r][c] = 0;
  }
}

 - 공기청정기 공기 순환 기능의 구현은 다음과 같다.

    1. 공기청정기 상부/하부 순환의 구분

    2. 구분된 순환의 종류에 따라 배열을 순회하며 공기 순환 

1) 실제 공기청정기의 흐름                                                      2) 기능 구현을 위해 표현한 공기청정기의 흐름

 - 좌측 그림과 같은 흐름을 만들어내기 위해 우측 그림에서 더 큰 번호를 가진 배열의 값을 작은 번호의 배열 값으로 덮어씌워 기능 구현

 - arr[22] = arr[21], arr[21] = arr[20] 을 반복하여 공기 순환

 - arr[22]의 경우, 공기청정기가 위치한 곳이므로 덮어씌우지 않고 arr[21]의 값을 0으로 할당

3. 특별히 고려해야 할 사항은?

 - 미세 먼지 확산 기능 구현 시, 임시 배열을 따로 만들어주지 않고 기존 배열에서 바로 확산을 구현하면 인접해 있는 다른 미세먼지의 양에 영향을 끼쳐 올바르지 않은 값을 저장할 수 있다.

---

🐕‍🦺 소스 코드

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

// 초기 값 설정
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];
let [R, C, T] = input[0].split(" ").map((element) => Number(element));
const arr = Array(R).fill(0);

solution();

function solution() {
  // idx : 공기청정기 위치를 담을 배열
  let idx = [];

  // 배열 생성
  for (let i = 0; i < R; ++i) {
    arr[i] = input[i + 1].split(" ").map((element) => Number(element));
    for (let j = 0; j < C; ++j) {
      if (arr[i][j] === -1) {
        idx.push([i, j]);
      }
    }
  }

  // 먼지 확산 -> 공기청정기 순환
  for (let i = 0; i < T; ++i) {
    doDustMove(idx); // 먼지 확산
    doCirculate(idx, 0); // 상부 공기 순환
    doCirculate(idx, 1); // 하부 공기 순환
  }

  // 정답 출력
  let answer = 0;
  for (let i = 0; i < R; ++i) {
    for (let j = 0; j < C; ++j) {
      if (arr[i][j] > 0) {
        answer += arr[i][j];
      }
    }
  }
  console.log(answer);
}

/**
 * 먼지 확산 알고리즘
 * @param {Object} idx
 */
function doDustMove(idx) {
  // 임시 배열 생성
  const tmpArr = Array(R)
    .fill(0)
    .map(() => Array(C).fill(0));

  // 공기청정기 위치 설정
  for (let i = 0; i < 2; ++i) {
    tmpArr[idx[i][0]][idx[i][1]] = -1;
  }

  // 먼지 확산
  for (let i = 0; i < R; ++i) {
    for (let j = 0; j < C; ++j) {
      if (arr[i][j] > 0) {
        let diffusion = Math.floor(arr[i][j] / 5);
        let cnt = 0;
        for (let k = 0; k < 4; ++k) {
          let nr = i + dr[k];
          let nc = j + dc[k];
          if (nr >= 0 && nr < R && nc >= 0 && nc < C) {
            if (arr[nr][nc] !== -1) {
              ++cnt;
              tmpArr[nr][nc] += diffusion;
            }
          }
        }
        tmpArr[i][j] += arr[i][j] - diffusion * cnt;
      }
    }
  }

  // 기존 배열 갱신
  for (let i = 0; i < R; ++i) {
    arr[i] = [...tmpArr[i]];
  }
}

/**
 * 공기청정기 순환 알고리즘
 * @param {Ojbect} idx
 * @param {Number} dir
 */
function doCirculate(idx, dir) {
  let [r, c] = idx[dir];

  // 공기청정기 상부 순환
  if (dir === 0) {
    while (r - 1 >= 0) {
      if (arr[r][c] === -1) {
        arr[r - 1][c] = 0;
        --r;
        continue;
      }
      arr[r][c] = arr[r - 1][c];
      --r;
    }
    while (c + 1 < C) {
      arr[r][c] = arr[r][c + 1];
      ++c;
    }
    while (r + 1 <= idx[dir][0]) {
      arr[r][c] = arr[r + 1][c];
      ++r;
    }
    while (c - 1 > 0) {
      arr[r][c] = arr[r][c - 1];
      --c;
    }
    arr[r][c] = 0;
  }

  // 공기청정기 하부 순환
  else if (dir === 1) {
    while (r + 1 < R) {
      if (arr[r][c] === -1) {
        arr[r + 1][c] = 0;
        ++r;
        continue;
      }
      arr[r][c] = arr[r + 1][c];
      ++r;
    }
    while (c + 1 < C) {
      arr[r][c] = arr[r][c + 1];
      ++c;
    }
    while (r - 1 >= idx[dir][0]) {
      arr[r][c] = arr[r - 1][c];
      --r;
    }
    while (c - 1 > 0) {
      arr[r][c] = arr[r][c - 1];
      --c;
    }
    arr[r][c] = 0;
  }
}

---

---

🐖 Think

 - 문제 해결에 필요한 기능들을 구별하고, 해당 기능에 대한 함수를 적절히 작성하며 진행하니 보다 원활하게 문제를 해결할 수 있었다. 갈수록 초기 필요한 기능 설계가 중요해지는 것 같다.