https://www.acmicpc.net/problem/17144
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사
www.acmicpc.net
해당 문제는 이차원 배열에서의 인덱스를 어떻게 효율적으로 접근하고, 그 값을 관리할 것인가에 대한 문제이다.
문제에서 구현해야하는 시뮬레이션은
1. 먼지의 확산
2. 공기청정기 동작
이렇게 둘로 나눌 수 있다.
여기서 모든 동작이 배열에서 인접한 칸에만 영향을 미치므로 이차원 배열을 활용해서 이를 구현하는 것으로 문제를 해결했다.
문제를 풀면서 파트를 총 4개(출력 제외하면 3개)로 나눠 생각해봤다.
1. 입력 처리
2. 먼지 확산
3. 공기청정기 동작
4. 출력
먼저 입력처리를 살펴보자.
입력 처리 과정에서 필요한 것은 이차원 배열에서 먼지가 어디에 있는지 저장해두고, 공기청정기의 위치가 어딘지 체크해야한다. -1이 처음으로 입력되면 공기청정기의 위쪽 부분, 이미 입력되어 있다면 공기청정기의 아래쪽 부분으로 구분할 수 있다. 위쪽과 아래쪽을 구분해야하는 이유는 위쪽과 아래쪽에 따라서 바람 방향이 바뀌는 순서가 다르기 때문이다.
코드에서 dr1, dc1이 위쪽 공기청정기의 바람 방향이고, dr2, dc2가 아래쪽 공기청정기의 바람 방향이다.
for(int r = 0; r<R; r++) {
st = new StringTokenizer(br.readLine());
for(int c = 0; c <C; c++) {
room[r][c] = Integer.parseInt(st.nextToken());
if(room[r][c] == -1) {
if(r1 == -1) {
r1 = r;
c1 = c;
}
else {
r2 = r;
c2 = c;
}
}
}
}다음으로 주어진 시간(T) 동안 simulation이 진행된다.
각 시간 동안 simulation은 먼지확산 후 공기청정기 동작을 반복한다.
먼지 확산 과정에서 중요한 것은 모든 먼지가 동시에 확산된다는 것이다. 두개의 붙어있는 먼지가 있었을 때 어느 하나가 먼저 확산되지 않는다. 즉, 먼지의 확산은 계산하되 해당 확산이 모든 먼지가 확산될 때까지 먼지 정보를 담고 있는 room에 반영이 되면 안된다. 그렇기 때문에 nextRoom을 만들어서 확산되는 먼지들의 정보를 저장해두고, 모든 먼지가 확산된 후에 현재 방 상태인 room에 더해서 먼지 확산 과정을 처리하고자 했다.
//dust diffusion
for(int r = 0; r<R; r++) {
for(int c = 0; c<C; c++) {
if(room[r][c] == 0 ||room[r][c] == -1) continue;
for(int i = 0; i<4; i++) {
nr = r+dr1[i];
nc = c+dc1[i];
if(checkRange(nr, nc) && room[nr][nc] != -1) {
nextRoom[nr][nc] += room[r][c]/5;
nextRoom[r][c] -= room[r][c]/5;
}
}
}
}
for(int r = 0; r<R; r++) {
for(int c = 0; c<C; c++) {
room[r][c] += nextRoom[r][c];
}
}그 다음으로 공기청정기의 동작에서는 공기청정기에서 시작해서 실제 동작처럼 공기청정기를 미는 방법도 있긴한데, 그렇게 하면 먼지가 밀렸을 때 원래 있던 칸의 먼지 정보를 따로 저장해둬야 한다. 하지만 역방향으로 생각했을 떄는 공기청정기에 들어갈 먼지부터 생각한다면 따로 저장할 필요 없이 방향만 생각해서 한칸씩 당겨주기만 하면 된다.
먼저 위쪽 공기청정부터 살펴봤을 때, 공기청정기에 들어오는 부분이 위쪽 방향이니까 위쪽 방향으로 먼저 가고, 그다음 오른쪽, 그 다음 아래, 마지막으로 왼쪽으로 탐색해 다시 공기청정기에 들어올 수 있도록 한다. 아래쪽도 방향만 다르고 방법은 동일하다. 하지만 중요한것이 다른 방향은 range만 검사해서 벽에 부딫히면 방향을 바꿔주면 되는데 위쪽 공기청정기 기준으로 아래쪽으로 탐색하면서 공기청정기의 가로줄에 들어오면 아래로 계속 내려가는 것이 아니라 왼쪽으로 방향을 바꿔줘야 한다. 그래서 그 부분을 추가해서 코드를 작성했다.
static void pushDust() {
int uidx = 3; //위쪽 공기청정
int didx = 3; //아래쪽 공기청정
int nr, nc;
int r=r1, c=c1;
while(true){
nr = r+dr1[uidx];
nc = c+dc1[uidx];
if(nr == r1 && nc == c1) {
room[r][c] = 0;
break;
}
if(!checkRange(nr, nc)) {
uidx--;
nr = r+dr1[uidx];
nc = c+dc1[uidx];
}
//당겨오기
if(r == r1 && c== c1) {
room[nr][nc] = 0;
}
else {
room[r][c] = room[nr][nc];
}
if(uidx == 1 && nr==r1) {
uidx--;
}
r = nr;
c = nc;
}
r=r2; c=c2;
while(true){
nr = r+dr2[didx];
nc = c+dc2[didx];
if(nr == r2 && nc == c2) {
room[r][c] = 0;
break;
}
if(!checkRange(nr, nc)) {
didx--;
nr = r+dr2[didx];
nc = c+dc2[didx];
}
//당겨오기
if(r == r2 && c== c2) {
room[nr][nc] = 0;
}
else {
room[r][c] = room[nr][nc];
}
if(didx == 1 && nr==r2) {
didx--;
}
r = nr;
c = nc;
}
}
출력은 간단히 마지막에 공기청정기가 있는 칸을 제외하고 모든 칸에 대해서 먼지의 수를 다 더하면 답을 구하고 출력할 수 있다.
전체 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int R, C, T, dust;
static int r1=-1, c1=-1, r2=-1, c2=-1; //공기청정기 위치
static int[][] room;
//위쪽 공기청정기 탐색 방향 3(북)->2(동)->1(남)->0(서)으로 돌아감
static int[] dr1 = {0, 1, 0, -1};
static int[] dc1 = {-1, 0, 1, 0};
//아래쪽 공기청정기 탐색 방향 3(남)->2(동)->1(북)->0(서)으로 돌아감
static int[] dr2 = {0, -1, 0, 1};
static int[] dc2 = {-1, 0, 1, 0};
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());
room = new int[R][C];
for(int r = 0; r<R; r++) {
st = new StringTokenizer(br.readLine());
for(int c = 0; c <C; c++) {
room[r][c] = Integer.parseInt(st.nextToken());
if(room[r][c] == -1) {
if(r1 == -1) {
r1 = r;
c1 = c;
}
else {
r2 = r;
c2 = c;
}
}
}
}
for(int t = 0; t<T; t++) {
simulation();
}
for(int r = 0; r<R; r++) {
for(int c = 0; c<C; c++) {
if(room[r][c] != -1) {
dust+=room[r][c];
}
}
}
System.out.println(dust);
}
//먼지 확산, 공기청정기 작동 시 범위 체크 함수
static boolean checkRange(int r, int c) {
if(r>=R || r<0 || c>=C || c<0) {
return false;
}
return true;
}
//시뮬레이션 함수, 함수 내부에서 먼지확산을 하고
//pushDust함수를 불러서 공기청정기 작동을 시뮬레이션함.
static void simulation() {
int nr, nc;
int[][] nextRoom = new int[R][C];
//dust diffusion
for(int r = 0; r<R; r++) {
for(int c = 0; c<C; c++) {
if(room[r][c] == 0 ||room[r][c] == -1) continue;
//상하좌우 모든 방향에 대하여 먼지를 확산시킴
for(int i = 0; i<4; i++) {
nr = r+dr1[i];
nc = c+dc1[i];
if(checkRange(nr, nc) && room[nr][nc] != -1) {
nextRoom[nr][nc] += room[r][c]/5;
nextRoom[r][c] -= room[r][c]/5;
}
}
}
}
//먼지 확산을 현재 방에 적용함
for(int r = 0; r<R; r++) {
for(int c = 0; c<C; c++) {
room[r][c] += nextRoom[r][c];
}
}
pushDust();
}
static void pushDust() {
int uidx = 3; //위쪽 공기청정 인덱스는 3-2-1-0
int didx = 3; //아래쪽 공기청정 인덱스는 3-2-1-0
int nr, nc; //새로운 위치
//위쪽 공기청정기에서 시작
int r=r1, c=c1;
while(true){
nr = r+dr1[uidx];
nc = c+dc1[uidx];
//다 돌고나서 공기청정기에 다시 도착하면 공기청정기 바로 오른쪽 칸은 0으로 만들고 break
if(nr == r1 && nc == c1) {
room[r][c] = 0;
break;
}
//범위를 벗어나면 index를 감소시켜 방향을 전환함
if(!checkRange(nr, nc)) {
uidx--;
nr = r+dr1[uidx];
nc = c+dc1[uidx];
}
//당겨오기
if(r == r1 && c== c1) { //시작점일 때
room[nr][nc] = 0;
}
else { //나머지 경우
room[r][c] = room[nr][nc];
}
//아래쪽으로 내려가고 있을 때 공기청정기가 있는 줄에 오면 방향 전환
if(uidx == 1 && nr==r1) {
uidx--;
}
//다음 칸 탐색을 위해서 현재 위치 수정
r = nr;
c = nc;
}
//아래쪽 공기청정기 탐색. 위랑 방식은 똑같음
r=r2; c=c2;
while(true){
nr = r+dr2[didx];
nc = c+dc2[didx];
if(nr == r2 && nc == c2) {
room[r][c] = 0;
break;
}
if(!checkRange(nr, nc)) {
didx--;
nr = r+dr2[didx];
nc = c+dc2[didx];
}
//당겨오기
if(r == r2 && c== c2) {
room[nr][nc] = 0;
}
else {
room[r][c] = room[nr][nc];
}
if(didx == 1 && nr==r2) {
didx--;
}
r = nr;
c = nc;
}
}
}
'알고리즘' 카테고리의 다른 글
| [boj2531, 15961/Java] 회전 초밥 (0) | 2023.07.31 |
|---|---|
| [boj3649/Java]로봇 프로젝트 (0) | 2023.07.31 |
| [boj5397/Java] 키로거(Stack) (0) | 2023.07.24 |
| [boj13335/Java] 트럭(Queue 사용법) (0) | 2023.07.24 |
| [boj2477/Java] 참외밭 (0) | 2023.07.20 |