[백준 P21610] 마법사 상어와 비바라기 Java
마법사 상어와 비바라기
21610번: 마법사 상어와 비바라기
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기
www.acmicpc.net
문제
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다.
격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에는 N번 행이 있고, 1번 열의 왼쪽에는 N번 열이, N번 열의 오른쪽에는 1번 열이 있다.
비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다. 구름은 칸 전체를 차지한다. 이제 구름에 이동을 M번 명령하려고 한다. i번째 이동 명령은 방향 di과 거리 si로 이루어져 있다. 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다. 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.
- 모든 구름이 d 방향으로 s칸 이동한다.
- 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
- 구름이 모두 사라진다.
- 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
- 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
- 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
- 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.
M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.
입력값
첫째 줄에 N, M이 주어진다.
둘째 줄부터 N개의 줄에는 N개의 정수가 주어진다. r번째 행의 c번째 정수는 A[r][c]를 의미한다.
다음 M개의 줄에는 이동의 정보 di, si가 순서대로 한 줄에 하나씩 주어진다.
- 2 ≤ N ≤ 50
- 1 ≤ M ≤ 100
- 0 ≤ A[r][c] ≤ 100
- 1 ≤ d ≤ 8
- 1 ≤ s≤ 50
5 4
0 0 1 0 2
2 3 2 1 0
4 3 2 9 0
1 0 2 9 0
8 8 2 1 0
1 3
3 4
8 1
4 8
5 8
0 0 1 0 2
2 3 2 1 0
0 0 2 0 0
1 0 2 0 0
0 0 2 1 0
1 9
2 8
3 7
4 6
5 5
6 4
7 3
8 2
5 8
100 100 100 100 100
100 100 100 100 100
100 100 100 100 100
100 100 100 100 100
100 100 100 100 100
8 1
7 1
6 1
5 1
4 1
3 1
2 1
1 1
출력값
첫째 줄에 M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 출력한다.
77
41
2657
알고리즘
전형적인 구현 문제이다. 구현 문제를 풀 때는 문제를 풀기 전에 해야하는 일들을 리스팅하고 풀이를 시작한다. 해당 문제를 풀기 위해서 해야 하는 일들은 다음과 같다.
- 현재 구름이 있는 곳은 물의 양이 1만큼 증가하고, 구름이 사라진다.
- 물 복사 마법을 시전한다.
- 새로운 구름이 만들어진다. 이때 원래 구름이 있던 곳은 구름이 생기지 않는다.
현재 구름이 있는 곳을 저장할 Groom 클래스를 만들고 이를 Queue로 관리했다. 큐에서 Groom이 하나씩 나와서 이동해야 하는 위치로 이동한다. 이때 맵의 행과 열이 연결되어 있으므로 인덱스를 적절하게 처리해줘야 한다. 이를 위해서 현재 구름의 위치와 새로운 구름의 위치를 더한 뒤 N으로 모듈러 연산을 취했다. 3번에서 새로운 구름이 만들어 질 때, 원래 구름이 있던 곳은 구름이 생기지 않기 때문에 원래 구름이 있던 위치를 기록하기 위한 visited 배열을 만들어서 위치를 기록했다.
//1. 구름이 하나씩 나오고 물의 양이 1만큼 && 2. 구름이 모두 사라짐
while (!grooms.isEmpty()) {
Groom g = grooms.poll();
int newR = (S * N + g.r + S * dr[dir]) % N;
int newC = (S * N + g.c + S * dc[dir]) % N;
visited[newR][newC] = true;
map[newR][newC] += 1;
}
물 복사 마법을 시전한다. 만약 visited 배열이 true라면 이 공간에는 구름이 있었다는 얘기이다. 구름이 있는 자리의 좌우상하 대각선 방향를 탐색하여 물이 있는 공간의 갯수만큼 물이 추가된다. 이를 위해 좌우상하 대각선을 탐색하여 물이 있는 공간의 수를 구한다. 최종적으로 그 값을 더해준다. 복사된 물을 현재 상태에 반영한다. 이를 두번의 과정으로 나누어 처리하는 이유는 물을 복사하고 이를 바로 배열에 반영할 경우 기존의 물 상태가 달라져서 다른 결과가 도출될 수 있기 때문이다.
//3. 물 복사 마법 시전
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (visited[r][c]) {
int total = 0;
for (int k = 0; k < 4; k++) {
int newR = r + copyR[k];
int newC = c + copyC[k];
if (0 <= newR && newR < N && 0 <= newC && newC < N) {
if (map[newR][newC] > 0) total++;
}
}
temp[r][c] = total;
}
}
}
//4. 다 더하기
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
map[r][c] += temp[r][c];
}
}
새로운 구름을 만든. 이때 원래 구름이 있던 곳, 즉 visited가 true인 곳은 구름이 생기지 않는다. 구름이 생긴 곳은 물의 양을 2 빼준다.
//5. 새로운 구름 만들기
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (map[r][c] >= 2 && !visited[r][c]) {
grooms.add(new Groom(r, c));
map[r][c] -= 2;
}
}
}
이를 M번 반복하고 물의 최종 상태 배열을 탐색하여 물의 총 합을 구한다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int[] dr = {0, 0, -1, -1, -1, 0, 1, 1, 1};
static int[] dc = {0, -1, -1, 0, 1, 1, 1, 0, -1};
static int[] copyR = {-1, -1, 1, 1};
static int[] copyC = {-1, 1, 1, -1};
static int N, M, dir, S;
static int[][] map;
static Queue<Groom> grooms = new ArrayDeque<>();
public static void main(String[] args) throws Exception {
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][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
grooms.add(new Groom(N - 1, 0));
grooms.add(new Groom(N - 1, 1));
grooms.add(new Groom(N - 2, 0));
grooms.add(new Groom(N - 2, 1));
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
dir = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
boolean[][] visited = new boolean[N][N];
int[][] temp = new int[N][N];
//1. 구름이 하나씩 나오고 물의 양이 1만큼 && 2. 구름이 모두 사라짐
while (!grooms.isEmpty()) {
Groom g = grooms.poll();
int newR = (S * N + g.r + S * dr[dir]) % N;
int newC = (S * N + g.c + S * dc[dir]) % N;
visited[newR][newC] = true;
map[newR][newC] += 1;
}
//3. 물 복사 마법 시전
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (visited[r][c]) {
int total = 0;
for (int k = 0; k < 4; k++) {
int newR = r + copyR[k];
int newC = c + copyC[k];
if (0 <= newR && newR < N && 0 <= newC && newC < N) {
if (map[newR][newC] > 0) total++;
}
}
temp[r][c] = total;
}
}
}
//4. 다 더하기
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
map[r][c] += temp[r][c];
}
}
//5. 새로운 구름 만들기
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (map[r][c] >= 2 && !visited[r][c]) {
grooms.add(new Groom(r, c));
map[r][c] -= 2;
}
}
}
}
int total = 0;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
total += map[r][c];
}
}
System.out.println(total);
}
}
class Groom {
int r, c;
Groom(int r, int c) {
this.r = r;
this.c = c;
}
}