[백준/골드1] 23290. 마법사 상어와 복제

문제

---

문제

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기, 블리자드 마법을 할 수 있다. 오늘은 기존에 배운 물복사버그 마법의 상위 마법인 복제를 배웠고, 4 × 4 크기의 격자에서 연습하려고 한다. (r, c)는 격자의 r행 c열을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (4, 4)이다.

격자에는 물고기 M마리가 있다. 각 물고기는 격자의 칸 하나에 들어가 있으며, 이동 방향을 가지고 있다. 이동 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다. 마법사 상어도 연습을 위해 격자에 들어가있다. 상어도 격자의 한 칸에 들어가있다. 둘 이상의 물고기가 같은 칸에 있을 수도 있으며, 마법사 상어와 물고기가 같은 칸에 있을 수도 있다.

상어의 마법 연습 한 번은 다음과 같은 작업이 순차적으로 이루어진다.

1. 상어가 모든 물고기에게 복제 마법을 시전한다. 복제 마법은 시간이 조금 걸리기 때문에, 아래 5번에서 물고기가 복제되어 칸에 나타난다.
2. 모든 물고기가 한 칸 이동한다. 상어가 있는 칸, 물고기의 냄새가 있는 칸, 격자의 범위를 벗어나는 칸으로는 이동할 수 없다. 각 물고기는 자신이 가지고 있는 이동 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기의 냄새는 아래 3에서 설명한다.
3. 상어가 연속해서 3칸 이동한다. 상어는 현재 칸에서 상하좌우로 인접한 칸으로 이동할 수 있다. 연속해서 이동하는 칸 중에 격자의 범위를 벗어나는 칸이 있으면, 그 방법은 불가능한 이동 방법이다. 연속해서 이동하는 중에 상어가 물고기가 있는 같은 칸으로 이동하게 된다면, 그 칸에 있는 모든 물고기는 격자에서 제외되며, 제외되는 모든 물고기는 물고기 냄새를 남긴다. 가능한 이동 방법 중에서 제외되는 물고기의 수가 가장 많은 방법으로 이동하며, 그러한 방법이 여러가지인 경우 사전 순으로 가장 앞서는 방법을 이용한다. 사전 순에 대한 문제의 하단 노트에 있다.
4. 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
5. 1에서 사용한 복제 마법이 완료된다. 모든 복제된 물고기는 1에서의 위치와 방향을 그대로 갖게 된다.

격자에 있는 물고기의 위치, 방향 정보와 상어의 위치, 그리고 연습 횟수 S가 주어진다. S번 연습을 모두 마쳤을때, 격자에 있는 물고기의 수를 구해보자.

입력

첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향은 8 이하의 자연수로 표현하고, 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 마지막 줄에는 sx, sy가 주어지며, 상어가 (sx, sy)에 있음을 의미한다.

격자 위에 있는 물고기의 수가 항상 1,000,000 이하인 입력만 주어진다.

출력

S번의 연습을 마친 후 격자에 있는 물고기의 수를 출력한다.

제한

• 1 ≤ M ≤ 10
• 1 ≤ S ≤ 100
• 1 ≤ fx, fy,sx, sy ≤ 4
• 1 ≤ d ≤ 8
• 두 물고기 또는 물고기와 상어가 같은 칸에 있을 수도 있다.

노트

상어의 이동 방법 중 사전 순으로 가장 앞서는 방법을 찾으려면 먼저, 방향을 정수로 변환해야 한다. 상은 1, 좌는 2, 하는 3, 우는 4로 변환한다. 변환을 모두 마쳤으면, 수를 이어 붙여 정수로 하나 만든다. 두 방법 A와 B가 있고, 각각을 정수로 변환한 값을 a와 b라고 하자. a < b를 만족하면 A가 B보다 사전 순으로 앞선 것이다.

예를 들어, [상, 하, 좌]를 정수로 변환하면 132가 되고, [하, 우, 하]를 변환하면 343이 된다. 132 < 343이기 때문에, [상, 하, 좌]가 [하, 우, 하]보다 사전 순으로 앞선다.

총 43 = 64가지 방법을 사전 순으로 나열해보면 [상, 상, 상], [상, 상, 좌], [상, 상, 하], [상, 상, 우], [상, 좌, 상], [상, 좌, 좌], [상, 좌, 하], [상, 좌, 우], [상, 하, 상], ..., [우, 하, 하], [우, 하, 우], [우, 우, 상], [우, 우, 좌], [우, 우, 하], [우, 우, 우] 이다.

 

백준에서 문제 보기

풀이

---

접근 방법

• 딱 문제를 읽자마자 빡빡한 구현이라는 건 알 수 있다.
• 문제를 자세히 읽고 그림을 그려서 이해를 해야 한다.
• 일단 크게 연습을 네 단계로 나눌 수 있다.

1. 물고기를 옮기고 다른 배열에 저장하기
2. 가장 많이 먹을 수 있는 방법 정하기
3. 최적 경로로 가면서 먹은 곳을 삭제하기, 냄새를 남기기, 상어 옮기기
4. 배열 두 개를 합치기

• 처음에는 물고기를 2차원 ArrayList에 저장해서 풀고 있었다. 하지만 예제 8번을 보니 출력이 574418 이었고.. ArrayList로 하나하나 옮긴다면 시간 초과가 날 것 같았다. ⇒ 실제로 이 문제를 삼성 코테에서 풀어보신 스터디원 피셜께서는 시험장에서 입력과 출력이 달랐고 574418보다 훨씬 큰 출력도 있었다고,,, ArrayList로 풀었더니 시간초과였다고 하셨다!
• 그래서 나는 3차원 배열에 물고기의 수를 저장했다.
  • Origin 이라는 3차원 배열의 첫번째 인덱스는 세로, 두번째 인덱스는 가로, 세번째 인덱스는 방향을 뜻한다.

  static int[][][] origin = new int[4][4][8]; // 물고기 숫자
  

 

1. 물고기를 옮기고 다른 배열에 저장하기

• 왜 Origin 배열에서 옮기지 않고 다른 배열(temp)을 사용해야 하는가? ⇒ Origin 배열에서 바로 옮긴다면 옮긴 물고기랑 안옮긴 물고기랑 섞여서 안됨
• 방향을 반시계방향으로 돌리면서 갈 수 있는지 확인함 ⇒ dx, dy 배열을 이용해서 움직인다. ⇒ 1. 배열을 벗어나면 안되고 2. 냄새가 나면 안되고 3. 상어가 있으면 안됨 ⇒ 한 바퀴 돌아서 원래 내 방향이랑 똑같아지면 그냥 저장
• temp 배열의 가고자 하는 곳에, origin 배열의 원래 위치에 있던 숫자를 더한다.
• 그리고 그 위치에 있는 모든 숫자를 더한 값(모든 방향)도 이때 저장해 준다 fishNumMap. 뒤에서 배열을 합칠 때 수월하도록

2. 가장 많이 먹을 수 있는 방법 정하기

• eaten 이라는 배열에 가장 많이 먹을 수 있는 방법을 저장한다.
• 여기서 실수를 해서.. 엄청 헤맸다.!!! ⇒ 상 하 상 이런식으로도 갈 수 있다. 문제의 노트 부분에서 예시로도 적혀있었다. ⇒ 예를 들어서 상어가 1,1의 위치에 있고 물고기가 한마리도 없다면 상 하 상으로 움직이는 게 가장 우선순위가 높을 것이다
• 사전 순 정렬이 상,좌,하,우 였는데 이는 상어 방향 배열 edx, edy를 사전 순서대로 정해놓고 dfs든for문이든 돌리면 된다. 더 큰 수가 있을 때 업데이트 하도록 하면 됨.
• 나는 어쩌피 모든 경우를 확인해 봐야 하기 때문에 3중 for문을 사용했다.

3. 최적 경로로 가면서 먹은 곳을 삭제하기, 냄새를 남기기, 상어 옮기기

• eaten 배열을 따라가면서 먹은 곳의 배열은 초기화한다. findNumMap도 0으로 바꿔줌
• 냄새를 남기기 전에 원래 있던 냄새를 1씩 감소시킨다.
• 냄새를 남길 때는 남길 곳의 냄새를 2로 설정해 준다.
• eaten 배열에을 따라가면서 도착한 곳을 shark로 둔다.

4. 배열 두개를 합치기

• 배열 두개를 합치는 것은 temp 배열에 있는 값들을 다 origin 배열에 더해주면 된다.
• 물고기의 숫자(연습을 끝낸 후)는 numOfFish(원래 Origin에 있던 물고기 수) *2 에서 가장 많이 먹을 수 있는 방법으로 먹은 물고기수(Max)를 뺀 것이다.

 

코드

import java.io.IOException;
import java.io.InputStreamReader;
import java.text.FieldPosition;
import java.util.Arrays;
import java.util.StringTokenizer;

// origin 이라는 3차원 배열에 각 방향마다 물고기 몇마리있는지 저장해놓고 했습니다..
public class baekjoon_23290{
	static int M, S; // 물고기 수, 상어가 마법을 연습한 횟수
	static int[] dx = { 0, -1, -1, -1, 0, 1, 1, 1 }; // ←, ↖, ↑, ↗, →, ↘, ↓, ↙
	static int[] dy = { -1, -1, 0, 1, 1, 1, 0, -1 };

	static int[] edx = { -1, 0, 1, 0 }; // 상 좌 하 우
	static int[] edy = { 0, -1, 0, 1 };

	static Shark shark;
	static int[][][] origin = new int[4][4][8]; // 물고기 숫자
	static int[][] smell = new int[4][4]; // 냄새 저장하는 배열
	static int[][][] temp; // 이동한 물고기

	static int[] eaten;// 최대한 많이 먹을 수 있는 이동방향
	static boolean[][] visited; // eaten 구할 때 쓸 visited 배열
	static int Max; // 가장 많이 먹는 물고기 수

	static int numOfFish;
	static int[][] fishNumMap;

	public static void main(String[] args) throws IOException {
		// 입력 받는 부분
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		M = Integer.parseInt(st.nextToken());
		numOfFish = M;
		S = Integer.parseInt(st.nextToken());

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			int d = Integer.parseInt(st.nextToken()) - 1;
			origin[x][y][d]++;
		}

		// 초기의 상어 위치를 입력 받음
		st = new StringTokenizer(br.readLine());
		shark = new Shark(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1);

		for (int s = 0; s < S; s++) {
			// 1. 물고기를 옮기고 temp에 저장한다.
			moveFishes();

			// 2. 가장 많이 먹을 수 있는 방법을 정한다.
			eaten = new int[3];
			Max = -1;

			findEatdir();

			// 3. 먹은 곳 삭제하기, 냄새 남기기
			delete();

			// 4. 배열 두개를 합치기
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					if (fishNumMap[i][j] != 0) {
						for (int d = 0; d < 8; d++) {
							origin[i][j][d] += temp[i][j][d];
						}
					}
				}
			}
			numOfFish = numOfFish * 2 - Max;

		}
		System.out.println(numOfFish);
	}
	
	// 2. 가장 많이 먹을 수 있는 방법 정하기
	private static void findEatdir() {
		int x = shark.x;
		int y = shark.y;
		int sum = 0;
		for (int i = 0; i < 4; i++) {
			int nx1 = x + edx[i];
			int ny1 = y + edy[i];
			if (nx1 < 0 || nx1 >= 4 || ny1 < 0 || ny1 >= 4) {
				continue;
			}

			sum += fishNumMap[nx1][ny1];

			for (int j = 0; j < 4; j++) {
				int nx2 = nx1 + edx[j];
				int ny2 = ny1 + edy[j];
				if (nx2 < 0 || nx2 >= 4 || ny2 < 0 || ny2 >= 4) {
					continue;
				}
				sum += fishNumMap[nx2][ny2];
				for (int k = 0; k < 4; k++) {
					int nx3 = nx2 + edx[k];
					int ny3 = ny2 + edy[k];
					if (nx3 < 0 || nx3 >= 4 || ny3 < 0 || ny3 >= 4) {
						continue;
					}
					
					if(nx1!=nx3 || ny1!=ny3) {
						sum += fishNumMap[nx3][ny3];
					}
					
					// 최대값인지 비교하는 부분
					if(Max<sum) {
						Max = sum;
						eaten[0]= i;
						eaten[1]= j;
						eaten[2]= k;
					}
					
					
					if(nx1!=nx3 || ny1!=ny3) {
						sum -= fishNumMap[nx3][ny3];
					}
					
				}
				sum -= fishNumMap[nx2][ny2];
			}
			
			sum -= fishNumMap[nx1][ny1];
		}

	}

	private static void delete() {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (smell[i][j] != 0) {
					smell[i][j]--;
				}
			}
		}
		int nx = shark.x;
		int ny = shark.y;
		for (int i = 0; i < 3; i++) {
			int d = eaten[i];

			nx += edx[d];
			ny += edy[d];
			

			// 물고기가 있다면
			if (fishNumMap[nx][ny] != 0) {
				temp[nx][ny] = new int[8]; // 먹고
				fishNumMap[nx][ny] = 0;
				smell[nx][ny] = 2; // 냄새남김
			}
		}
		shark = new Shark(nx, ny); // shark 위치를 옮김
	}

	private static void moveFishes() {
		fishNumMap = new int[4][4];
		temp = new int[4][4][8];
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				for (int d = 0; d < 8; d++) {
					if (origin[i][j][d] == 0) { // 한마리도 없으면 continue
						continue;
					} else {
						int tempd = d;
						// 방향 정하기
						while (true) {
							int nx = i + dx[tempd];
							int ny = j + dy[tempd];

							// 갈 수 없으면
							if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4 || smell[nx][ny] != 0
									|| (shark.x == nx && shark.y == ny)) {
								tempd--;
								if (tempd == -1) {
									tempd = 7;
								}
								if (tempd == d) {
									temp[i][j][d] += origin[i][j][d];
									fishNumMap[i][j] += origin[i][j][d];
									break;
								}
								continue;
							}
							// 갈 수 있으면

							temp[nx][ny][tempd] += origin[i][j][d];
							fishNumMap[nx][ny] += origin[i][j][d];
							break;
						}
					}
				}
			}
		}

	}

	private static class Shark {
		int x;
		int y;

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

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

	}
}

 

출처: 백준

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

23290번: 마법사 상어와 복제