문제 설명
문제 링크는 여기
접근
시뮬레이션 문제로 솔직히 정말 화나고 짜증 나는 문제였다. 조건들이 너무 억지스러워서 솔직히 화났다!! 흥
문제를 크게 나누면 다음과 같다.
- 구름 이동 후 비 내리기
- 물 복사 하기
- 구름 생성
따라서 나는 각각의 기능을 수행하는 세 개의 함수를 나누어 구현하였다.
여기서 주의할 점은 3번 구름 생성 시 이전에 구름이 생겼던 부분에는 구름이 생기면 안 된다는 것이다. 따라서 추가적으로 이전 구름의 위치를 저장하는 cnt 배열을 이용하였다.
먼저 구름 이동 및 비 내리는 함수이다.
private static void rain(int d, int t, int N, int[][] arr, Stack<int[]> cloudStack, Stack<int[]> copyStack, boolean[][] cnt) {
while(!cloudStack.isEmpty()) {
int[] temp = cloudStack.pop();
int r = (temp[0] + (dr[d]+N)*t)%N;
int c = (temp[1] + (dc[d]+N)*t)%N;
copyStack.add(new int[] {r, c});
arr[r][c]++;
cnt[r][c] = true;
}
}cloudStack에는 구름들의 좌표가 담겨있다.
먼저 명령대로 구름을 이동시킨 후 비를 내린다. 이후 구름이 있었음을 알리기 위해 해당 좌표의 cnt 값을 true로 변경한다.
또한 해당 위치는 물 복사도 수행해야하므로 copyStack에 삽입한다.
물 복사 함수이다.
private static void copyWater(int N, int[][] arr, Stack<int[]> copyStack) {
while(!copyStack.isEmpty()) {
int[] temp = copyStack.pop();
int copy = 0;
for(int i=0; i<4; i++) {
int r = temp[0]+dr[1+2*i];
int c = temp[1]+dc[1+2*i];
if(!rangeCheck(r, c, N) || arr[r][c]==0) continue;
copy++;
}
arr[temp[0]][temp[1]] += copy;
}
}비가 내린 곳의 각 좌표에 대해 대각선 탐색을 수행한다. 마침 설정한 8방 탐색 배열을 사용해도 되길래 이용하였다.
각각 4개 위치 중 물이 있는 칸의 수만큼 해당 좌표의 값을 증가시켰다.
구름 생성 함수이다.
private static void makeCloud(int N, int[][] arr, Stack<int[]> cloudStack, boolean[][] cnt) {
for(int r=0; r<N; r++) {
for(int c=0; c<N; c++) {
if(!cnt[r][c] && arr[r][c]>=2) {
arr[r][c] -= 2;
cloudStack.add(new int[] {r, c});
}
}
}
}단순히 2보다 큰 곳은 2를 감하고 해당 좌표를 cloudStack에 담는다. 이때 이미 구름이 있었던 곳이면 수행하지 않는다.
위 세 개의 함수를 순서대로 실행시키는 함수는 다음과 같다.
private static void tryMagic(int N, int M, int[][] arr) throws Exception {
Stack<int[]> cloudStack = new Stack<>();
Stack<int[]> copyStack = new Stack<>();
boolean[][] cnt;
cloudStack.add(new int[] {N-1, 1});
cloudStack.add(new int[] {N-1, 0});
cloudStack.add(new int[] {N-2, 1});
cloudStack.add(new int[] {N-2, 0});
for(int m=0; m<M; m++) {
st = new StringTokenizer(br.readLine());
int d = Integer.parseInt(st.nextToken())-1;
int t = Integer.parseInt(st.nextToken());
cnt = new boolean[N][N];
rain(d, t, N, arr, cloudStack, copyStack, cnt);
copyWater(N, arr, copyStack);
makeCloud(N, arr, cloudStack, cnt);
}
}해당 함수에는 초기 구름을 설정하고 이후 반복문을 통해 명령어 수만큼 비를 내리고 구름 생성하는 것을 반복한다.
최종 메인 코드는 다음과 같다.
public static void main(String[] args) throws Exception {
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] arr = new int[N][N];
for(int r=0; r<N; r++) {
st = new StringTokenizer(br.readLine());
for(int c=0; c<N; c++) {
arr[r][c] = Integer.parseInt(st.nextToken());
}
}
tryMagic(N, M, arr);
System.out.println(getAnswer(arr));
}메인에서는 사용자 입력을 받고 tryMagic()을 실행 후 배열의 합을 출력한다.
소스코드
최종 제출한 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
public static int[] dr = {0, -1, -1, -1, 0, 1, 1, 1};
public static int[] dc = {-1, -1, 0, 1, 1, 1, 0, -1};
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static StringTokenizer st;
public static void main(String[] args) throws Exception {
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] arr = new int[N][N];
for(int r=0; r<N; r++) {
st = new StringTokenizer(br.readLine());
for(int c=0; c<N; c++) {
arr[r][c] = Integer.parseInt(st.nextToken());
}
}
tryMagic(N, M, arr);
System.out.println(getAnswer(arr));
}
private static int getAnswer(int[][] arr) {
int sum = 0;
for(int[] r : arr)
for(int i : r)
sum += i;
return sum;
}
private static void tryMagic(int N, int M, int[][] arr) throws Exception {
Stack<int[]> cloudStack = new Stack<>();
Stack<int[]> copyStack = new Stack<>();
boolean[][] cnt;
cloudStack.add(new int[] {N-1, 1});
cloudStack.add(new int[] {N-1, 0});
cloudStack.add(new int[] {N-2, 1});
cloudStack.add(new int[] {N-2, 0});
for(int m=0; m<M; m++) {
st = new StringTokenizer(br.readLine());
int d = Integer.parseInt(st.nextToken())-1;
int t = Integer.parseInt(st.nextToken());
cnt = new boolean[N][N];
rain(d, t, N, arr, cloudStack, copyStack, cnt);
copyWater(N, arr, copyStack);
makeCloud(N, arr, cloudStack, cnt);
}
}
private static void rain(int d, int t, int N, int[][] arr, Stack<int[]> cloudStack, Stack<int[]> copyStack, boolean[][] cnt) {
while(!cloudStack.isEmpty()) {
int[] temp = cloudStack.pop();
int r = (temp[0] + (dr[d]+N)*t)%N;
int c = (temp[1] + (dc[d]+N)*t)%N;
copyStack.add(new int[] {r, c});
arr[r][c]++;
cnt[r][c] = true;
}
}
private static void copyWater(int N, int[][] arr, Stack<int[]> copyStack) {
while(!copyStack.isEmpty()) {
int[] temp = copyStack.pop();
int copy = 0;
for(int i=0; i<4; i++) {
int r = temp[0]+dr[1+2*i];
int c = temp[1]+dc[1+2*i];
if(!rangeCheck(r, c, N) || arr[r][c]==0) continue;
copy++;
}
arr[temp[0]][temp[1]] += copy;
}
}
private static void makeCloud(int N, int[][] arr, Stack<int[]> cloudStack, boolean[][] cnt) {
for(int r=0; r<N; r++) {
for(int c=0; c<N; c++) {
if(!cnt[r][c] && arr[r][c]>=2) {
arr[r][c] -= 2;
cloudStack.add(new int[] {r, c});
}
}
}
}
private static boolean rangeCheck(int y, int x, int N) {
return y>=0 && y<N && x>=0 && x<N;
}
}결과
제출 결과는 다음과 같다.
고찰
테케 해설이 친절하지 않았으면 진짜 키보드 팝콘 만들었을 것 같다… 억지 조건이 너무 많아서 구현 내내 화가 났을 정도…
차라리 깔끔한 조건이 주어진 시뮬레이션이었으면 구현하는 맛이라도 있을 텐데, 이상한 조건이 너무 많아서 구현하면서도 내가 뭘 하나 싶었다.
오엥