Algorithm/Problem
마법사 상어와 비바라기(BJ_G5_21610)
당진개발자
2024. 2. 24. 17:52
1. 문제 링크
https://www.acmicpc.net/problem/21610
21610번: 마법사 상어와 비바라기
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기
www.acmicpc.net
2. 나의 코드
메모리: 22864kb
시간: 264ms
코드 길이: 3527B
시간 복잡도 : O(M * N^2)
설명
- 모든 구름을 이동
- 이동한 좌표를 방문처리
- 이동한 곳을 기준으로 대간선으로 탐import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class BJ_21610 {
static class Cloud {
int r, c;
public Cloud(int r, int c) {
this.r = r;
this.c = c;
}
}
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[] diagonal = {2, 4, 6, 8}; // 대각선의 인덱스 번호
static int N, M; // N : 가로,세로 길이 M : 이동 횟수
static int[][] water; // 물의 양을 저장하는 배열
static Queue<Cloud> clouds; // 이동할 구름들
static boolean[][] visited; // 이동을 마친 구름들의 좌표
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());
water = new int[N][N];
clouds = new LinkedList<>();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
water[i][j] = Integer.parseInt(st.nextToken());
}
}
// 최초 구름 생성
for (int i = N - 2; i < N; i++) for (int j = 0; j < 2; j++) clouds.offer(new Cloud(i, j));
// 명령 시작
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
solve(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
}
System.out.println(sumCloud());
}
private static int sumCloud() {
return Arrays.stream(water)
.flatMapToInt(Arrays::stream)
.sum();
}
// 구름 이동시켜서 비를 내리게 하고 구름을 없애는 메서드
private static void solve(int d, int s) { // d : 방향, s : 거리
visited = new boolean[N][N];
while (!clouds.isEmpty()) {
Cloud nowCloud = clouds.poll();
int nr = (nowCloud.r + N + dr[d] * (s % N)) % N;
int nc = (nowCloud.c + N + dc[d] * (s % N)) % N;
visited[nr][nc] = true; // 이동한 곳의 좌표를 방문처리
water[nr][nc] += 1; // 이동한 곳 비내리기
}
// 이동한 구름들의 대각선을 확인 후 비내리게 하기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (visited[i][j]) {
for (int idx : diagonal) {
int nr = i + dr[idx];
int nc = j + dc[idx];
if (isValid(nr, nc) && water[nr][nc] != 0) ++water[i][j];
}
}
}
}
// 구름 생성하기
makeCloud();
}
// 구름 생성하는 메서드
private static void makeCloud() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visited[i][j] && water[i][j] >= 2) {
clouds.offer(new Cloud(i, j));
water[i][j] = Math.max((water[i][j] - 2), 0);
}
}
}
}
// 맵을 벗어났는지 여부 체크
private static boolean isValid(int r, int c) {
return 0 <= r && r < N && 0 <= c && c < N;
}
}
3. 정답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int n, m, map[][];
static int[] dx = { 0, -1, -1, -1, 0, 1, 1, 1 };
static int[] dy = { -1, -1, 0, 1, 1, 1, 0, -1 };
static List<Cloud> list; // 구름을 관리하는 리스트
static boolean[][] isCloud; // 삭제된 구름의 위치에 구름을 생성하지 않도록 상태 저장 하는 배열
static class Cloud {
int x;
int y;
Cloud(int x, int y) {
this.x = x;
this.y = y;
}
}
static void moveAndRain(int d, int s) { // 이동 후 비를 내림
isCloud = new boolean[n][n];
for (Cloud cloud : list) {
cloud.x = (n + cloud.x + (dx[d] * s) % n) % n; // 이동
cloud.y = (n + cloud.y + (dy[d] * s) % n) % n; // 이동
map[cloud.x][cloud.y]++; // 이동된 위치에 비 내림
isCloud[cloud.x][cloud.y] = true; // 위치 저장
}
copyWater(); // 물 복사 버그
list.clear(); // 구름 다 삭제
}
static void copyWater() { // 물을 복사
for (Cloud cloud : list) {
for (int i = 0; i < 4; i++) {
int nx = cloud.x + dx[i * 2 + 1];
int ny = cloud.y + dy[i * 2 + 1];
if (isIn(nx, ny) && map[nx][ny] != 0) { // 대각선 방향으로 물이 있으면
map[cloud.x][cloud.y]++; // 물 추가
}
}
}
}
static boolean isIn(int x, int y) {
return x >= 0 && y >= 0 && x < n && y < n;
}
static void makeCloud() { // 구름을 생성
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] >= 2 && !isCloud[i][j]) { // 물이 2이상이 있고 구름이 있던 위치가 아니면
list.add(new Cloud(i, j)); // 구름 생성
map[i][j] -= 2;
}
}
}
}
static int getWater() { // 구름의 총합
int water = 0;
for (int i = 0; i < n; i++) {
water += Arrays.stream(map[i]).sum();
}
return water;
}
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][];
list = new ArrayList<>();
for (int i = 0; i < n; i++) {
map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
for (int i = n - 2; i < n; i++) {
for (int j = 0; j < 2; j++) {
list.add(new Cloud(i, j));
}
}
while (m-- > 0) {
st = new StringTokenizer(br.readLine());
int d = Integer.parseInt(st.nextToken()) - 1;
int s = Integer.parseInt(st.nextToken());
moveAndRain(d, s);
makeCloud();
}
int answer = getWater();
System.out.println(answer);
}
}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, M, answer;
static int[] dr = {0, -1, -1, -1, 0, 1, 1, 1};
static int[] dc = {-1, -1, 0, 1, 1, 1, 0, -1};
static int[][] map;
static Queue<Cloud> clouds;
static Move[] moves;
static class Cloud {
int r, c;
public Cloud(int r, int c) {
this.r = r;
this.c = c;
}
}
static class Move {
int d, s;
public Move(int d, int s) {
this.d = d;
this.s = s;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
// 초기 세팅
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][N];
moves = new Move[M];
clouds = new ArrayDeque<>();
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());
}
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
moves[i] = new Move(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()));
}
play();
// 바구니에 들어있는 물의 양 합 구하기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
answer += map[i][j];
}
}
System.out.println(answer);
}
private static void play() {
boolean[][] visited;
// 비바라기 시전
for (int i = N - 2; i < N; i++) {
for (int j = 0; j < 2; j++) {
clouds.offer(new Cloud(i, j));
}
}
// M번 명령 반복
for (int time = 0; time < M; time++) {
int d = moves[time].d;
int s = moves[time].s;
int cloudsSize = clouds.size();
visited = new boolean[N][N];
// 생성된 구름 개수만큼 반복
for (int idx = 0; idx < cloudsSize; idx++) {
Cloud cloud = clouds.poll();
// 1. 모든 구름이 d방향으로 s칸 이동한다.
int nr = cloud.r + dr[d] * (s % N);
int nc = cloud.c + dc[d] * (s % N);
if (nr > 0) {
nr %= N;
} else if (nr < 0) {
nr += N;
}
if (nc > 0) {
nc %= N;
} else if (nc < 0) {
nc += N;
}
cloud.r = nr;
cloud.c = nc;
// 2~3. 구름에서 비가 내려 바구니의 물이 1 증가하고 구름이 사라진다.
map[nr][nc]++;
visited[nr][nc] = true;
}
// 4. 물복사버그 마법을 시전한다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (visited[i][j]) {
for (int dir = 1; dir < 8; dir += 2) {
if (isIn(i + dr[dir], j + dc[dir]) && map[i + dr[dir]][j + dc[dir]] > 0) {
map[i][j]++;
}
}
}
}
}
// 5. 구름이 생기고 물의 양이 줄어든다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] >= 2 && !visited[i][j]) {
clouds.offer(new Cloud(i, j));
map[i][j] -= 2;
}
}
}
}
}
private static boolean isIn(int r, int c) {
return r >= 0 && c >= 0 && r < N && c < N;
}
}
4. 배운 점
- 전형적인 시물레이션 문제이다. 이렇게 이동하는 객체가 많을 경우는 모두 이동 시킨뒤 후처리 하는게 더 좋은 것 같다.
- 배열의 합을 구할 때는 다음과 같은 Stream을 쓰는 연습을 많이 하면 좋을 것 같다.
- Arrays.stream : 배열 >> 스트림
- flatMaptoInt : 2차원 배열 >> 1차원 배열
Arrays.stream(water)
.flatMapToInt(Arrays::stream)
.sum();