https://www.acmicpc.net/problem/21610
1. 아이디어
구현, 시뮬레이션
- 구름 칸 이동 -> 이동한 구름 칸에서 비 내리기 -> 물 복사 버그 시전 (대각선 확인) -> 새로운 구름 칸 생성
1) 각 구름 칸이 d 방향으로 s 칸 이동
- 큐에서 구름 좌표들을 꺼내서 차례로 이동
y < 1이 되면y = n처리 (맨 아래 행으로 보냄)y > n이 되면,y = 1처리 (맨 윗 행으로 보냄)x < 1이 되면,x = n처리 (맨 오른쪽 열로 보냄)x > n이 되면,x = 1처리 (맨 왼쪽 열로 보냄)
2) 각 구름 칸에서 비가 내림 => 바구니의 물 양 +1
- 이동한 구름 좌표 바구니에
map[i][j]++
3) 모든 구름 소멸
4) 2에서 물이 증가한 칸 [r][c] (이동한 구름 칸)에 물복사버그 마법
: 대각선 방향 1칸에 존재하는 물이 든 바구니 개수만큼 [r][c] 바구니의 물 양 증가
- 큐에서 구름 좌표들을 차례로 꺼내서 대각선 바구니들 확인
- 큐의 구름 좌표들에 대해
visited[][]방문 처리 (새로운 구름 칸 생성 전, 현재 구름 칸 좌표 체크)
5) 바구니에 저장된 물 양이 2 이상인 모든 칸에 구름 생성되고, 물 양 -2
: 구름 생성 칸은 3에서 구름이 사라진 칸이 아니어야 함 (기존 구름 칸이 아니어야 함)
=> 기존 구름 칸 제외, 물 양이 2 이상인 곳이 새로운 구름 칸이 됨
!visited[기존 구름 칸 y][기존 구름 칸 x]이고,map[i][j] >= 2인 칸
2. 자료구조
Queue<Point>,LinkedList<Point>: 구름 좌표 큐boolean[][] visited: 방문 처리 (구름 이동 전의 구름 좌표 체크)
※ 문제 핵심
1)Queue<Point>를 이용한 구름 칸 시뮬레이션 처리
- 구름 칸 이동, 비 내리기, 새로운 구름 칸 생성(추가)
2) 2차원 방문 처리 배열:
boolean[][] visited
코드
import java.io.*;
import java.util.*;
class Operation {
public int d, s; // 명령: 방향, 거리
public Operation(int d, int s) {
this.d = d;
this.s = s;
}
}
class Point {
public int y, x;
public Point(int y, int x) {
this.y = y;
this.x = x;
}
}
public class Main {
static int n; // n x n 행렬
static int m; // 구름에 m번 명령(방향 d, 거리 s)
static int[][] map;
static Operation[] operations; // m개 명령
static int resultSum; // 출력, 바구니에 든 물 양의 합
// 대각선 방향 index: [2], [4], [6], [8]
static int[] dy = { 0, 0, -1, -1, -1, 0, 1, 1, 1 }; // 이동 8개 방향, [1] ~ [8] 사용
static int[] dx = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
static boolean[][] visited;
static Queue<Point> queue = new LinkedList<>(); // 구름 좌표 큐
static void solution() {
// 각 명령 수행
for (Operation op : operations) {
visited = new boolean[n + 1][n + 1]; // 방문 배열 초기화
// 각 구름 칸을 명령에 따라 이동 시킨 후, 비를 내림
int qSize = queue.size();
for (int i = 0; i < qSize; i++) {
Point cloudPoint = queue.remove();
int ny = cloudPoint.y;
int nx = cloudPoint.x;
// 1) 구름 칸 이동: op.d 방향으로 op.s 칸 만큼 이동
for (int j = 0; j < op.s; j++) {
ny += dy[op.d];
nx += dx[op.d];
if (ny < 1) ny = n;
else if (ny > n) ny = 1;
if (nx < 1) nx = n;
else if (nx > n) nx = 1;
}
queue.add(new Point(ny, nx)); // 큐에 이동한 구름 칸 추가 (구름 칸 이동 반영)
// 2) 이동한 구름 칸에서 비 내리기 => 바구니의 물 양 +1
map[ny][nx]++;
}
// 3) 모든 구름 소멸: while 문 실행하면, queue empty
// 4) 물 복사 버그 시전
while (!queue.isEmpty()) {
Point cloudPoint = queue.remove();
int waterBasketCount = 0; // 구름 칸 기준, 대각선 방향의 물이 든 바구니 개수
for (int i = 2; i <= 8; i += 2) { // 대각선 4개 방향 확인
int ny = cloudPoint.y + dy[i];
int nx = cloudPoint.x + dx[i];
if (isValid(ny, nx) && map[ny][nx] > 0) {
waterBasketCount++;
}
}
visited[cloudPoint.y][cloudPoint.x] = true; // 구름 위치 표시
map[cloudPoint.y][cloudPoint.x] += waterBasketCount;
}
// 5) 새로운 구름 칸 생성
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// 현재 구름 칸이 아니고, 물이 2 이상 든 바구니 => 새로운 구름 칸
if (!visited[i][j] && map[i][j] >= 2) {
map[i][j] -= 2;
queue.add(new Point(i, j));
}
}
}
}
}
static boolean isValid(int ny, int nx) {
return (1 <= ny && ny <= n) && (1 <= nx && nx <= n);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in)
);
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
map = new int[n + 1][n + 1]; // [1][1] ~ [n][n] 사용
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
operations = new Operation[m];
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int d = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
operations[i] = new Operation(d, s);
}
// 큐에 초기 4개 구름 칸 추가
queue.add(new Point(n, 1));
queue.add(new Point(n, 2));
queue.add(new Point(n - 1, 1));
queue.add(new Point(n - 1, 2));
solution();
// 물 양 카운트
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (map[i][j] > 0)
resultSum += map[i][j];
}
}
System.out.println(resultSum);
}
}
Silver Star