[자바] 백준 21610 - 마법사 상어와 비바라기 (java)

목차

문제 : boj21610

 

 

필요 알고리즘

• 시뮬레이션
  
  • 제시된 대로 구현하면 된다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  그냥 문제에 제시된대로 구현하면 되서 풀이는 필요없을 것 같다. 이하 코드는 그냥 풀긴 좀 심심할 것 같아서 2차원 배열을 쓰지 않고 풀어봤다. 그러니 2차원 배열 안쓰고 푸는걸 참고하려면 코드를 확인해보자. 각 단계별로 처리하는 코드는 주석을 달아두었다. 2차원 배열로 문제에 제시된대로 구현하는게 더 편하다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);
    public static void main(String[] args) throws Exception {new Main().solution();}

    static final int[] DR = {0, -1, -1, -1, 0, 1, 1, 1};
    static final int[] DC = {-1, -1, 0, 1, 1, 1, 0, -1};
    int n;
    int[] arr;
    List<Integer> candidates;

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        arr = new int[n*n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i*n+j] = Integer.parseInt(st.nextToken());
            }
        }

        candidates = new ArrayList<>();
        for (int i = 1; i <= 2; i++)
            for (int j = 0; j <= 1; j++)
                candidates.add((n-i)*n+j);

        while (m-->0) {
            st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            proc(d-1, s);
        }

        System.out.println(Arrays.stream(arr).sum());
    }

    private void proc(int d, int s) {
        LinkedHashSet<Integer> tmp = new LinkedHashSet<>();
        for (int cur : candidates) {
            // step 1
            int r = (cur/n + DR[d]*s + n*s)%n;
            int c = (cur%n + DC[d]*s + n*s)%n;

            // step 2
            arr[r*n+c]++;
            tmp.add(r*n+c);
        }

        // step 3 : do nothing

        for (int cur : tmp) {
            int r = cur/n;
            int c = cur%n;

            // step 4
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    if (i==0||j==0) continue;

                    int nr = r+i;
                    int nc = c+j;
                    if (nr<0||nr>=n||nc<0||nc>=n) continue;

                    arr[r*n+c] += arr[nr*n+nc]>0?1:0;
                }
            }
        }

        // step 5
        List<Integer> nextCandidates = new ArrayList<>();
        for (int i = 0; i < n*n; i++) {
            if (tmp.contains(i) || arr[i]<2) continue;

            arr[i]-=2;
            nextCandidates.add(i);
        }

        candidates = nextCandidates;
    }
}