코테/백준

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

imname1am 2024. 3. 22. 23:59
반응형

📖 문제

 

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

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기

www.acmicpc.net

 

 

 

💡  풀이 방식

• 구현, 시뮬레이션

문제에 주어진 조건 그대로 구현하면 된다.

 

필요 자료구조
- 8방향 저장 dx/dy 배열
- 구름인 적 있었는지 나타내는 boolean형 방문 표시 배열
- 구름 위치 저장용 큐

 

 

 

💥 유의사항

1단계, 구름을 이동시키는 단계에서는 배열의 행과 열의 끝끼리 연결되어 있게 해야 한다.

이 때 인덱스에 유의해야 한다.

c[0] = (N + c[0] + dx[d] * (s % N)) % N;
c[1] = (N + c[1] + dy[d] * (s % N)) % N;

 

 

 

🔺 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0-1-1-10111};   // ←, ↖, ↑, ↗, →, ↘, ↓, ↙
    static int[] dy = {-1-101110-1};
    
    static int N,M;
    static int[][] A;   // 저장된 물의 양
    static boolean[][] visited;    // 구름인 적 있었는지 나타내는 방문 표시 
    static Queue<int[]> clouds = new ArrayDeque<>();    // 구름 위치 저장용 큐
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        A = new int[N][N];
        
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 초기 비구름 위치 저장
        clouds.add(new int[] {N-10});
        clouds.add(new int[] {N-11});
        clouds.add(new int[] {N-20});
        clouds.add(new int[] {N-21});
        
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int d = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            
            visited = new boolean[N][N];
            step12(d-1, s);
            step34();
            step5();
        }
        
        System.out.println(printSum());
    }
    
    private static void step12(int d, int s) {
        for(int[] c : clouds) {
            // 1. 구름 d방향으로 s칸 이동시키기 (💥 인덱스)
            c[0= (N + c[0+ dx[d] * (s % N)) % N;
            c[1= (N + c[1+ dy[d] * (s % N)) % N;
            visited[c[0]][c[1]] = true;
            
            // 2. 비 내리기
            A[c[0]][c[1]]++;
        }
    }
    
    private static void step34() {
        while(!clouds.isEmpty()) { 
            int[] now = clouds.poll();  // 3. 구름 없애기
            addWater(now[0], now[1]);   // 4. 물복사버그 마법
        }
    }
    
    // 대각선 물 갯수 세는 메서드
    private static void addWater(int x, int y) {
        for(int i = 1 ; i <= 7 ; i += 2) {  // 1, 3, 5, 7
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(inRange(nx, ny) && A[nx][ny] > 0)
                A[x][y]++;
        }
    }
    
    private static void step5() {
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                if(A[i][j] >= 2 && !visited[i][j]) {
                    clouds.add(new int[] {i, j});
                    A[i][j] -= 2;
                }
            }
        }
    }
    
    private static int printSum() {
        int sum = 0;
        
        for(int[] i : A) {
            for(int j : i)
                sum += j;
        }
        
        return sum;
    }
    
    private static boolean inRange(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < N;
    }
}
 
cs

 

 

➕ 다른 풀이 방식

구름 위치를 리스트 인터페이스에 넣지 않으시고, boolean형 배열에 표시하시면서 직접 매번 완탐으로 구름 위치 찾도록 하셨다.

 

백준 21610 마법사 상어와 비바라기(Java)

문제 출처 : https://www.acmicpc.net/problem/21610 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남

jyunslog.tistory.com

 

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

[문제] https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바

geumba.tistory.com


💦 어려웠던 점

- 인덱스 처리 부분이 헷갈림,,,,,,,,,, s % N 갑자기 뭐지 했는데 이제 이해함!!

 

 

 

1회독 2회독 3회독 4회독 5회독
V        

(참고)

 

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

[백준 Baekjoon] 21610번 마법사 상어와 비바라기 - JAVA 문제 풀이 문제에서 주어진 격자는 (1, 1)부터 (N, N)의 크기이지만, 저는 (0, 0)부터 (N-1, N-1)의 크기로 만들어 사용하였습니다. 방향 이동 또한 1부

dlee0129.tistory.com

 

[백준] 21610번 마법사 상어와 비바라기 - Java, 자바

골드 5https://www.acmicpc.net/problem/21610주어진 조건을 차례대로 잘 구현하면 되는 문제. 이 문제에서 어려웠던 점은 구름을 di 방향으로 si 칸 이동하는 부분 로직을 짜는 것이었는데, 이 부분 유의하

velog.io

반응형