문제
문제접근 방법
해당 문제는 R x C 크기의 공간에 미세먼지와 공기청정기가 존재하고 1초마다 아래의 일들이 일어난다고 할 때
T초 후에는 공간에 미세먼지가 얼마나 존재하는지를 구하는 문제이다.
- 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
- (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
- 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
- 확산되는 양은 Ar, c/5이고 소수점은 버린다. 즉, ⌊Ar, c/5⌋이다.
- (r, c)에 남은 미세먼지의 양은 Ar, c- ⌊Ar, c/5⌋×(확산된 방향의 개수)이다.
- 공기청정기가 작동한다.
- 공기청정기에서는 바람이 나온다.
- 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
- 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
- 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
처음에 문제를 읽고 어떤 알고리즘을 사용해 접근해야 하는지와 구조를 파악했다.
먼저 문제에서는 R x C 공간과 임의의? 행 1열부터?+1행 1열을 차지하는 2 크기의 공기청정기가
존재하고 공간에 먼지가 존재한다는 것까지 알 수 있다.
여기서 중요한 부분은 1) 공기 청정기는 무조건 1열에 설치하고 크기는 2이다. 부분이다.
그러고 나서는 1초 동안 순서대로 일어나는 일들을 분석해야 하는데 본인이 이해한 바로는
크게 3가지 로직이 존재해야 한다.
1) 미세먼지 확산 로직
- 동시에 확산
- 상하좌우 인접한 공간으로 확산
- 확산양은 본체에서 1/5한 값이다.
- 확산된 후 본체에서는 확산된 만큼 작아진다.
2) 공기청정기 작동 로직
- 바람이 나오는데
- 위쪽에서는 반시계 방향으로 순환
- 아래쪽에서는 시계 방향으로 순환
- 바람 불면 미세먼지가 바람 방향으로 한 칸씩 이동
- 공기청정기에서 나온 바람은 먼지가 없다
- 공기청정기로 먼지 들어오면 정화된다.
3) 먼지 카운트
- 위의 로직들이 T초동 안 작동하고 나서 마지막에 공간의 먼지를 카운트
- 입력 범위가 충분하기 때문에 이중반복문을 활
이런 조건을 가진 로직이다. 위의 문제를 그대로 적어둔 것이라 생각될 수 있지만 3가지 로직으로 나누고 나름대로의
조건들을 정리한 것이다.
다 잘 구현하였지만 공기청정기 로직을 잘못 설계하였다. 한 칸씩 이동한다기에 먼지가 뭉쳐진다고 생각했다.
그래서 결국 공기가 순환하면서 뭉쳐진 먼지가 1초마다 공기청정기로 들어간다고 판단해 공기가 순환하는 곳을 모두 빈칸 처리해 주었다. 하지만 아래서 설명하겠지만 이 부분이 잘못되었다.
< 초기 코드 >
import java.util.*;
//
public class Main{
public static int map[][]; // R x C 크기 공간
public static int tempMap[][]; // R x C 크기 공간 임시 공간
public static int airPurifier[]=new int[2]; // 공기청정기 좌표
public static void main(String args[]){
Scanner s=new Scanner(System.in);
int r=s.nextInt(); // 행
int c=s.nextInt(); // 열
int t=s.nextInt(); // 몇초?
int airIndex=0;
map=new int[r][c];
tempMap=new int[r][c];
// 공간에 존재하는 미세먼지와 공기청정기 입력
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
map[i][j]=s.nextInt();
if(map[i][j]==-1){
// 공기 청정기는 -1
airPurifier[airIndex]=j;
airIndex++;
}
}
}
for(int repeat=0;repeat<t;repeat++){
// 1초동안 아래 행위 반복 총 t초 동안
// 1) 미세먼지 확산
for(int i=0;i<r;i++){
for(int j=0;j<r;j++){
if(map[i][j]>0){
spreadDust(i,j);
}
}
}
addDust();
// 2)공기청정기 작동
airPurifier_operation();
}
// t초 동안 반복 후 공간에 남아있는 미세먼지 카운트
System.out.print(dustCount());
}
public static void spreadDust(int x,int y){
int dust=map[x][y];
int spread=dust/5;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
//공기청정기 존재 or 칸 존재 하지 않는다면 확산 x
if(nx>=0&&ny>=0&&nx<map.length&&ny<map[0].length&&map[nx][ny]!=-1){
tempMap[nx][ny]+=spread;
map[x][y]-=spread;
}
}
}
public static void addDust(){
for(int i=0;i<map.length;i++){
for(int j=0;j<map[0].length;j++){
map[i][j]+=tempMap[i][j];
}
Arrays.fill(tempMap[i],0);
}
}
public static void airPurifier_operation(){
int topX=airPurifier[0];
int bottomX=airPurifier[1];
for(int j=0;j<map[0].length;j++){
map[topX][j]=0;
map[bottomX][j]=0;
map[0][j]=0;
map[map.length-1][j]=0;
}
for(int i=0;i<map.length;i++){
map[i][0]=0;
map[i][map[0].length-1]=0;
}
for(int i=0;i<2;i++){
map[0][airPurifier[i]]=-1;
}
}
public static int dustCount(){
int total=0;
for(int i=0;i<map.length;i++){
for(int j=0;j<map[0].length;j++){
total+=map[i][j];
}
}
return total+2;
} // 그냥 완전 탐색해도 ㄱㅊ? -> ㅇㅇ 범위가 크지 않음
}코드의 흐름이나 작동방식은 위에서 간단하게 설명하기도 했고 주석도 있기 때문에 필요한 부분만 설명하겠다.
크게 3가지 로직과 각 로직에서 쪼개져 기능을 하는 4개의 함수로 이루어져 있다.
- 먼지 확산
- spreadDust // 먼지 확산
- map배열에 있는 먼지 확산을 tempMap에 저장
- 그래야 초마다 어떤 먼지가 확산해야 하는지를 정할 수 있음
- addDust
- spreadDust에서 확산된 먼지를 tempMap에 저장했는데 이를 합치는 과정
- tempMap과 map을 합친다.
- spreadDust // 먼지 확산
- 공기청정기 작동
- airPurifier_operation
- 공기청정기의 바람 순환 로직을 구현
- 결국 바람이 지나가는 모든 길은 0이 되어야 함 -> 잘못된 판단 -> 설명은 아래에서
- airPurifier_operation
- 먼지 카운트
- dustCount
- 최종 T초가 지나고 공간에 존재하는 먼지를 카운트하는 함수
- dustCount
각각의 로직의 함수들로 쪼개어 잘 작동하겠지라고 생각했지만 아니었다.
public static void airPurifier_operation(){
int topX=airPurifier[0];
int bottomX=airPurifier[1];
for(int j=0;j<map[0].length;j++){
map[topX][j]=0;
map[bottomX][j]=0;
map[0][j]=0;
map[map.length-1][j]=0;
}
for(int i=0;i<map.length;i++){
map[i][0]=0;
map[i][map[0].length-1]=0;
}
for(int i=0;i<2;i++){
map[0][airPurifier[i]]=-1;
}
}airPurifier_operation함수 부분이 문제였는데 해당 함수는 공기 순환을 구현한 함수로 공기청정기의 핵심 기능이다.
하지만 문제 자체를 잘못이해하고 접근한 것을 예제를 입력하다가 알게 되었다. 위의 문제에서는 예제 1까지만 나와있는데
본인이 일부러 잘라서 캡처한 것이다.
본인도 거기까지만 보고 문제를 풀이했기 때문이다. 본래는 예제를 보면서 더블체크했지만 본문제를 풀 때는 문제에서 요구하는 게 명확해 문제를 설계한 대로 작성 후 나중에 예제의 입력을 넣으면 출력이 맞는지 확인해보려 하였다.
그런데 예제 사이에 이런 추가 설명이 있는 것이었다. 그러니까 본인이 해석한 공기청정기는 먼지가 뭉쳐져서 결국에는 순환하면
바람이 지나가는 길에 있는 먼지들은 1초마다 뭉쳐져 공기청정기로 돌아오는 것이었다.
하지만 실제로는 1초마다 바람이 1칸씩 밀어서 밀린 먼지가 들어오는 방식이었다. 이를 해결하기 위해서 아래와 같이 코드를 수정하였다.
< 최종 코드 >
import java.util.*;
//
public class Main{
public static int map[][]; // R x C 크기 공간
public static int tempMap[][]; // R x C 크기 공간 임시 공간
public static int airPurifier[]=new int[2]; // 공기청정기 좌표
public static void main(String args[]){
Scanner s=new Scanner(System.in);
int r=s.nextInt(); // 행
int c=s.nextInt(); // 열
int t=s.nextInt(); // 몇초?
int airIndex=0;
map=new int[r][c];
tempMap=new int[r][c];
// 공간에 존재하는 미세먼지와 공기청정기 입력
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
map[i][j]=s.nextInt();
if(map[i][j]==-1){
// 공기 청정기는 -1
airPurifier[airIndex]=i;
airIndex++;
}
}
}
for(int repeat=0;repeat<t;repeat++){
// 1초동안 아래 행위 반복 총 t초 동안
// 1) 미세먼지 확산
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(map[i][j]>0){
spreadDust(i,j);
}
}
}
addDust();
// 2)공기청정기 작동
airPurifier_operation();
}
// t초 동안 반복 후 공간에 남아있는 미세먼지 카운트
System.out.print(dustCount());
}
public static void spreadDust(int x,int y){
int dust=map[x][y];
int spread=dust/5;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
//공기청정기 존재 or 칸 존재 하지 않는다면 확산 x
if(nx>=0&&ny>=0&&nx<map.length&&ny<map[0].length&&map[nx][ny]!=-1){
tempMap[nx][ny]+=spread;
map[x][y]-=spread;
}
}
}
public static void addDust(){
for(int i=0;i<map.length;i++){
for(int j=0;j<map[0].length;j++){
map[i][j]+=tempMap[i][j];
}
Arrays.fill(tempMap[i],0);
}
}
public static void airPurifier_operation(){
int r=map.length, c=map[0].length;
int top=airPurifier[0], bot=airPurifier[1];
for(int i=top-1;i>0;i--) map[i][0]=map[i-1][0];
for(int j=0;j<c-1;j++) map[0][j]=map[0][j+1];
for(int i=0;i<top;i++) map[i][c-1]=map[i+1][c-1];
for(int j=c-1;j>1;j--) map[top][j]=map[top][j-1];
map[top][1]=0;
map[top][0]=-1;
for(int i=bot+1;i<r-1;i++) map[i][0]=map[i+1][0];
for(int j=0;j<c-1;j++) map[r-1][j]=map[r-1][j+1];
for(int i=r-1;i>bot;i--) map[i][c-1]=map[i-1][c-1];
for(int j=c-1;j>1;j--) map[bot][j]=map[bot][j-1];
map[bot][1]=0;
map[bot][0]=-1;
}
public static int dustCount(){
int total=0;
for(int i=0;i<map.length;i++){
for(int j=0;j<map[0].length;j++){
total+=map[i][j];
}
}
return total+2;
} // 그냥 완전 탐색해도 ㄱㅊ? -> ㅇㅇ 범위가 크지 않음
}초기 코드에서는 바람이 지나가는 길은 모두 0으로 처리하였지만 1칸씩 이동하는 것이라고 생각하니 어떤 식으로 접근해야 할지 고민이 생겼다. 바람의 방향대로 수가 한 칸씩 이동하게 된다면 배열로 생각했을 때 앞의 값이 없어져 이동이 불가능하기 때문이다.
그래서 역으로 시계방향으로 바람이 불면 배열은 반시계순으로 처리하는 식으로 처리하여 문제를 해결하였다.
마무리
처음에는 구현과 DFG를 활용하는 문제인가 생각했지만 문제를 설계하는 과정에서 DFS를 사용할 필요가 없다고 판단했다.
문제 자체는 어렵지 않게 접근해 풀이가능할 것이라 생각된다. 하지만 처음 설계가 중요할 것 같다.
그냥 접근한다면 중간에 조건을 고려하지 않거나 해서 시간이 더 소요될 것으로 보인다.
'문제풀이 > 구현' 카테고리의 다른 글
| [문제 풀이] 백준 1244번 스위치 켜고 끄기 JAVA (0) | 2025.08.11 |
|---|---|
| [문제 풀이] 백준 3190번 뱀 JAVA (0) | 2025.07.27 |
| [문제 풀이] 백준 20055번 컨베이어 벨트 위의 로봇 JAVA (0) | 2025.07.20 |
| [문제 풀이] 백준 14503번 로봇 청소기 JAVA (0) | 2025.07.19 |
| [문제 풀이] 백준 14890번 경사로 JAVA (0) | 2025.07.18 |