24.02.04 기준 이 문제 java 그룹에서의 제 풀이가 1년 넘게 계속 정답 1등에 랭크되어 있습니다.
아무래도 싸피에서 풀게 시키는 문제라 그런지 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에 의해서 알아서 해제될 것 같네요.)