구현
백준 17144번 구현문제를 Java로 풀어보았다. 머리가 띵~하다.
이 문제 역시 문제 자체가 졸라 길기 때문에 링크로 첨부하겠다.
https://www.acmicpc.net/problem/17144
조건 파악
이 문제는 하나의 문제를 두 개의 작은 문제로 나눠서 풀 수 있다.
- 미세먼지 확산
- 공기 청정기 바람
이 중에서도 미세먼지 확산은 하나의 문제로 처리할 수 있고,
공기 청정기 바람은 또다시 두 개의 작은 문제로 처리할 수 있다.
먼저 미세먼지 확산부터 살펴보자.
미세먼지 확산
우선 미세먼지 확산은 모든 지점에서 한 번에 일어나는 단회성 사건이기 때문에 초기 상태와 이후 상태 두 개로 나누어 봐야한다.
이 말이 무슨 말이냐면, 초기 상태 배열과 이후 상태 배열 두 개를 통해 이후 상태 배열의 값들을 업뎃해줘야 한다.
초기 상태 배열 하나로 그 배열 자체를 업데이트 해나가면 중간에 미세먼지 양의 왜곡이 생겨버리기 때문이다.
코드로 살펴보면 좀 더 이해가 쉬울 것이다.
아래는 미세먼지 확산만을 표현한 메소드다.
static int[][] Spread(int[][] before){ // 미세 먼지 확산 메소드
int[][] after = new int[R][C];
for(int i=0; i<R; i++)
for(int j=0; j<C; j++)
after[i][j] = before[i][j];
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
if(before[i][j]==0 || before[i][j]==-1) continue; // 0이나 -1이면 그냥 지나침
else{ // 미세먼지 있을 경우는 확산시켜주자
int contribute = before[i][j]/5; // 나눠줄 양
for(int k=0; k<4; k++){ // 사방으로 나눠주자
int nRow = i + direction[k][0];
int nCol = j + direction[k][1];
if(nRow<0 || nRow>=R || nCol<0 || nCol>=C) continue; // 범위 벗어나면
if(nRow==whereCleanerIs-1 && nCol==0) continue; // 공기 청정기1 자리면
if(nRow==whereCleanerIs && nCol==0) continue; // 공기 청정기2 자리면
after[nRow][nCol] += contribute; // 사방에 주고
after[i][j] -= contribute; // 자기 자신은 줄어들고
}
}
}
}
return after;
}코드를 보면 알 수 있겠지만 초기 상태 배열의 값을 기준으로 이후 상태 배열의 값들을 업데이트 해준다.
또한 미세먼지 확산은 하나의 전체 배열로 처리해주는 것을 확인할 수 있다. 이후에 볼 공기 청정기 바람 처리와는 어떻게 다른지 비교해볼 것이다.
공기 청정기 바람
공기 청정기 바람을 처리해줄 때는 하나의 전체 배열을 두 개로 나눠 볼 수 있다. 왜냐면 공기청정기 위 아래를 기준으로 완전히 독립적으로 작업이 이뤄지기 때문이다.
이를 코드로 표현하면 각자의 범위만을 다룬 두 개의 이중 for문이 나오게 된다.
static int[][] Circulate(int[][] before){ // 공기 청정기 가동 메소드
int[][] after = new int[R][C];
for(int i=0; i<R; i++)
for(int j=0; j<C; j++)
after[i][j] = before[i][j];
/** 공기 청정기 윗 부분 */
for(int i=0; i<whereCleanerIs; i++){
for(int j=0; j<C; j++){
if(i==0){ // 첫 번째 행 처리
if(j==0) { // 왼쪽 상단 꼭짓점은 아래로 내려가고
if(before[1][0]!=-1) // 만약 청정기 자리가 아니면
after[1][0] = before[i][j];
}
else // 왼쪽 꼭짓점을 제외하고는 왼쪽으로 한 칸씩만 옮겨가면 된다
after[i][j-1] = before[i][j];
}
else if(i==whereCleanerIs-1){ // 마지막 행 처리
if(j==0) continue; // 청정기 자리임
if(j==C-1) after[i-1][j] = before[i][j]; // 우측 하단 꼭짓점은 위로 한 칸 올리고
else // 나머지는 우측으로 한 칸씩만 옮기면 된다
after[i][j+1] = before[i][j];
}
else{ // 처음과 마지막 사이
if(j>0 && j<C-1) continue;
if(j==0){ // 아래로 밀어
if(before[i+1][j]!=-1) // 한 칸 밑이 청정기가 아니라면 밀어주자
after[i+1][j] = before[i][j];
}
else if(j==C-1) // 위로 밀어
after[i-1][j] = before[i][j];
}
}
}
/** 공기 청정기 아랫 부분 */
for(int i=whereCleanerIs; i<R; i++){
for(int j=0; j<C; j++){
if(i==whereCleanerIs){ // 첫 번째 행 처리
if(j==0) continue; // 청정기 자리임
if(j==C-1) after[i+1][j] = before[i][j]; // 우측 상단 꼭짓점은 한 칸 내리고
else // 그 외는 오른쪽으로 한 칸씩 옮기면 된다
after[i][j+1] = before[i][j];
}
else if(i==R-1){ // 마지막 행 처리
if(j==0)
if(before[i-1][j]!=-1) // 한 칸 위가 청정기가 아니라면 위로 밀어주자
after[i-1][j] = before[i][j];
else // 그 외는 왼쪽으로 한 칸씩 밀면 된다
after[i][j-1] = before[i][j];
}
else{ // 처음과 마지막 사이
if(j>0 && j<C-1) continue; // 바람 안 닿는 부분
if(j==0) // 위로 밀어
if(before[i-1][j]!=-1)
after[i-1][j] = before[i][j];
else if(j==C-1) // 아래로 밀어
after[i+1][j] = before[i][j];
}
}
}
return after;
}코드가 길어서 복잡해 보이지만 그저 조건에 따라 각 위치의 값들을 한 칸씩 옮겨주는 작업만을 그대로 구현한 것이다. 더 짧고 직관적으로 짤 수 있을까를 더 고민해보지는 못했다. 1시간 안에 푸는 것만으로도 벅찼기 때문...ㅠ
T초간 위 두 행위를 반복
위의 두 작업을 한 번만 하는 것이 아니라 T번만큼 반복해서 해야한다. 이를 구현하기 위해 for문으로 위 작업을 T번만큼 반복해줬다.
for(int i=0; i<T; i++){
int[][] after = Spread(map);
after = Circulate(after);
map = after; // 이젠 얘를 초기상태로 초기화해주어 다시 작업에 들어간다
map[whereCleanerIs-1][1] = 0; // 공기 청정기 옆자리는 바람이 불면 당연히 비어있다.
map[whereCleanerIs][1] = 0; // 위와 마찬가지
}그리고 미세먼지 총량을 계산해주기 위해 map의 모든 값들을 다 더한 후에 공기 청정기 자리의 -1이 두 번 나오는 것을 다시 +2를 해줌으로써 총량을 계산한다.
for(int i=0; i<R; i++){
for(int j=0; j<C; j++)
answer += map[i][j];
}
answer += 2;위 모든 코드를 다 합친 것이 아래의 내가 제출한 코드다.
import java.util.*;
import java.io.*;
public class boj17144 {
static int R,C,T, whereCleanerIs, answer;
static int[][] map;
static int[][] direction = { {-1,0}, {1,0}, {0,-1}, {0,1} }; // 상 하 좌 우
public static void main(String args[]) throws IOException {
BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stk = new StringTokenizer(bfr.readLine());
R = Integer.parseInt(stk.nextToken()); C = Integer.parseInt(stk.nextToken()); T = Integer.parseInt(stk.nextToken());
map = new int[R][C];
for(int i=0; i<R; i++){ // 초기 상태 입력 받자
stk = new StringTokenizer(bfr.readLine());
for(int j=0; j<C; j++) {
map[i][j] = Integer.parseInt(stk.nextToken());
if(map[i][j]==-1) whereCleanerIs = i; // 두 번 나올테니까 밑에 위치한 녀석의 row를 저장할 거다
}
}
for(int i=0; i<T; i++){
int[][] after = Spread(map);
after = Circulate(after);
map = after;
map[whereCleanerIs-1][1] = 0; // 공기 청정기 옆자리는 바람이 불면 당연히 비어있다.
map[whereCleanerIs][1] = 0; // 위와 마찬가지
}
for(int i=0; i<R; i++){
for(int j=0; j<C; j++)
answer += map[i][j];
}
answer += 2;
bfw.write(String.valueOf(answer));
bfw.close();
}
static int[][] Spread(int[][] before){ // 미세 먼지 확산 메소드
int[][] after = new int[R][C];
for(int i=0; i<R; i++)
for(int j=0; j<C; j++)
after[i][j] = before[i][j];
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
if(before[i][j]==0 || before[i][j]==-1) continue; // 0이나 -1이면 그냥 지나침
else{ // 미세먼지 있을 경우는 확산시켜주자
int contribute = before[i][j]/5; // 나눠줄 양
for(int k=0; k<4; k++){ // 사방으로 나눠주자
int nRow = i + direction[k][0];
int nCol = j + direction[k][1];
if(nRow<0 || nRow>=R || nCol<0 || nCol>=C) continue; // 범위 벗어나면
if(nRow==whereCleanerIs-1 && nCol==0) continue; // 공기 청정기1 자리면
if(nRow==whereCleanerIs && nCol==0) continue; // 공기 청정기2 자리면
after[nRow][nCol] += contribute; // 사방에 주고
after[i][j] -= contribute; // 자기 자신은 줄어들고
}
}
}
}
return after;
}
static int[][] Circulate(int[][] before){ // 공기 청정기 가동 메소드
int[][] after = new int[R][C];
for(int i=0; i<R; i++)
for(int j=0; j<C; j++)
after[i][j] = before[i][j];
/** 공기 청정기 윗 부분 */
for(int i=0; i<whereCleanerIs; i++){
for(int j=0; j<C; j++){
if(i==0){ // 첫 번째 행 처리
if(j==0) { // 왼쪽 상단 꼭짓점은 아래로 내려가고
if(before[1][0]!=-1) // 만약 청정기 자리가 아니면
after[1][0] = before[i][j];
}
else // 왼쪽 꼭짓점을 제외하고는 왼쪽으로 한 칸씩만 옮겨가면 된다
after[i][j-1] = before[i][j];
}
else if(i==whereCleanerIs-1){ // 마지막 행 처리
if(j==0) continue; // 청정기 자리임
if(j==C-1) after[i-1][j] = before[i][j]; // 우측 하단 꼭짓점은 위로 한 칸 올리고
else // 나머지는 우측으로 한 칸씩만 옮기면 된다
after[i][j+1] = before[i][j];
}
else{ // 처음과 마지막 사이
if(j>0 && j<C-1) continue;
if(j==0){ // 아래로 밀어
if(before[i+1][j]!=-1) // 한 칸 밑이 청정기가 아니라면 밀어주자
after[i+1][j] = before[i][j];
}
else if(j==C-1) // 위로 밀어
after[i-1][j] = before[i][j];
}
}
}
/** 공기 청정기 아랫 부분 */
for(int i=whereCleanerIs; i<R; i++){
for(int j=0; j<C; j++){
if(i==whereCleanerIs){ // 첫 번째 행 처리
if(j==0) continue; // 청정기 자리임
if(j==C-1) after[i+1][j] = before[i][j]; // 우측 상단 꼭짓점은 한 칸 내리고
else // 그 외는 오른쪽으로 한 칸씩 옮기면 된다
after[i][j+1] = before[i][j];
}
else if(i==R-1){ // 마지막 행 처리
if(j==0)
if(before[i-1][j]!=-1) // 한 칸 위가 청정기가 아니라면 위로 밀어주자
after[i-1][j] = before[i][j];
else // 그 외는 왼쪽으로 한 칸씩 밀면 된다
after[i][j-1] = before[i][j];
}
else{ // 처음과 마지막 사이
if(j>0 && j<C-1) continue; // 바람 안 닿는 부분
if(j==0) // 위로 밀어
if(before[i-1][j]!=-1)
after[i-1][j] = before[i][j];
else if(j==C-1) // 아래로 밀어
after[i+1][j] = before[i][j];
}
}
}
return after;
}
}
오늘 배운 것
- 구현 문제는 조건을 따라 충실하게 따라가며 짜면 어느 정도 큰 틀이 나온다. 여기서부터 디테일을 추가해주자.
- 지난 번에 한 번 다뤘던 배열의 깊은 복사와 얕은 복사. 오늘 또다시 마주했는데 난 그냥 1차원 배열이나 2차원 배열이나 동일하게
.clone()으로 처리해주면 될 줄 알았는데 이 방식은 1차원 배열에만 깊은 복사를 해주는 해결책이었다. 2차원 배열에 이 짓을 하면 얕은 복사가 된다는 것을 알게 됐다. 그래서 그냥 직접 2중for문을 돌려 복사해줬다.
개발 빼고 다 하는 개발자