[백준 - 21610][Gold 5] - 마법사 상어와 비바라기 (JAVA)

728x90

문제 링크

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

문제

N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 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부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.

모든 구름이 di 방향으로 si칸 이동한다.
각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 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 ≤ di ≤ 8
1 ≤ si ≤ 50

출력

첫째 줄에 M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 출력한다.

구현으로 풀릴까??

우선 가장 쉬운 방법인 구현을 생각해보자.

문제에서 요구하는 행동을 다시 보면 다음과 같다.

모든 구름이 di 방향으로 si칸 이동한다.
각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 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에서 구름이 사라진 칸이 아니어야 한다.

위의 행동을 간단한 코드로 표현하면 다음과 같다.

for(K번){
모든 구름

for(모든 구름){
다음 구름 위치 = di방향으로 si칸 이동
다음 위치에서 비 내리기
구름 사라짐 표시
비내린 구름 집합.add(다음 구름)
}

for(비내린 구름){
for(대각 방향){
if(다음위치가 대각방향이 아닌경우){
continue;
}

if(비내린 구름이 사라질 위치인 경우){
continue;
}
비내린 구름 위치에 비 한번 더 내리기
}
}

다음 비 내릴 구름집합

for(행){
for(열){
if(현대 위치의 물이 2 이상이 경우){
다음 비 내릴 구름집합.add(현재 위치)
}
}
}

모든 구름 = 다음 비 내릴 구름집합
}

조건이 많기 때문이 좀 복잡해 보이지만 이를 이용해 시간복잡도를 계산하면 다음과 같다.

O(n) = (구름 이동 횟수)*((비내리기) + (물복사버그) + (다음 구름 생성))
= M * (N^2 + N^2 + N^2 )
≒ M * N^2

이때 M은 최대 100이며 N은 최대 50이다. 그러므로 최대 연산 횟수는 100*50^2 = 250,000 이므로 시간제한 1초의 예상 연상 시간인 1억보다 훨신 작으므로 구현으로 해결할 수 있다!

1행 -> N행 -> 1행을 편하게 구현할 방법은 없을까?

이 문제는 8방향 이동 문제이다. 이때 배열 밖으로 넘어가는 경우 1행(열)이 N행(열)과 연결되어 있으므로 순환 구조를 가지고 있다. 이동을 1번씩 이동하여 1행에서 밖으로 넘어갔을때 N행으로, N행에서 밖으로 넘어갔을 때 1행으로 가도록 로직을 만들면 다음과 같다.

for(모든 구름){
        for(s){
            다음 구름 위치 = di방향으로 1칸 이동
            
            if(다음 구름.row < 1 ){	
		다음 구름.row = N
            }else if(다음 구름.row > N){
		다음 구름.row = 1
            }
            
             if(다음 구름.col < 1 ){	
		다음 구름.col = N 
            }else if(다음 구름.col > N){
		다음 구름.col = 1
            }
        }
    }

위의 방식대로 1칸씩 이동하여 다음 좌표로 이동하도록 로직을 만들면 si는 최대 50이기 때문에 시간복잡도는 M*N^2이 아니라 M*N^2*S = 100 * 50^2 * 50 = 12,500,000이 된다. 물론 제한시간인 1초의 연산횟수인 1억보다 작기 때문에 가능하겠지만 1칸씩 움직이는 것이아니라 한번에 움직이는 방법을 도입하면 O(S)의 연산 횟수가 O(1)로 줄기 때문에 더 빠른 구현이 가능하다!

이 문제는 순환 구조를 따르기 때문에 1,2,3...N,1,2,3,...N을 반복한다. 이때 1행부터 시작하는 것을 0행으로 시작하는 것으로 바꾸면 0,1,2 ... N-1, 0,1,2, ... , N-1의 반복 구조로 바뀌게 되는데 이는 N의 나머지 수열과 같다! 그러므로 해당방향 + si를 더해주고 N을 나누면 목표 좌표가 나오게 된다. 이를 반영한 코드는 다음과 같다.

for(모든 구름){
	다음 구름 위치 = (현재 구름 위치 + di방향으로 S칸 이동) % N
	}
}

하지만 변수가 하나 있는데 바로 이동벡터가 음수인 경우이다. 예를 들어 왼쪽 대각선 위로 가려고 하면 행과 열의 이동벡터는 각각 -1이다. 그러므로 -1*S 만큼 움직이게 되는데 이러면 0, N-1,N-2 .. 0, N-1의 수열이 아니라 0, -1, -2, ... -(N-1) , 0이 되어버리므로 원하는 위치가 나오지 않게 된다.

이를 해결하기 위해 음수를 양수로 바꿀 필요가 있으므로 N을 양수가 나올 만큼 더해주어 음수를 양수로 변환해준다. 이때 Si는 최대 50이므로 50*N을 해주어도 되지만 필요한 만큼만 양수를 만들어주고 싶어 N*S를 더해주어 음수가 나오지 않도록 하였다. 이를 반영한 코드는 다음과 같다.

for(모든 구름){
	다음 구름 위치 = (현재 구름 위치 + di방향으로 S칸 이동 + S*N) % N
	}
}

문제 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

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

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");

		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);

		long[][] map = new long[N][N];

		for(int i=0;i<N;i++){
			map[i] = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
		}

		Queue<Coordinate> cloudQ = new LinkedList<>();

		//시작 구름 넣기
		cloudQ.add(new Coordinate(N-1,0));
		cloudQ.add(new Coordinate(N-1,1));
		cloudQ.add(new Coordinate(N-2,0));
		cloudQ.add(new Coordinate(N-2,1));

		for(int round=0;round<M;round++){
			input = br.readLine().split(" ");
			int direction = Integer.parseInt(input[0]) - 1;
			int speed = Integer.parseInt(input[1]);
			boolean[][] visited = new boolean[N][N];
			
            //구름 움직이고 비내림
			cloudQ = rain(cloudQ,direction,speed,visited,map);
			
            //물복사 버그실행
            waterCopyBug(cloudQ,map);
            
            //구름 생성
			cloudQ = makeCloud(visited,map);
		}

		long waterSum = getSum(map);

		System.out.println(waterSum);
	}
    
    //구름을 움직이고 비를 내리는 메소드
	public static Queue<Coordinate> rain(Queue<Coordinate> q, int direction, int speed,boolean[][] visited, long[][]map){
		Queue<Coordinate> movedCloudQ = new LinkedList<>();

		while(!q.isEmpty()){
			Coordinate cloud = q.poll();

			int nextRow = (cloud.row + dx[direction]*speed + speed*N) % N;
			int nextCol = (cloud.col + dy[direction]*speed + speed*N) % N;

			Coordinate next = new Coordinate(nextRow,nextCol);
			//방문처리
			visited[next.row][next.col] = true;
			//비내리기
			map[next.row][next.col]++;

			movedCloudQ.add(next);
		}

		return movedCloudQ;
	}
    
    //물복사버그를 실행해 대각 위치의 물이 있는 영역만큼 비를 추가로 내리는 메소드
	public static void waterCopyBug(Queue<Coordinate> cloudQ,long[][]map){
		while(!cloudQ.isEmpty()){
			Coordinate cloud = cloudQ.poll();

			//대각 이동 벡터
			int[] diagDX = {-1,-1,1,1};
			int[] diagDy = {-1,1,-1,1};

			//물복사버그 시전
			for(int i=0;i<diagDX.length;i++){
				Coordinate next = new Coordinate(cloud.row+diagDX[i],cloud.col+diagDy[i]);

				//맵 밖으로 넘어가는 경우
				if(next.row < 0 || next.col <0 || next.row >= N || next.col >= N){
					continue;
				}
				//믈이 없는 바구니인 경우
				if(map[next.row][next.col] ==0){
					continue;
				}

				map[cloud.row][cloud.col]++;
			}
		}
	}
    
    //비구름을 만드는 메소드
	public static Queue<Coordinate> makeCloud(boolean[][] visited,long[][]map){
		Queue<Coordinate> cloudQ = new LinkedList<>();

		for(int row=0;row<map.length;row++){
			for(int col=0;col<map[row].length;col++){
                //지금 사라질 구름의 위치면 패스 
				if(visited[row][col]){
					continue;
				}
                //물의 양이 부족하면 패스
                else if(map[row][col] < 2){
					continue;
				}

				cloudQ.add(new Coordinate(row,col));
				map[row][col] -= 2;
			}
		}

		return cloudQ;
	}
    
    //모든 물의 합을 구하는 메소드
	public static long getSum(long[][]map){
		long sum =0;

		for(int row=0;row<map.length;row++){
			for(int col=0;col<map[row].length;col++){
				sum += map[row][col];
			}
		}

		return sum;
	}
}

class Coordinate{
	int row;
	int col;

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

실행 결과

제한시간인 2초 안에 문제가 해결되었다!

키워드

N이 충분히 작음(N = 50)
- 구현의 가능성을 가지고 있다.

팁

조건이 많고 N이 작으면 구현부터 해보자
조건이 많으면 순차적으로 메소드를 만들고 각 메소드가 잘 실행되는지 개별적으로 확인하자

'알고리즘 문제 풀이 > 해설' 카테고리의 다른 글

[백준 - 21758][Gold 5] - 꿀 따기 (JAVA) (1)	2024.02.28
[백준 - 2331][Silver 4] - 반복수열 (JAVA) (0)	2024.02.17
[백준 - 2138][Gold 5] - 전구와 스위치 (JAVA) (0)	2024.02.15
[백준 - 15486][Gold 5] - 퇴사 2 (JAVA) (0)	2024.02.12
[백준 - 1092][Gold 5] - 배 (JAVA) (1)	2024.02.09