[백준 / JAVA] 21610. 마법사 상어와 비바라기 (G5)

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

21610번: 마법사 상어와 비바라기

 

단순 구현이지만 다른 어려운 문제들에 사용할 만한 기법들을 연습하기 좋은 문제라고 느껴졌다. 특히 배열 밖으로 나가면 반대쪽에서 들어오는 부분 구현이 유익했다.

 

정답이 맞으면 코드를 정리해서 다시 제출한다.

 

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

public class Main {
	static BufferedReader br;
	static StringTokenizer st;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		int m = Integer.parseInt(st.nextToken());
		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());
		}
		dq.add(new Cloud(N - 2, 0));
		dq.add(new Cloud(N - 2, 1));
		dq.add(new Cloud(N - 1, 0));
		dq.add(new Cloud(N - 1, 1));
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			move(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) % N);
		}
		System.out.println(calcWater());
	}

	static int N, map[][], dr[] = { 0, -1, -1, -1, 0, 1, 1, 1 }, dc[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static Deque<Cloud> dq = new ArrayDeque<>();

	static int calcWater() {
		int water = 0;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				water += map[i][j];
		return water;
	}

	static void move(int direction, int distance) {
		boolean visited[][] = new boolean[N][N];
		for (Cloud c : dq) {
			c.row += distance * dr[direction];
			c.col += distance * dc[direction];
			if (c.row < 0)
				c.row = N + c.row;
			if (c.col < 0)
				c.col = N + c.col;
			if (c.row >= N)
				c.row = c.row - N;
			if (c.col >= N)
				c.col = c.col - N;
			map[c.row][c.col]++;
			visited[c.row][c.col] = true;
		}
		while (!dq.isEmpty()) {
			Cloud c = dq.poll();
			int count = 0;
			for (int d = 1; d < 8; d += 2) {
				int nr = c.row + dr[d];
				int nc = c.col + dc[d];
				if (nr < 0 || nc < 0 || nr >= N || nc >= N)
					continue;
				if (map[nr][nc] > 0)
					count++;
			}
			map[c.row][c.col] += count;
		}
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				if (map[i][j] > 1 && !visited[i][j]) {
					dq.add(new Cloud(i, j));
					map[i][j] -= 2;
				}
	}

	static class Cloud {
		int row, col;

		public Cloud(int row, int col) {
			super();
			this.row = row;
			this.col = col;
		}
	}
}