Coding - Algo/Java
[백준] 17144번:미세먼지 안녕! (Java 자바)
jainn
2021. 9. 24. 12:19
728x90
문제
https://www.acmicpc.net/problem/17144
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사
www.acmicpc.net
풀이 및 소스코드
공기청정기에서 나오는 부분은 0으로 초기화해야하는데
그걸 간과하고 했다가 시간낭비를 잔뜩했당 ㅠㅠ
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
int[][] map = new int[n][m];
Node am = new Node(0, 0);
for(int i=0;i<n;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<m;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j]==-1) {
am = new Node(i, j);
//공기청정기 좌표 넣기
}
}
}
int[] dx1 = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
int[] dx2 = {1, 0, -1, 0};
int time = 0;
while(true) {
//1. 미세먼지 확산
int[][] c_map = new int[n][m];
//확산된 공기를 계산해서 담는 배열
for(int x=0;x<n;x++) {
for(int y=0;y<m;y++) {
if(map[x][y]==0||map[x][y]==-1) continue;
int cnt = 0;
//확산 시키고, 확산될 방향의 개수를 구하는 for문
for(int i=0;i<4;i++) {
int nowx = x+dx1[i], nowy = y+dy[i];
if(0>nowx||0>nowy||nowx>=n||nowy>=m) continue;
if(map[nowx][nowy]==-1) continue;
c_map[nowx][nowy]+=map[x][y]/5;
cnt++;
}
if(cnt!=0) {
c_map[x][y] += (map[x][y]-map[x][y]/5*cnt);
}
}
}
//확산 된 결과를 원래 배열에 담는 for문
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
map[i][j] = c_map[i][j];
}
}
map[am.x][am.y] = -1;
map[am.x-1][am.y] = -1;
//2. 공기청정기 작동
int x1 = am.x-2;
int y1 = am.y;
//공기청정기 윗칸은 위에서부터 시작
int x2 = am.x+1;
int y2 = am.y;
//공기청정기 아랫칸의 아래부터 시작
//공기청정기에 들어가면 미세먼지가 사라지므로 공기청정기에 들어가는 부분부터 해주면된다.
for(int i=0;i<4;i++) {
while(true) {
int nowx1 = x1+dx1[i], nowy1 = y1+dy[i];
if(nowx1<0||nowy1<am.y||nowx1>am.x-1||nowy1>=m) break;
if(map[nowx1][nowy1]==-1) {
map[am.x-1][am.y+1] = 0;
break;
}
map[x1][y1] = map[nowx1][nowy1];
x1 = nowx1;
y1 = nowy1;
}
while(true) {
int nowx2 = x2+dx2[i], nowy2 = y2+dy[i];
if(nowx2<am.x||nowy2<am.y||nowx2>=n||nowy2>=m) break;
if(map[nowx2][nowy2]==-1) {
map[am.x][am.y+1] = 0;
break;
}
map[x2][y2] = map[nowx2][nowy2];
x2 = nowx2;
y2 = nowy2;
}
}
time++;
if(time == t) break;
//t초후 종료
}
int res =0;
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(map[i][j]!=0&&map[i][j]!=-1) {
res+=map[i][j];
}
}
}
System.out.println(res);
}
}
class Node{
int x,y;
public Node(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
반응형