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

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

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

🤔 문제분석

아래의 3가지의 함수를 통하여 M번 반복하여 문제를 해결하였습니다.

• 그룸을 이동시키는 함수
• 그룸을 통하여 바구니에 저장된 물이 증가하는 함수
• 새로운 그룸을 생성하는 함수

그룸을 이동시키는 함수에서 중요한점은 N이 넘어가는 순간 0으로 바꾸어주고, -1로 넘어가는순간 N-1로 바꾸어주는 로직이 필요하다. 이부분은 문제에서 N번째 열과 0번째 열이 연결되어있고, N번째 행과 0번째 행이 연결되어있는 조건을 해결해준다.

💻 코드

파이썬

import sys
input = sys.stdin.readline

N, M = map(int ,input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

def change_range(y, x):
    if N > y >= 0 and N > x >=0:
        return y, x
    else:
        if y == N:
            y = 0
        
        if y == -1:
            y = N-1
            
        if x == N:
            x = 0
        
        if x == -1:
            x = N-1
            
        return y, x

def move_cloud(cloud, d, s): #구름, 방향, 거리
    moves = [(0, 0),(0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)]
    moved_cloud = set()
    for y, x in cloud:
        temp_y, temp_x = y, x
        for _ in range(s):
            dy, dx = moves[d][0], moves[d][1]
            ny, nx = dy + temp_y, dx + temp_x
            temp_y, temp_x = change_range(ny, nx)
        
        moved_cloud.add((temp_y, temp_x))
    
    return moved_cloud

def rain_and_copy_bug(cloud):
    moves = [(1, 1), (-1, -1), (1, -1), (-1, 1)]
    for y, x in cloud:
        graph[y][x] += 1
        
    for y, x in cloud:
        for dy, dx in moves:
            ny, nx = dy + y, dx + x
            if N > ny >=0 and N > nx >=0 and graph[ny][nx]:
                graph[y][x] += 1
    

def make_clude(cloud):
    new_cloud = set()
    for i in range(N):
        for j in range(N):
            if graph[i][j] >= 2:
                if (i, j) not in cloud:
                    graph[i][j] -= 2
                    new_cloud.add((i, j))
                
    return new_cloud

def sum_bucket():
    ans = 0
    for i in range(N):
        for j in range(N):
           ans += graph[i][j] 
    
    return ans
    
cloud = set([(N-1, 0), (N-1, 1), (N-2, 0), (N-2, 1)])
for _ in range(M):
    d, s = map(int, input().split())
    cloud = move_cloud(cloud, d, s)
    rain_and_copy_bug(cloud)
    cloud = make_clude(cloud)
    
print(sum_bucket())

자바

package Algorithm.백준;
import java.util.*;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class BOJ21610 {
    static int N;
    static int M;
    static int[][] table;
    public static void main(String[] argv) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        table = new int[N][N];
        List<Cloud> clouds = new ArrayList<>();

        clouds.add(new Cloud(N-1, 0));
        clouds.add(new Cloud(N-1, 1));
        clouds.add(new Cloud(N-2, 0));
        clouds.add(new Cloud(N-2, 1));

        for(int i = 0; i < N; i++)
        {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j ++)
            {
                table[i][j] = Integer.parseInt(st.nextToken());
            }
        }

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

        int ans = sumWater();
        StringBuilder result = new StringBuilder();
        result.append(ans);
        bw.write(result.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    public static class Cloud {
        public int x;
        public int y;

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

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            Cloud cloud = (Cloud) obj;
            return x == cloud.x && y == cloud.y;
        }
    
        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    public static boolean isRange(Cloud cloud)
    {
        return N > cloud.y && cloud.y >= 0 && N > cloud.x && cloud.x >= 0;
    }

    public static Cloud moveFix(Cloud cloud)
    {
        if (isRange(cloud)) {
            return cloud;
        }
        else{
            if(cloud.y == N) {
                cloud.y = 0;
            }

            if(cloud.y == -1) {
                cloud.y = N-1;
            }

            if(cloud.x == N) {
                cloud.x = 0;
            }

            if(cloud.x == -1) {
                cloud.x = N-1;
            }
            return cloud;
        }
    }

    public static List<Cloud> moveCloud(List<Cloud> clouds, int direction, int moveCnt)
    {
        int [][]moves = {{0, 0}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}};
        List<Cloud> newClouds = new ArrayList<>();

        for (Cloud cloud : clouds) {
            int tempY = cloud.y;
            int tempX = cloud.x;
            for(int i = 0; i < moveCnt; i ++) {
                int dy = moves[direction][0];
                int dx = moves[direction][1];
                var newCloud = moveFix(new Cloud(dy + tempY, dx + tempX));
                tempY = newCloud.y;
                tempX = newCloud.x;
            }
            newClouds.add(new Cloud(tempY, tempX));
        }
        return newClouds;
    }

    public static void rainAndCopy(List<Cloud> clouds)
    {
        int [][]moves = {{1, 1}, {-1, -1}, {-1, 1}, {1, -1}};

        for(var cloud : clouds)
        {
            table[cloud.y][cloud.x] += 1;
        }

        for(var cloud : clouds)
        {
            for (int i =0; i < 4; i ++)
            {
                int dy = moves[i][0];
                int dx = moves[i][1];
                if (isRange(new Cloud(dy+cloud.y, dx+cloud.x)) && table[dy+cloud.y][dx+cloud.x] >= 1)
                {
                    table[cloud.y][cloud.x] += 1;
                }
            }
        }
    }

    public static List<Cloud> makeClouds(List<Cloud> oldClouds)
    {
        List<Cloud> clouds = new ArrayList<>();
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if (table[i][j] >= 2) {
                    if(!oldClouds.contains(new Cloud(i, j)))
                    {
                        table[i][j] -= 2;
                        clouds.add(new Cloud(i, j));
                    }
                }
            }
        }
        return clouds;
    }

    public static int sumWater()
    {
        int ans = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j ++) {
                ans += table[i][j];
            }
        }
        return ans;
    }
}

🎯 피드백 및 개선사항

비가오는것과 대각선의 방향이 물웅덩이가 1이상인경우를 나누어서 풀었어야했는데 한번에 증가시키다보니 여기서 시간을 많이 잡아먹었습니다. 디버깅을 통하여 해당 이슈를 알게되었고… 문제를 해결했지만 해당 문제를 찾는데 15분 정도 시간을 날렸습니다. 😢