BOJ 17144 미세먼지 안녕! java 풀이

신현철·2024년 2월 4일
0

BOJ

목록 보기
9/9
post-thumbnail

ranking

24.02.04 기준 이 문제 java 그룹에서의 제 풀이가 1년 넘게 계속 정답 1등에 랭크되어 있습니다.
아무래도 싸피에서 풀게 시키는 문제라 그런지 java 풀이를 읽으시는 분들이 많은 것 같아서 코드와 간단한 해설을 업로드하겠습니다.


📗 Java 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int dx[] = {0,1,0,-1};
	static int dy[] = {1,0,-1,0};
	static int R,C,T;
	static int[][] room;
	static List<Point> cleaners = new ArrayList<>();
	
	static class Point{
		int x;
		int y;
		
		public Point(int x, int y){
			this.x = x;
			this.y = y;
		}
		
		public static boolean isValid(int x, int y) {
			
			if (x < 0 || y < 0 || x >= R || y >= C) return false;
			
			return true;
		}
	}
	
	public static void main(String[] args) throws IOException {
		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 i=0;i<R;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<C;j++) {
				room[i][j] = Integer.parseInt(st.nextToken());
				
				if (room[i][j] == -1) cleaners.add(new Point(i,j));
			}
		}
		
		System.out.println(simulate());
	}
	
	static void spreadAir() {
		int[][] after = new int[R][C];
		
		for(int x=0;x<R;x++) {
			for(int y=0;y<C;y++) {
				if(room[x][y] == -1) {
					after[x][y] = -1;
					continue;
				}
				
				int total = room[x][y];
				int diff = total/5;
				
				for(int i=0;i<4;i++) {
					int nx = x + dx[i], ny = y + dy[i];
					
					if (!Point.isValid(nx, ny) || room[nx][ny] == -1) continue;
					
					after[nx][ny] += diff;
					total -= diff;
				}
				after[x][y] += total;
			}
		}
		
		room = after;
	}
	
	static void cleanUp(int x, int y, int dir, int dust, int rot) {
		if (room[x][y] == -1) return;
		
		int tmp = room[x][y];
		room[x][y] = dust;
		
		int nx = x + dx[dir], ny = y + dy[dir];
		
		if (!Point.isValid(nx, ny)) {
			dir = (dir + rot) % 4;
			nx = x + dx[dir];
			ny = y + dy[dir];
		}
		
		cleanUp(nx, ny, dir, tmp, rot);
	}
	
	static void turnOnCleaner() {
		Point AC1 = cleaners.get(0);
		Point AC2 = cleaners.get(1);
		cleanUp(AC1.x, AC1.y + 1, 0, 0, 3);
		cleanUp(AC2.x, AC2.y + 1, 0, 0, 1);
	}
	
	static int simulate() {
		int ret = 2;
		
		while(T-- > 0) {
			spreadAir();
			turnOnCleaner();
		}
		
		for(int i=0;i<R;i++) {
			for(int j=0;j<C;j++) {
				ret += room[i][j];
			}
		}
		
		return ret;
	}
}

🔍 간단한 해설

우선 문제의 조건대로 따라가면서 구현을 정확하게 하면 풀리는 문제입니다.
따라서 명확한 풀이를 위해 phase의 동작마다 메소드를 나누어 작성하였습니다.

공기를 확산시키고 (spreadAir),
공기청정기를 가동하는 것을 (turnOnCleaner)
T초 동안 반복합니다.

turnOnCleaner 에서는 공기청정기가 두 방향으로 작동하는 행위를 하나의 메소드(cleanUp)에 다른 매개변수를 입력하여 구현했습니다.

첫 번째 시간 단축 포인트입니다

cleanUp 메소드는 DFS처럼 작동하며, 인풋 파라미터는 다음과 같습니다.

int x // 청정기가 작동할 격자의 세로 좌표값
int y // 청정기가 작동할 격자의 가로 좌표값
int dir // 청정기가 작동하는 방향 = 바람의 방향
int dust // 이전 칸에서 불어온 먼지의 유무, 이를 통해 새로 값을 할당합니다.
int rot // 순환하는 방향(시계 1 or 반시계 3)

rot 라는 변수를 통하여 격자의 가장자리에 닿을 때는 dir = (dir + rot) % 4; 부분에서 시계 또는 반시계로 회전하는 것을 하나의 메소드로 구현할 수 있습니다.

이렇게 하나의 메소드를 사용할 때 장점이 있을까요?

네 있습니다.

  • 지역 변수 및 상태 유지의 간소화: 여러 메소드를 사용하면 각 메소드에서 필요한 지역 변수 및 상태를 유지해야 합니다. 하나의 메소드로 모든 작업을 처리하면 공통 상태를 유지하고 지역 변수의 사용을 최소화할 수 있어 메모리 및 관리 오버헤드를 감소시킬 수 있습니다.

  • 최적화 기회 확대: 컴파일러나 JIT(Just-In-Time) 컴파일러는 단일 메소드 내에서의 코드 흐름을 더 잘 이해하고 최적화할 수 있습니다. 여러 메소드가 서로 다른 파일에 존재하면 이러한 최적화가 어려울 수 있습니다.

라고 우리 짱피티 형님이 말씀하시네요. (사실 미미하긴 합니다)

두 번째 시간 단축 포인트입니다

spreadAir 메소드의 첫 라인을 보면 다음과 같이 청정기 작동 후의 먼지 상태를 담아놓을 격자를 미리 생성하고 마지막에 교체해줍니다.

int[][] after = new int[R][C];

// (중략)

room = after;

당연한거 아니냐구요?
그럼 당신은 최고에요.

이 부분에서 격자를 갈아끼우지 않고 마지막에 이중 for문으로 값을 하나씩 옮긴다면 느려지게됩니다.(기존 room은 GC에 의해서 알아서 해제될 것 같네요.)

profile
DB는 두부

0개의 댓글

관련 채용 정보