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

문제 설명

• https://www.acmicpc.net/problem/21610
  • 해당 링크에 위 사진보다 더 상세한 그림 설명이 포함되어 있습니다. 지면관계상 생략했습니다.
• 주어진 조건에 맞게 구현하는 문제입니다.

접근법

• 2차원 배열을 탐색할 때 다음의 두 가지를 신경써야 합니다.
  • 범위를 넘어갔을 때 다시 반대방향으로 넘어오는 방법
  • d방향이 음수일 때 인덱싱을 처리하는 방법
• 조건을 만족하는 값을 구했을 때 그자리에서 바로 값을 변화시켜야 하는지, 모아뒀다가 한번에 처리해야 하는지를 고민해야 합니다.
  • 물복사 부분에서 즉시 복사를 하면 대각선으로 인접한 다른 바구니의 값에 영향을 미치기 때문에 모아뒀다가 한번에 처리해야 합니다.

pseudocode

정확도를 측정하기 위해 메서드 구현 없이 풀어봤습니다.
메서드로 구현하는 게 디버깅에 엄청난 시간단축이 됩니다.
메서드 구현이 아니므로 각 구간에 대한 설명은 정답코드의 주석으로 대신하겠습니다.

정답

import java.util.*;

public class Main {
	static int[][] board;
	static int[] dx = { 0, -1, -1, -1, 0, 1, 1, 1 };
	static int[] dy = { -1, -1, 0, 1, 1, 1, 0, -1 };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		board = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = sc.nextInt();
			}
		}
		// 최초 생성된 구름입니다.
		List<pos> CloudLst = new ArrayList<pos>();
		CloudLst.add(new pos(N - 1, 0));
		CloudLst.add(new pos(N - 2, 0));
		CloudLst.add(new pos(N - 1, 1));
		CloudLst.add(new pos(N - 2, 1));

		for (int m = 0; m < M; m++) { // M번의 이동이 발생합니다.
			boolean[][] v = new boolean[N][N];
			int d = sc.nextInt(); 
			d--; // d는 1~8로 들어오기 때문에 인덱스로 활용하기 위해 -1을 실행합니다.
			int s = sc.nextInt();
			int size = CloudLst.size();
			List<pos> CheckLst = new ArrayList<pos>();

			// 구름 이동
			for (int idx = 0; idx < size; idx++) {
				pos c = CloudLst.remove(0);
				int nx = c.x;
				int ny = c.y;
				
				// d방향으로 s만큼 움직입니다.
				for (int i = 0; i < s; i++) {
					// dx가 마이너스라서 음수가 나오는 걸 방시하기위해 0이될때마다 새롭게 N을 더해줍니다.
					if (nx == 0) {
						nx += N;
					}

					if (ny == 0) {
						ny += N;
					}

					nx = (nx + dx[d]) % N;
					ny = (ny + dy[d]) % N;
				}

//				int nx = (N*N*N+c.x+dx[d]*s)%N;
//				int ny = (N*N*N+c.y+dy[d]*s)%N;
				
				v[nx][ny] = true; // 이번에 구름이 위치한 곳에서는 다음 구름이 발생하지 않습니다.
				board[nx][ny] += 1;
				CheckLst.add(new pos(nx, ny));
			}

//			System.out.println("구름 이동");
//			for (int i = 0; i < N; i++) {
//				System.out.println(Arrays.toString(board[i]));
//			}			

			// 물복사
			for (int c = 0; c < CheckLst.size(); c++) {
				int cnt = 0;
				for (int d2 = 0; d2 < 8; d2++) {
					if (d2 % 2 == 0)
						continue;
					int nx = CheckLst.get(c).x + dx[d2];
					int ny = CheckLst.get(c).y + dy[d2];
					if (0 <= nx && nx < N && 0 <= ny && ny < N && board[nx][ny] != 0) { // 구름의 이동과 다르게 경계를 넘어갈 수 없습니다.
						cnt++;
					}
				}
				board[CheckLst.get(c).x][CheckLst.get(c).y] += cnt;
			}

//			System.out.println("물복사");
//			for (int i = 0; i < N; i++) {
//				System.out.println(Arrays.toString(board[i]));
//			}

			// 구름생성
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (board[i][j] >= 2 && !v[i][j]) {
						CloudLst.add(new pos(i, j));
						board[i][j] -= 2;
					}
				}
			}

//			System.out.println("구름생성");
//			for (int i = 0; i < N; i++) {
//				System.out.println(Arrays.toString(board[i]));
//			}

		}
		
		// 최종 점수를 계산합니다
		int Score = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				Score += board[i][j];
			}
		}
		System.out.println(Score);
	}

	static class pos {
		int x;
		int y;

		@Override
		public String toString() {
			return "pos [x=" + x + ", y=" + y + "]";
		}

		public pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

	}
}

기타

음수 인덱싱

d방향으로 s만큼 이동한다고 했을 때

• 원래 하던 방법: N의 배수를 더한다.
  • 문제점: 얼마나 큰 N의 배수를 더해야 할지 모른다. StackOverFlow위험
  • 예시) 마법사 상어와 파이어볼
• 새로운 방식: 1씩 더하면서 0이 되었을때마다 N을 더한다.
  • 문제점: s크기만큼의 반복문이 수행되어야 함.
  • 예시) 이번문제