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

1. 소요시간 : 1시간
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 4
4. 문제 유형 : 구현, 시뮬레이션
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 문제 링크 : https://www.acmicpc.net/problem/21610
7. 푼 날짜 : 2023.05.06

1. 사용한 자료구조 & 알고리즘

구현 + 시뮬레이션

2. 풀이과정

문제에 있는 그대로를 구현한다.
주의할 점은 구름이 4개라면, 구름이 완전히 이동하고, 4개의 구름이 다 사라진 후에 대각선에 있는 바구니의 물을 보고 1 이상이면 count를 증가시켜야 한다.
1개의 구름이 이동하고, 대각선 체크,
1개의 구름이 이동하고, 대각선 체크 .. 이렇게 구현하면 틀린 답이 나온다.
이 문제를 20분 동안 찾아 헤맸다.

1. queue를 이용해서 구름이 해당 방향으로 s 칸이동
2. 구름이 있는 칸 물 1 증가.
3. 모든 구름이 2번 작업을 수행한다면, 이제 대각선을 보고 물이 1 이상 있다면 해당 좌표의 물을 1증가. ( 구름이 사라진 자리에서만 수행하므로, 2번 작업이 끝난 좌표의 위치는 queue에 담아두어야 한다.)
4. 물이 2 이상인 모든 좌표를 구름에 추가하고, 물을 2 줄인다.
5. 1번으로 돌아간다.

3. 소스코드

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


public class Main{
	static int dy[]= { 0,-1,-1,-1,0,1,1,1};
	static int dx[]= {-1,-1,0,1,1,1,0,-1};
	static int map[][];
	static Queue <Integer[]> cloud = new LinkedList<>();

	public static void main(String[] args) throws IOException{

		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;


		st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		map=new int[N][N];
		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());
			}
		}
		cloud.add(new Integer[] {N-1,0});
		cloud.add(new Integer[] {N-1,1});
		cloud.add(new Integer[] {N-2,0});
		cloud.add(new Integer[] {N-2,1});


		for(int i=0;i<M;i++) {
			st=new StringTokenizer(br.readLine());
			int d = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			moveCloud(d-1,s);
		
		}



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

		System.out.println(sum);


	}
	public static void moveCloud(int d,int s) {


		int yy[] = {-1,-1,1,1};
		int xx[] = {-1,1,-1,1};
		boolean visited[][]=new boolean[map.length][map.length];
		Queue<Integer[]> plus = new LinkedList<>();

		while(!cloud.isEmpty()) {
			Integer temp[] = cloud.poll();
			int nowY = temp[0];
			int nowX = temp[1];

			nowY += (s*dy[d]);
			nowX += (s*dx[d]);

			nowY %= map.length;
			nowX %= map.length;

			if(nowY<0) {
				nowY = Math.abs(nowY);
				nowY = map.length - nowY;
			}
			if(nowX<0) {
				nowX = Math.abs(nowX);
				nowX = map.length -nowX;
			}

			map[nowY][nowX] ++;
			visited[nowY][nowX] = true;
			plus.add(new Integer[] {nowY,nowX});





		}

		while(!plus.isEmpty()) {
			Integer temp [] =plus.poll();
			int nowY=temp[0];
			int nowX =temp[1];
			for(int k=0;k<4;k++) {
				int nextY = nowY+yy[k];
				int nextX = nowX+xx[k];
				if(nextY<0||nextX<0||nextY>=map.length||nextX>=map.length)
					continue;
				if(map[nextY][nextX]>0)
					map[nowY][nowX] ++;

			}
			
		}


		for(int i=0;i<map.length;i++) {
			for(int j=0;j<map.length;j++) {
				if(!visited[i][j]&&map[i][j]>1) {
					cloud.add(new Integer[] {i,j});
					map[i][j]-=2;	
				}
			}
		}



	}


}

4. 결과

5. 회고

예전에 프로그래밍 교수님께서
프로그래밍을 잘하는 것은 코드로 빠르게 주어진 문제에서 설계하고 푸는 것보다는
오류가 발생했을 때 그 오류를 빨리 찾는 사람이 잘하는 거라고 하셨는데
요즘에 그 말이 실감이 난다. 제대로 작동하지 않았을 때 디버깅 하는 게 만만치 않다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212