문제 바로가기

https://www.acmicpc.net/problem/21610

문제 소개 및 재정의

N X N 격자가 있다. 각 cell에는 바구니가 있고.
여기에는 물이 무한히 저장된다.
A[r][c] 는 r행 c열에 있는 바구니의 물의 양이다.
격자의 맨위와 맨아래 행은 고리형태로 연결돼있다.
격자의 맨 오른쪽과 맨 왼쪽 행은 고리형태로 연결돼있다.
.
처음 비바라기를 시전하면 좌하단 귀퉁이에 4개의 비구름이 생긴다.
.
각 명령에는 이동방향과 이동거리가 있음.
명령의 절차는 다음과 같음.
.
1. 모든 구름이 di 방향으로 si칸 이동한다.
.
2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
.
3. 구름이 모두 사라진다.
.
4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다.
물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼
(r, c)에 있는 바구니의 물이 양이 증가한다.
!! 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
.
5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

문제 패턴

어떻게 풀까? - 시뮬레이션

포인트

구름의 이동 구현
구름을 이동시키고 작업을 한 다음에, 해당 위치의 구름을 없앤다고 생각하니까.
도착한 곳에 이미 구름이 있을때 문제가 되지 않을까란 생각이 들었다.
이동한 곳에 구름이 있을때를 대비하자.
구름을 이동 시키고 해당 자리를 방문처리하자.
기존에 있던 구름도 이동시키고 이동된 자리를 방문처리하자.
그러면 모든 구름이 이동된 곳이 방문처리가 될것이다.
방문처리가 된 곳에 비를 내리면 된다.
.
보드를 두개 써야하나?
이전 구름 방문 배열과 이후 구름 방문 배열
.
방문 배열을 하나만 쓸거라면, 방문처리는 현재 round값으로 갱신하는 것으로 하자.
구름이 있는 위치를 List에 저장해두고, List를 순회하면서 해당 격자에서 이동시켜서 이동한 위치의 방문배열을 갱신하는 방법.
근데 ArrayList.clear()할때 메모리가 어떻게 되는지 모르겠네.
메모리 어딘가에 쌓여있다가 나중에 G.C.되나? 아니면 바로 메모리 반납하나?

물복사 버그 마법 구현
단순하게 적힌 그대로 구현하자.

구름의 생성 구현

• 물의 양이 2이상인지 확인.
• 직전에 구름이 사라진 칸이 아닌지 확인. => 라운드 개념 도입.
• 둘다 통과하면 구름 생성.

의식의 흐름

코드

package study.week13;

import java.io.*;
import java.util.*;

public class BOJ_21610_마법사상어와비바라기2 {
	// 입력고정
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	// 세팅
	static int N;
	static int M;
	static int[][] origin;
	static int[][] visit;
	static int[][] cmd;
	static int round;
	static int[][] deltas = {{0,-1},{-1,-1}, {-1,0},{-1,+1}, {0,+1},{+1,+1}, {+1,0},{+1,-1}}; // deltas[cmd-1][0]
	static ArrayList<int[]> clouds = new ArrayList<>();
	
	
	// 메소드
	//// 구름의 생성
	static void make() {
		// 구름의 생성이 새로운 round의 기준임.
		round++; // 새 round 업데이트
		clouds.clear();
		// 구름 현재 위치 저장
		for (int row = 0; row < N; row++) {
			for (int col = 0; col < N; col++) {
				if( (visit[row][col]!=round-1) && (origin[row][col]>=2) ) { // 이전 라운드에 구름이 도착한 곳이 아니고, 물이 2이상 있는 곳이라면. 구름생성
					clouds.add(new int[]{row,col});
					origin[row][col] -=2;
				}
			}
		}
//		debug("after make");
	}
	//// 구름의 이동 (%N 하면 되는거 아님?)
	static void move(int direction, int distance) {
		// 비내리기 먼저 다하고 그 다음에 물복사버그 써야 데이터의 일관성이 유지됨. 그게 규칙임.
		// 구름이 도착할때마다 물복사 버그 쓸때는 대각선 위치에 물이 없던곳이어도. 모든 구름이 비내리기를 다 하고 나서 물복사 버그 쓸때는 그곳에 물이 있을수도 있음. 
		for (int i = 0; i < clouds.size(); i++) {
			// 구름이 도착할 위치 계산
			int x = clouds.get(i)[0];
			int y = clouds.get(i)[1];
			int dx = deltas[direction-1][0]*distance;
			int dy = deltas[direction-1][1]*distance;
			int nx = x +dx;
			int ny = y +dy;
			
			// 상하좌우 연결하는 스킬 
			//// 디버깅 포인트 1. 
			//// 먼저 나머지를 구하자. nx가 아주 큰 음수일때 한번의 +N으로 정상범위에 들어올수 있도록. 
			//// 그리고 N을 더해주자. 
			//// 그리고 한번더 %N을 해주자. 이미 정상범위라면 +N하면서 정상범위 밖으로 나가니까. 
			//// 이러면 5칸 짜리에서 -100칸 뒤로 가는것도 계산가능하다.
			nx = ((nx%N)+N)%N;
			ny = ((ny%N)+N)%N;
			
			// 비 내리기.
			origin[nx][ny] +=1;
			// 구름 사라짐.
			//// 현재 round를 저장해서, 가장 최근에 방문한 곳임을 구분
			visit[nx][ny] = round;
		}
		// 물복사 버그
		for (int i = 0; i < clouds.size(); i++) {
			// 구름이 도착할 위치 계산
			int x = clouds.get(i)[0];
			int y = clouds.get(i)[1];
			int dx = deltas[direction-1][0]*distance;
			int dy = deltas[direction-1][1]*distance;
			int nx = x +dx;
			int ny = y +dy;
			// 상하좌우 연결하는 스킬
			nx = ((nx%N)+N)%N;
			ny = ((ny%N)+N)%N;
			// 물복사 버그 사용 시점
			int bonus = bug(nx, ny);
			origin[nx][ny] += bonus;
		}
		debug("after move");
	}
	//// 물복사 버그
	static int bug(int x, int y) {
		int sum = 0;
		for (int i = 0; i < 4; i++) {
			int diagonalIndex = i*2+1; // 기존 deltas에서 인덱스가 홀수면 대각방향인 것을 활용.
			int dx = deltas[diagonalIndex][0];
			int dy = deltas[diagonalIndex][1];
			int nx = x+dx;
			int ny = y+dy; // 디버깅 포인트 2. ny = x+dy 이따구로 적어둠.
			if( (0<=nx && nx<N) && (0<=ny && ny<N) && (origin[nx][ny]>0) ) { // 보드 안에 있는 격자이고. 격자에 물이 있을때
				sum++;
			}
		}
		return sum;
	}

	// 메인
	public static void main(String[] args) throws Exception {
		// 입력
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		origin = new int[N][N];
		visit = new int[N][N];
		cmd = new int[M][2];
		//// 격자칸 받기
		for (int row = 0; row < N; row++) {
			tokens = new StringTokenizer(input.readLine());
			for (int col = 0; col < N; col++) {
				origin[row][col] = Integer.parseInt(tokens.nextToken());
			}
		}
		//// 명령어 집합 받기
		for (int i = 0; i < M; i++) {
			tokens = new StringTokenizer(input.readLine());
			cmd[i][0] = Integer.parseInt(tokens.nextToken());
			cmd[i][1] = Integer.parseInt(tokens.nextToken());
		}
		// 세팅
		debug("first");
		//// 최초의 구름 생성.
		round++; // 구름 생성할때 round가 새로 시작됨.
		//// 디버깅 포인트 3. 최초 구름 스폰지역들을 리터럴로 그대로 넣었음. (N,1), (N,2) 이렇게. 인덱스에 맞게 -1씩 해줬어야함.
		clouds.add(new int[] {(N)-1,1-1});
		clouds.add(new int[] {(N)-1,2-1});
		clouds.add(new int[] {(N-1)-1,1-1});
		clouds.add(new int[] {(N-1)-1,2-1});

		// 작업
		//// 디버깅 포인트 4.  작업순서 헷갈림. 구름의 생성이 작업의 마무리인데, 작업의 시작이라고 착각함.  
		for (int i = 0; i < cmd.length; i++) {
			int direction = cmd[i][0];
			int distance= cmd[i][1];
			move(direction, distance);
			make();
		}
		//// 합계 계산
		int sum = 0;
		for (int row = 0; row < N; row++) {
			for (int col = 0; col < N; col++) {
				sum += origin[row][col];
			}
		}
		// 출력
		System.out.println(sum);
		
	} // 메인 종료
	
	// 디버깅 스킬.
	//// 각 함수의 호출에 따라 상태를 관찰하고 싶을때.
	//// 해당 함수 맨 마지막에 debug 코드 삽입. 어떤 함수가 불렀는지 구분하는 문자열도 그 함수에 넣어두면. 디버깅 코드 유지보수가 편해짐.
	//// 제출할때는 debug() 내부를 주석처리하면 작동안함.
	static void debug(String funcName) {
//		for (int i = 0; i < N; i++) {
//			System.out.println(Arrays.toString(origin[i]));
//		}
//		System.out.println("========================="+funcName);
	}
}

퍼포먼스

[ 17,520KB | 144ms ]

마무리

각각의 디버깅 포인트를 주의하는 연습이 필요한것 같다.
문제를 잘 읽고.
코드를 카피&페이스트 했으면 잘 수정하고.
인덱스로 변환할때 잘 하고.
대체로 잘 하는 것들인데 가끔 실수 나는곳들이다.

잘한 포인트
deltas에서 대각방향만 잘 추출해서 쓴것.
끝과 끝을 연결하는 로직.
디버깅 함수 사용.