Problem

• 문제 링크

주어진 맵을 5 개의 구역으로 나눕니다.

각 구역의 인구의 합을 구한 뒤 가장 큰 값과 가장 작은 값의 차를 구합니다.

구역을 나눌 수 있는 모든 경우에서 최대값과 최소값의 차를 구한 뒤 이 중에서 가장 작은 수를 구하는 문제입니다.

Solution

대각선으로 나누어지기도 하고 좌표값이 복잡해보이긴 하지만 문제에서 주어진 대로 구현만 하면 쉽게 풀리는 문제입니다.

1. 4 중 for 문으로 (x, y, d1, d2) 경우의 수를 전부 구한다.
2. (x, y) 좌표에서 시작하여 d1, d2 를 기준으로 경계선만 체크한다.
3. 경계선을 기준으로 1, 2, 3, 4 구역의 인구수를 구한다.
4. 5 구역은 (전체 인구수 - 나머지 구역의 인구수) 로 계산한다.
5. 각 구역 인구수를 오름차순으로 정렬한 뒤에 최대값에서 최소값을 빼고 min 배열과 비교해서 최소값을 구한다.

각 구역의 인구수를 구하는 순서는 아래 그림처럼 위에서부터 아래로, 화살표 순서대로 값을 더했습니다.

미리 표시해둔 경계선을 만나면 다음 줄로 넘어가는 방식으로 구현하여 5 구역을 전부 알아낼 필요 없이 경계선만 체크했습니다.

Java Code

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

class Main {
    static int N;
    static int[][] arr;
    static int totalPeople = 0;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // input
        st = new StringTokenizer(br.readLine());
        N = 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][j] = Integer.parseInt(st.nextToken());
                totalPeople += arr[i][j];
            }
        }

        // solution
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                for (int d1 = 1; d1 < N; d1++) {
                    for (int d2 = 1; d2 < N; d2++) {
                        if (x + d1 + d2 >= N) continue;
                        if (y - d1 < 0 || y + d2 >= N) continue;

                        solution(x, y, d1, d2);
                    }
                }
            }
        }

        System.out.println(min);
    }

    static void solution(int x, int y, int d1, int d2) {
        boolean[][] border = new boolean[N][N];

        // 경계선 세팅
        for (int i = 0; i <= d1; i++) {
            border[x + i][y - i] = true;
            border[x + d2 + i][y + d2 - i] = true;
        }

        for (int i = 0; i <= d2; i++) {
            border[x + i][y + i] = true;
            border[x + d1 + i][y - d1 + i] = true;
        }

        int[] peopleSum = new int[5];

        // 1 구역 인구수
        for (int i = 0; i < x + d1; i++) {
            for (int j = 0; j <= y; j++) {
                if (border[i][j]) break;
                peopleSum[0] += arr[i][j];
            }
        }

        // 2 구역 인구수
        for (int i = 0; i <= x + d2; i++) {
            for (int j = N - 1; j > y; j--) {
                if (border[i][j]) break;
                peopleSum[1] += arr[i][j];
            }
        }

        // 3 구역 인구수
        for (int i = x + d1; i < N; i++) {
            for (int j = 0; j < y - d1 + d2; j++) {
                if (border[i][j]) break;
                peopleSum[2] += arr[i][j];
            }
        }

        // 4 구역 인구수
        for (int i = x + d2 + 1; i < N; i++) {
            for (int j = N - 1; j >= y - d1 + d2; j--) {
                if (border[i][j]) break;
                peopleSum[3] += arr[i][j];
            }
        }

        // 5 구역 인구수
        peopleSum[4] = totalPeople;

        for (int i = 0; i < 4; i++) {
            peopleSum[4] -= peopleSum[i];
        }

        // 정렬
        Arrays.sort(peopleSum);

        // 최대 - 최소
        min = Math.min(min, peopleSum[4] - peopleSum[0]);
    }
}

Problem

• 문제 링크

연구소에는 벽과 비활성화된 바이러스가 있습니다.

10 개 이하의 비활성화 바이러스 중 M 개를 선택해서 활성화 시키려고 합니다.

활성화된 바이러스는 1 초에 인접한 상하좌우로 이동할 수 있으며 벽은 지나갈 수 없습니다.

M 개를 활성화시키는 모든 경우 중에서 바이러스가 연구소에 전부 퍼지는 최단시간을 구하는 문제입니다.

Solution

활성화된 바이러스를 택하는 모든 경우의 수는 백트래킹으로 구합니다.

Input 을 받을 때 바이러스들의 모든 리스트를 List<Virus> viruses 에 받아서 저장해둡니다.

재귀를 통해서 활성화 시킬 바이러스 리스트인 Virus[] active 를 구하고 나면 바이러스틀 퍼트립니다.

바이러스 퍼트리기는 BFS 로 진행하면 됩니다.

BFS 를 진행하면서 방문 체크가 필요한대, 기존 2차원 배열은 계속해서 사용해야되기 때문에 다른 배열을 복사하거나 생성해서 사용해야 합니다.

boolean[][] infected 배열을 통해 확산 여부를 체크하고 기존 배열로는 벽을 체크하면서 진행합니다.

처음 입력을 받을 때 미리 구해둔 emptySpace 를 사용해서 빈 공간의 갯수가 0 이 되는 순간의 시간초를 구하고 그 중 가장 작은 숫자를 구하면 됩니다.

주의할 점

1. 활성화된 바이러스가 퍼질 때 비활성화된 바이러스도 지나갈 수 있다.

2. 벽에 막혀서 바이러스가 존재하지 못하는 경우라고 반드시 -1 은 아니다. 다른 바이러스를 활성화 하면 성공할 수도 있다. 모든 바이러스의 경우를 만들었을때 전부 실패해야 -1 이다.

3. 바이러스를 퍼트릴 맵은 따로 복사해서 사용하는게 좋다.

4. 비활성화된 바이러스는 지나갈 수 있지만 도착하는 순간에 시간을 갱신하면 안된다. 비활성화된 바이러스들 때문에 바이러스가 전부 퍼졌는지 확인하는 건 빈 공간의 갯수로 파악하는 것이 훨씬 효과적이다.

Java Code

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

class Main {
    static class Virus {
        int x, y, time;

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

    static int N, M;
    static int[][] arr;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static List<Virus> viruses = new ArrayList<>();
    static Virus[] active;
    static int resultMinTime = Integer.MAX_VALUE;
    static int originEmptySpace = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // input
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        arr = new int[N][N];
        active = new Virus[M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());

                if (arr[i][j] == 0) {
                    originEmptySpace++;
                } else if (arr[i][j] == 2) {
                    viruses.add(new Virus(i, j, 0));
                }
            }
        }

        // solution
        if (originEmptySpace == 0) {
            System.out.println(0);
        } else {
            selectVirus(0, 0);
            System.out.println(resultMinTime == Integer.MAX_VALUE ? -1 : resultMinTime);
        }
    }

    // 백트래킹으로 M 개의 바이러스를 선택하는 Combination 구현
    static void selectVirus(int start, int selectCount) {
        if (selectCount == M) {
            spreadVirus(originEmptySpace);
            return;
        }

        for (int i = start; i < viruses.size(); i++) {
            active[selectCount] = viruses.get(i);
            selectVirus(i + 1, selectCount + 1);
        }
    }

    // BFS 로 바이러스를 퍼트린다
    static void spreadVirus(int emptySpace) {
        Queue<Virus> q = new LinkedList<>();
        boolean[][] infected = new boolean[N][N];

        for (int i = 0; i < M; i++) {
            Virus virus = active[i];
            infected[virus.x][virus.y] = true;
            q.add(virus);
        }

        while (!q.isEmpty()) {
            Virus virus = q.poll();

            for (int i = 0; i < 4; i++) {
                int nx = virus.x + dx[i];
                int ny = virus.y + dy[i];

                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                if (infected[nx][ny] || arr[nx][ny] == 1) continue;

                if (arr[nx][ny] == 0) {
                    emptySpace--;
                }

                if (emptySpace == 0) {
                    resultMinTime = Math.min(resultMinTime, virus.time + 1);
                    return;
                }

                infected[nx][ny] = true;
                q.add(new Virus(nx, ny, virus.time + 1));
            }
        }
    }
}

Problem

• 문제 링크

문제에서 설명해주는 R 연산과 C 연산을 반복한 뒤 특정 좌표의 숫자가 k 와 일치하는 시간은 몇 초 뒤인지 구하는 문제입니다.

Solution

단순하게 구현하면 됩니다.

R 연산과 C 연산의 인덱스 빼고는 거의 동일한데 저는 헷갈릴까봐 그냥 각각 정의했습니다.

인덱스에 대한 처리만 주의하면 되는 문제입니다.

특정 행이나 열에 대한 연산은 다음 순서로 진행했습니다.

1. 숫자들의 갯수를 카운팅해서 Map<number, count> 에 저장합니다.
2. 우선순위를 적용한 Pair 클래스에 넣어서 우선순위 큐에 넣어줍니다.
3. 우선순위 큐에서 순서대로 값들을 꺼내 배열을 다시 갱신해주고 해당되지 않는 배열들은 전부 0 으로 초기화해줍니다.

주의할 점

1. R 연산, C 연산 인덱스 헷갈리지 않기

2. 100 초가 넘어가는 순간이기 때문에 100 초에 성공한 값도 인정

3. 연산할 때 0 의 갯수는 세지 않는 예외처리 필요

4. A 배열에 그대로 새 값을 덮어쓴다면 연산에 해당하지 않는 값은 0 으로 세팅 해줘야한다.

   • 연산을 한다고 길이가 무조건 길어지지는 않다.
   • [1, 1, 1, 1, 1] 을 연산하면 [1, 5] 가 되는데 만약 뒤의 값들을 0 으로 바꾸지 않으면 [1, 5, 1, 1, 1] 로 남는다.

Java Code

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

class Main {
    static class Pair implements Comparable<Pair> {
        int number;
        int count;

        Pair(int n, int c) {
            this.number = n;
            this.count = c;
        }

        // count 가 작은 게 앞으로, 같으면 number 가 작은게 앞으로
        public int compareTo(Pair o) {
            if (this.count > o.count) {
                return 1;
            } else if (this.count == o.count) {
                return this.number - o.number;
            } else {
                return -1;
            }
        }
    }

    static int r, c, k;
    static int[][] A = new int[101][101];
    static int xLength = 3, yLength = 3;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // input
        st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= 3; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 1 ; j <= 3; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // solution
        System.out.println(solution());
    }

    static int solution() {
        for (int time = 0; time <= 100; time++) {
            if (A[r][c] == k) {
                return time;
            }
            operating();
        }

        return -1;
    }

    // R 연산 : 배열 A의 모든 행에 대해서 정렬을 수행한다
    // C 연산 : 배열 A의 모든 열에 대해서 정렬을 수행한다
    static void operating() {
        if (xLength >= yLength) {
            for (int i = 1; i <= xLength; i++) {
                R(i);
            }
        } else {
            for (int i = 1; i <= yLength; i++) {
                C(i);
            }
        }
    }

    // 각 숫자들의 개수를 구해서 HashMap 에 담았다가 우선순위 큐에 옮겨담아서 정렬
    static void R(int key) {
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        Map<Integer, Integer> map = new HashMap<>(); // <number, count>

        for (int i = 1; i <= yLength; i++) {
            if (A[key][i] == 0) continue;
            map.compute(A[key][i], (num, count) -> count == null ? 1 : count + 1);
        }

        map.forEach((k, v) -> pq.add(new Pair(k, v)));

        int i = 1;
        while (!pq.isEmpty()) {
            Pair p = pq.poll();
            A[key][i++] = p.number;
            A[key][i++] = p.count;
        }

        yLength = Math.max(yLength, i);

        while (i <= 99) {
            A[key][i++] = 0; 
            A[key][i++] = 0; 
        }
    }
    
    // 각 숫자들의 개수를 구해서 HashMap 에 담았다가 우선순위 큐에 옮겨담아서 정렬
    static void C(int key) {
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        Map<Integer, Integer> map = new HashMap<>(); // <number, count>

        for (int i = 1; i <= xLength; i++) {
            if (A[i][key] == 0) continue;
            map.compute(A[i][key], (num, count) -> count == null ? 1 : count + 1);
        }

        map.forEach((k, v) -> pq.add(new Pair(k, v)));

        int i = 1;
        while (!pq.isEmpty()) {
            Pair p = pq.poll();
            A[i++][key] = p.number;
            A[i++][key] = p.count;
        }

        xLength = Math.max(xLength, i);

        while (i <= 99) {
            A[i++][key] = 0; 
            A[i++][key] = 0; 
        }
    }
}

Problem

• 문제 링크

매 초마다 움직이는 물고기들과 물고기를 잡아먹으며 이동하는 상어가 존재할 때

상어가 잡아 먹을 수 있는 물고기 크기의 합을 구하는 문제입니다.

Solution

백트래킹을 이용해서 상어가 이동하는 모든 경우의 수를 구하면 됩니다.

상어는 한 방향밖에 가지 못하기 때문에 4 x 4 배열에서 이동하는 경우의 수는 최대 3 개입니다.

물고기가 먼저 이동해야 하기 때문에 DFS 시작하자마자 물고기를 전부 이동시키고 이동 가능한 경우의 수를 전부 확인하여 다시 DFS 를 들어갑니다.

원래 백트래킹을 할 때는 빠져 나오면서 값들을 원래 값으로 돌려놓아야 하는데

배열이나 물고기 리스트들이 너무 바뀌는게 많기 때문에 다음 DFS 로 넘기는 값들은 전부 복사한 새로운 값으로 했습니다.

그래서 DFS 를 빠져나온 후에도 기존 값들을 갖고 다음 경우의 수를 확인할 수 있습니다.

주의할 점

1. 물고기들은 번호 순서대로 이동해야 합니다. 물고기가 순서대로 주어지지 않기 때문에 정렬이 필요합니다.
2. 상어는 물고기가 있는 공간으로만 이동할 수 있습니다.
3. 물고기는 빈칸 또는 또다른 물고기가 있는 곳으로만 이동할 수 있습니다.
4. 상어나 물고기가 이동한 후에는 이동하기 전의 공간 뒷처리를 잘 해줘야합니다.

Java Code

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

class Main {
    static class Shark {
        int x, y, dir, eatSum;

        Shark() { }

        Shark(int x, int y, int dir, int eatSum) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.eatSum = eatSum;
        }
    }

    static class Fish {
        int x, y, id, dir;
        boolean isAlive = true;

        Fish() { }
        
        Fish(int x, int y, int id, int dir, boolean isAlive) {
            this.x = x;
            this.y = y;
            this.id = id;
            this.dir = dir;
            this.isAlive = isAlive;
        }
    }
    
    // 0 부터 7 까지 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};
    static int maxSum = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int[][] arr = new int[4][4];
        List<Fish> fishes = new ArrayList<>();

        // input
        for (int i = 0; i < 4; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < 4; j++) {
                Fish f = new Fish();
                f.id = Integer.parseInt(st.nextToken());
                f.dir = Integer.parseInt(st.nextToken()) - 1;
                f.x = i;
                f.y = j;
                
                fishes.add(f);
                arr[i][j] = f.id;
            }
        }

        // 물고기는 작은 순서부터 이동해야 하기 때문에 미리 정렬해둠
        Collections.sort(fishes, new Comparator<Fish>() {
            @Override
            public int compare(Fish o1, Fish o2) {
                return o1.id - o2.id;
            }
        });

        // 상어는 (0, 0) 물고기를 먹고 시작하며 위치는 -1 로 표현
        Fish f = fishes.get(arr[0][0] - 1);
        Shark shark = new Shark(0, 0, f.dir, f.id);
        f.isAlive = false;
        arr[0][0] = -1;
        
        // solution
        dfs(arr, shark, fishes);
        System.out.println(maxSum);
    }

    // 재귀로 상어가 이동할 수 없을 때까지 반복한다.
    static void dfs(int[][] arr, Shark shark, List<Fish> fishes) {
        // 잡아먹은 양의 최대값 구하기
        if (maxSum < shark.eatSum) {
            maxSum = shark.eatSum;
        }

        // 모든 물고기 순서대로 이동
        fishes.forEach(e -> moveFish(e, arr, fishes));
        
        for (int dist = 1; dist < 4; dist++) {
            int nx = shark.x + dx[shark.dir] * dist;
            int ny = shark.y + dy[shark.dir] * dist;
    
            if (0 <= nx && nx < 4 && 0 <= ny && ny < 4 && arr[nx][ny] > 0) {
                // 물고기 잡아먹고 dfs
                int[][] arrCopies = copyArr(arr);
                List<Fish> fishCopies = copyFishes(fishes);
                
                arrCopies[shark.x][shark.y] = 0;
                Fish f = fishCopies.get(arr[nx][ny] - 1);
                Shark newShark = new Shark(f.x, f.y, f.dir, shark.eatSum + f.id);
                f.isAlive = false;
                arrCopies[f.x][f.y] = -1;
                
                dfs(arrCopies, newShark, fishCopies);
            }
        }
    }
    
    // 이동가능한 칸은 빈칸, 다른 물고기가 있는 칸
    // 45도 반시계 방향으로 회전하면서 스캔
    static void moveFish(Fish fish, int[][] arr, List<Fish> fishes) {
        if (fish.isAlive == false) return;

        for (int i = 0; i < 8; i++) {
            int nextDir = (fish.dir + i) % 8;
            int nx = fish.x + dx[nextDir];
            int ny = fish.y + dy[nextDir];

            if (0 <= nx && nx < 4 && 0 <= ny && ny < 4 && arr[nx][ny] > -1) {
                arr[fish.x][fish.y] = 0;
                
                if (arr[nx][ny] == 0) {
                    fish.x = nx;
                    fish.y = ny;
                } else {
                    Fish temp = fishes.get(arr[nx][ny] - 1);
                    temp.x = fish.x;
                    temp.y = fish.y;
                    arr[fish.x][fish.y] = temp.id;

                    fish.x = nx;
                    fish.y = ny;
                }

                arr[nx][ny] = fish.id;
                fish.dir = nextDir;
                return;
            }
        }
    }

    static int[][] copyArr(int[][] arr) {
        int[][] temp = new int[4][4];

        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                temp[i][j] = arr[i][j];
            }
        }

        return temp;
    }

    static List<Fish> copyFishes(List<Fish> fishes) {
        List<Fish> temp = new ArrayList<>();
        fishes.forEach(e -> temp.add(new Fish(e.x, e.y, e.id, e.dir, e.isAlive)));
        return temp;
    }
}

Problem

• 문제 링크

낚시왕이 왼쪽에서 오른쪽 끝으로 이동하는 동안 잡은 상어 크기의 합을 구하는 문제입니다.

상어는 속력과 방향, 크기를 갖고 있으며 매 초마다 바라보는 방향으로 속력만큼 칸을 이동합니다.

만약 상어가 범위 밖으로 벗어나려고 하면 방향을 바꿔서 이동합니다.

Solution

문제에서 주어진 대로 구현하면 됩니다.

Shark 클래스를 선언해서 상어의 크기, 속력, 방향을 정의했고 좌표에 맞춰서 2차원 배열인 sharks 에 저장했습니다.

이 문제는 상어를 움직이는게 핵심입니다.

처음에는 계산하기 귀찮아서 단순하게 반복했더니.. Java 8 에서는 통과하는데 Java 11 이나 OpenJDK 환경에서는 시간초과가 발생했습니다.

따라서 어느정도 이동거리에 대한 최적화가 필요합니다.

몇 개의 예시를 만들어서 테스트 해보면 알 수 있지만 상어가 어디 위치에 있던, 일정한 거리를 이동하면 다시 원래 위치와 방향으로 돌아옵니다.

공식은 상어가 위아래로 움직일 땐 (R - 1) * 2 이고 좌우로 움직일 땐 (C - 1) * 2 입니다.

예를 들어 상어의 속력이 9 이고 위아래로 움직이며 R == 4 인 맵에 있다고 가정합니다.

상어는 어느 좌표에 있어도 6 만큼 이동하면 다시 원래 자리와 방향(중요)으로 돌아옵니다.

그렇기 때문에 9 % 6 인 3 만큼만 이동하면 상어의 최종 도착지가 됩니다.

최종 연산까지 구하기엔 아무래도 상어의 방향까지 구하기가 귀찮아서.. 나머지 연산 이후에는 직접 반복문으로 이동했습니다.

주의할 점

1. 상어는 맨 끝에 있으면서 바깥 방향을 바라본 채로 시작할 수 있습니다.
2. 상어 경쟁을 실시간으로 처리하면 이동하기 전 상어와 경쟁할 수 있기 때문에 경쟁은 모든 이동이 끝난 후에 해야 합니다.

Java Code

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

class Main {

    static class Shark {
        int speed, direction, size;
    }

    static int R, C, M;
    static int answerSumOfSize = 0;
    static Shark[][] sharks;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 격자판의 크기 R, C, 상어의 수 M
        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        sharks = new Shark[R][C];

        // M 개의 줄에 상어의 정보
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            Shark shark = new Shark();
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            shark.speed = Integer.parseInt(st.nextToken());
            shark.direction = Integer.parseInt(st.nextToken());
            shark.size = Integer.parseInt(st.nextToken());
            sharks[r - 1][c - 1] = shark;
        }

        solution();
        System.out.println(answerSumOfSize);
    }

    // 낚시왕이 오른쪽으로 한칸 이동하는건 반복문의 index 로 표현
    // 현재 상어의 위치 중 제일 가까운 상어를 잡고 상어 이동 반복
    private static void solution() {
        for (int i = 0; i < C; i++) {
            fishing(i);
            moveAllSharks();
        }
    }

    // 현재 위치에서 가장 가까이에 있는 상어를 잡는다.
    private static void fishing(int col) {
        for (int i = 0; i < R; i++) {
            if (sharks[i][col] != null) {
                answerSumOfSize += sharks[i][col].size;
                sharks[i][col] = null;
                return;
            }
        }
    }

    private static void moveAllSharks() {
        Shark[][] nextSharks = new Shark[R][C];

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                moveShark(nextSharks, i, j);
            }
        }

        // 이동 완료한 배열로 덮어 씌우기
        for (int i = 0; i < R; i++) {
            sharks[i] = Arrays.copyOf(nextSharks[i], C);
        }
    }

    private static void moveShark(Shark[][] nextSharks, int i, int j) {
        Shark shark = sharks[i][j];

        if (shark == null) {
            return;
        }

        // direction 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽
        // 위아래는 R, 좌우는 C 가 X 라고 할 때 (X - 1) * 2 만큼 이동하면 동일한 위치, 방향으로 돌아온다.
        // 그러므로 상어의 속도에서 (X - 1) * 2 을 나눈 나머지만큼만 이동하면 된다.
        // 총 이동해야 할 거리 = shark.speed % ((X - 1) * 2)
        int X = shark.direction < 3 ? R : C;
        int moveDistance = shark.speed % ((X - 1) * 2);
        int row = i;
        int col = j;

        // 움직이는 거리를 구한 후에는 직접 이동시킴
        // (최종 위치를 구했을 때 방향까지 계산하기 귀찮아서.. 직접 이동)
        for (int k = 0; k < moveDistance; k++) {
            if (shark.direction == 1) {
                row--;
                if (row < 0) {
                    shark.direction = 2;
                    row = 1;
                }
            } else if (shark.direction == 2) {
                row++;
                if (row > R - 1) {
                    shark.direction = 1;
                    row = R - 2;
                }
            } else if (shark.direction == 3) {
                col++;
                if (col > C - 1) {
                    shark.direction = 4;
                    col = C - 2;
                }
            } else {
                col--;
                if (col < 0) {
                    shark.direction = 3;
                    col = 1;
                }
            }
        }

        // 만약 이미 상어가 있으면 크기를 비교해서 사이즈 큰 놈을 남긴다
        if (nextSharks[row][col] != null && nextSharks[row][col].size > shark.size) {
            return;
        }

        nextSharks[row][col] = shark;
    }
}

Problem

• 문제 링크

매 초마다 움직이며 냄새를 뿌리는 상어들이 여러 마리 존재합니다.

각 상어들은 자신들이 바라보는 방향과 기준에 따라서 다음으로 움직일 방향을 선정합니다.

상어들이 같은 격자에 동시에 들어가게 되면 숫자가 작은 상어만 남고 나머지는 전부 내보냅니다.

가장 강한 1 번 상어가 남는 시간은 몇 초 뒤인지 구하는 문제입니다.

Solution

1 번 상어가 남거나 1000 초가 지날 때까지 다음 순서대로 반복하면 됩니다.

1. moveShark() : 상어 이동
   • 다음 방향 계산
   • 이동
   • 경쟁을 통해 작은 번호의 상어 생존
2. decreaseSmellTime() : 모든 냄새들 1 씩 감소
3. createSmell() : 상어가 이동한 자리에 새로운 냄새 생성

주의할점

1. 상어가 이동한 후에는 상어의 방향을 이동한 방향으로 바꿔주어야 합니다.
2. 위 순서에서 2번과 3번을 바꾸게 되면 상어가 새로운 냄새를 생성하자마자 1 씩 깎이기 때문에 순서를 지켜야 합니다.
3. 상어 리스트를 for 문으로 돌면서 경쟁에서 패배한 상어를 바로 제거하니 런타임 에러가 발생했습니다. for 문 도중에는 요소를 삭제하지 말고 기록해두었다가 나중에 삭제합니다.

Shark Class

• 상어의 넘버, 좌표, 현재 방향과 우선 순위를 갖고 있습니다.
• 우선 순위는 priority[현재 방향][우선 순위] 형태입니다.
• findNextDir 함수는 상어가 다음으로 이동할 방향을 구합니다.
• 현재 상어의 방향을 기준으로 우선순위가 높은 방향부터 candiates 셋에 존재하는지 확인합니다.
• candidates 셋은 상어가 이동할 수 있는 방향들을 갖고 있습니다.

arr, smellOwner, leftTime

• 각각 상어의 위치, 냄새의 주인, 냄새들의 남은 시간을 기록한 2 차원 배열입니다.

noSmellSet, mySmellSet

• 상어가 이동할 수 있는 공간을 미리 구하기 위해 사용합니다.
• 상어는 먼저 냄새가 없는 곳을 찾고 만약 4방향 전부 냄새가 존재한다면 자기 냄새가 있는 방향으로 이동합니다.
• 이동할 수 있는 곳은 여러 개가 될 수 있기 때문에 Set 자료구조에 저장하고 상어의 현재 방향에 따른 우선순위를 통해 비교합니다.

willRemove

• 경쟁에서 뒤쳐진 상어는 제거해야 합니다.
• 한번에 여러 마리가 겹칠 수 있기 때문에 Queue 에 담아둡니다.

Java Code

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

class Main {
    // 1, 2, 3, 4 는 각각 위, 아래, 왼쪽, 오른쪽
    static class Shark {
        int id, x, y, dir;
        int[][] priority = new int[5][5];

        Shark() { }

        int findNextDir(Set<Integer> candidates) {
            for (int i = 1; i < 5; i++) {
                if (candidates.contains(priority[dir][i])) {
                    return priority[dir][i];
                }
            }
            return 0;
        }
    }

    static int N, M, k;
    static int[][] arr = new int[21][21];
    static int[][] smellOwner = new int[21][21];
    static int[][] leftTime = new int[21][21];
    static Map<Integer, Shark> sharks = new HashMap<>();
    static int time = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // input
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());

                if (arr[i][j] > 0) {
                    Shark s = new Shark();
                    s.id = arr[i][j];
                    s.x = i;
                    s.y = j;
                    sharks.put(s.id, s);
                    
                    smellOwner[i][j] = s.id;
                    leftTime[i][j] = k;
                }
            }
        }

        // direction of sharks
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            Shark s = sharks.get(i + 1);
            s.dir = Integer.parseInt(st.nextToken());
        }

        // priority of sharks
        for (int i = 0; i < M; i++) {
            Shark s = sharks.get(i + 1);

            for (int j = 0; j < 4; j++) {
                st = new StringTokenizer(br.readLine());

                for (int z = 0; z < 4; z++) {
                    s.priority[j + 1][z + 1] = Integer.parseInt(st.nextToken());
                }
            }
        }

        // solution
        solution();
    }

    static void solution() {
        while (time++ < 1000) {
            moveShark();
            decreaseSmellTime();
            createSmell();

            if (sharks.size() == 1) {
                System.out.println(time);
                return;
            }
        }

        System.out.println(-1);
    }

    // 상어 이동 후 겹친 애 쫓아내기
    static void moveShark() {
        // dx dy 는 위, 아래, 왼쪽, 오른쪽 순서
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        Queue<Integer> willRemove = new LinkedList<Integer>();

        for (Integer id : sharks.keySet()) {
            Set<Integer> noSmellSet = new HashSet<>();
            Set<Integer> mySmellSet = new HashSet<>();
            Shark s = sharks.get(id);

            for (int i = 0; i < 4; i++) {
                int nx = s.x + dx[i];
                int ny = s.y + dy[i];

                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;

                if (smellOwner[nx][ny] == 0) {
                    noSmellSet.add(i + 1);
                } else if (smellOwner[nx][ny] == s.id) {
                    mySmellSet.add(i + 1);
                }
            }

            // 냄새 없는 곳부터 스캔하고 자기 냄새 있는 곳을 스캔해서 이동할 방향 구하기
            int nextDir = s.findNextDir(noSmellSet);

            if (nextDir == 0) {
                nextDir = s.findNextDir(mySmellSet);
            }

            // 상어 이동
            arr[s.x][s.y] = 0;
            if (nextDir == 1) {
                s.x -= 1;
            } else if (nextDir == 2) {
                s.x += 1;
            } else if (nextDir == 3) {
                s.y -= 1;
            } else if (nextDir == 4) {
                s.y += 1;
            }
            
            // 이동할 위치에 상어 있으면 경쟁 후 작은 번호가 승리
            if (arr[s.x][s.y] == 0 || s.id < arr[s.x][s.y]) {
                arr[s.x][s.y] = s.id;
                s.dir = nextDir;
            } else {
                willRemove.add(s.id);
            }
        }

        while (!willRemove.isEmpty()) {
            sharks.remove(willRemove.poll());
        }
    }

    // 맵 전체의 냄새 시간을 하나씩 감소 시키고 0 이 되면 냄새 주인 정보도 지움
    static void decreaseSmellTime() {
        for(int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (leftTime[i][j] == 0) continue;

                leftTime[i][j]--;

                if (leftTime[i][j] == 0) {
                    smellOwner[i][j] = 0;
                }
            }
        }
    }

    // 상어가 이동한 곳에 새로운 냄새 생성
    static void createSmell() {
        for (Integer id : sharks.keySet()) {
            Shark s = sharks.get(id);

            smellOwner[s.x][s.y] = s.id;
            leftTime[s.x][s.y] = k;
        }
    }
}

Problem

• 문제 링크

T 초가 지난 후 남아있는 미세 먼지들의 총 합을 구하는 문제입니다.

Solution

구현 문제입니다.

1. 미세먼지 확산
2. 공기청정기 가동

주의할 점은 미세먼지 확산 시 기존 배열 (아래 코드에서는 arr) 을 바로 수정하지 않는 겁니다.

예를 들어 (1, 1) = 5, (1, 2) = 9 의 미세머지가 있다고 가정합니다.

만약 기존 배열을 그대로 수정하면 (1, 1) 에 있던 미세먼지를 먼저 확산시켜서 (1, 2) 의 미세먼지가 10 이 되고

반복문이 (1, 2) 위치에 도달했을 때 10 을 기준으로 확산하기 때문에 주변에 2 씩 퍼지게 됩니다.

그래서 미세먼지의 확산 결과를 temp 배열에다가 담았다가 arr 배열에 덮어쓰는 형식으로 구현했습니다.

공기청정기는 그냥 노가다로 구현했습니다.

Java Code

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

class Main {
    static int R, C, T;
    static int[][] arr = new int[50][50];
    static List<Integer> airCleanerRows = new ArrayList<>();
    static int sumOfDust = 2;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // input
        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < C; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                sumOfDust += arr[i][j];

                if (arr[i][j] == -1) {
                    airCleanerRows.add(i);
                }
            }
        }

        // solution
        solution();
    }

    static void solution() {
        while (T-- > 0) {
            // 1. 먼지 확산
            arr = spreadDust();

            // 2. 공기청정기 가동
            executeAirCleaner();
        }

        System.out.println(calculateSum());
    }

    static int[][] spreadDust() {
        int[][] temp = new int[50][50];
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        // 확산된 미세먼지를 temp 배열에 계산
        for (int x = 0; x < R; x++) {
            for (int y = 0 ; y < C; y++) {
                if (arr[x][y] == -1) {
                    temp[x][y] = -1;
                    continue;
                }

                temp[x][y] += arr[x][y];

                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];

                    if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
                    if (arr[nx][ny] == -1) continue;

                    temp[nx][ny] += (arr[x][y] / 5);
                    temp[x][y] -= (arr[x][y] / 5);
                }
            }
        }

        return temp;
    }

    static void executeAirCleaner() {
        // 위쪽 공기청정기는 반시계방향
        int top = airCleanerRows.get(0);

        for (int x = top - 1; x > 0; x--) {
            arr[x][0] = arr[x-1][0];
        }
        
        for (int y = 0; y < C - 1; y++) {
            arr[0][y] = arr[0][y+1];
        }

        for (int x = 0; x < top; x++) {
            arr[x][C-1] = arr[x+1][C-1];
        }
        
        for (int y = C - 1; y > 1; y--) {
            arr[top][y] = arr[top][y-1];
        }

        arr[top][1] = 0;
        

        // 아래쪽 공기청정기는 시계 방향
        int bottom = airCleanerRows.get(1);
        
        for (int x = bottom + 1; x < R - 1; x++) {
            arr[x][0] = arr[x+1][0];
        }

        for (int y = 0; y < C - 1; y++) {
            arr[R-1][y] = arr[R-1][y+1];
        }

        for (int x = R - 1; x > bottom; x--) {
            arr[x][C-1] = arr[x-1][C-1];
        }

        for (int y = C - 1; y > 1; y--) {
            arr[bottom][y] = arr[bottom][y-1];
        }

        arr[bottom][1] = 0;
    }

    static int calculateSum() {
        int sum = 2;

        for (int x = 0; x < R; x++) {
            for (int y = 0; y < C; y++) {
                sum += arr[x][y];
            }
        }
        
        return sum;
    }
}

Problem

• 문제 링크

모든 승객들을 도착지에 옮겨주고 난 뒤 남은 연료의 양을 출력하는 문제입니다.

승객들을 데리러 가는 기준은 가까운 기준이며 같은 거리에 여러 명의 승객이 있다면 행 번호가 가장 작고 열 번호가 가장 작은 승객을 데리러 갑니다.

Solution

귀찮은 구현 문제입니다.

아래 과정을 계속 반복하면 됩니다.

1. BFS 를 사용하여 승객 찾기
2. 가장 가까운 승객 비교
3. 도착지에 데려다줌
4. 연료 확인

주의사항도 있습니다.

1. A 의 도착지와 B 의 출발지가 같은 경우 존재 -> 택시의 현재 위치도 검사
2. 도착지는 겹칠 수 있음 -> 도착지를 특정해놓고 BFS 를 진행
3. 행과 열 우선순위 헷갈리지 않게 주의
4. 연료는 많은데 벽에 막혀서 출발지 또는 도착지로 가지 못하는 경우 -> 승객을 태우거나 내리지 못했는데 BFS 가 끝나진 않았는지 확인

변수

가장 가까운 승객 비교하기

Taxi 클래스에 있는 move 변수를 이용하면 특정 좌표에 도달했을때 택시 위치로부터 얼만큼 이동했는지 알 수 있습니다.

BFS 를 진행하면서 승객 위치에 도달하면 candidates 큐에 담아둡니다.

prevMove 변수를 사용해서 이전 move 를 기억하고 있다가 둘이 달라지는 순간에 candidates 큐에 값이 있는지 없는지 검사합니다.

만약 값이 없으면 계속 BFS 를 진행하면 되고 값이 있다면 최단거리인 승객들을 이미 찾았기 때문에 break 로 빠져나옵니다.

candidates 큐에 있는 승객들은 모두 거리가 같기 때문에 행과 열을 비교하여 조건에 맞는 승객을 찾아서 태웁니다.

우선순위 큐를 쓰면 큐에 넣을때마다 매번 비교를 하기 때문에 그냥 일반큐로 하고 나중에 비교했습니다.

도착지에 데려다줌

taken 으로 타고 있는 승객의 정보를 알 기 때문에 도착지 좌표에 도달할 때까지 BFS 를 진행하면 됩니다.

연료 확인

BFS 가 끝나면 prevMove 값을 반환합니다.

이동한 거리, 즉 사용한 연료기 때문에 전체 연료량과 연산한 뒤 음수가 되는지 확인하면 됩니다.

벽에 막혀서 연료가 충분한데 도달할 수 없거나 이동 중에 연료가 떨어지면 Integer.MAX_VALUE 를 리턴하여 fuel 값을 음수로 만들어줍니다.

Java Code

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

class Main {
    static class Taxi {
        int x, y, move;

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

    static class Passenger {
        int id, sx, sy, ex, ey;

        Passenger() { }
    }

    static int N, M, fuel;
    static int[][] arr = new int[21][21];
    static Taxi taxi;
    static Passenger taken = null;
    static Map<Integer, Passenger> passMap = new HashMap<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // input
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        fuel = Integer.parseInt(st.nextToken());

        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 1; j < N + 1; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        taxi = new Taxi(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            Passenger p = new Passenger();
            p.id =  i + 2;  // 벽이 1 이라서 2 부터 넘버링
            p.sx = Integer.parseInt(st.nextToken());
            p.sy = Integer.parseInt(st.nextToken());
            p.ex = Integer.parseInt(st.nextToken());
            p.ey = Integer.parseInt(st.nextToken());

            passMap.put(p.id, p);

            // 출발지는 겹치지 않기 때문에 맵에 기록
            arr[p.sx][p.sy] = p.id;
        }

        // solution
        solution();
    }

    // 모든 승객을 데려다 줄때까지 BFS 를 반복하며 연료의 양을 확인한다.
    static void solution() {
        while (!passMap.isEmpty()) {
            int toStartFuel = bfs();
            fuel -= toStartFuel;

            if (fuel < 0) break;

            int toDestFuel = bfs();
            fuel -= toDestFuel;

            if (fuel < 0) break;

            fuel += toDestFuel * 2;
        }

        System.out.println(fuel < 0 ? -1 : fuel);
    }

    static int bfs() {
        Queue<Taxi> q = new LinkedList<>();
        Queue<Passenger> candidates = new LinkedList<>();
        boolean[][] visited = new boolean[21][21];
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        
        int prevMove = taxi.move;
        visited[taxi.x][taxi.y] = true;
        q.add(taxi);

        while (!q.isEmpty()) {
            Taxi now = q.poll();

            // 이동 중에 연료가 떨어지면 종료
            if (fuel - now.move < 0) {
                return Integer.MAX_VALUE;
            }

            // 택시 이동 시간대가 다르고 candidates 가 이미 존재하면 break
            if (prevMove != now.move && !candidates.isEmpty()) {
                break;
            }

            prevMove = now.move;

            if (taken == null) {
                // 택시가 비어있는 경우 가장 가까운 승객 후보를 만나면 candidates 에 추가
                int id = arr[now.x][now.y];

                if (id > 1) {
                    Passenger p = passMap.get(id);
                    candidates.add(p);
                }
            } else {
                // 택시에 승객이 있는 경우 도착지를 만나면 종료
                if (now.x == taken.ex && now.y == taken.ey) {
                    passMap.remove(taken.id);
                    taken = null;
                    taxi = new Taxi(now.x, now.y, 0);
                    return prevMove;
                }
            }

            // 동서남북 이동
            for (int i = 0 ; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                if (0 < nx && nx < N+1 && 0 < ny && ny < N+1) {
                   if (arr[nx][ny] != 1 && visited[nx][ny] == false) {
                       q.add(new Taxi(nx, ny, now.move + 1));
                       visited[nx][ny] = true;
                   } 
                }
            }
        }

        // while 문이 끝났는데 candidates 에 아무것도 없으면 벽에 막혀서 도달못함
        if (candidates.isEmpty()) {
            return Integer.MAX_VALUE;
        }

        taken = findNearest(candidates);
        taxi = new Taxi(taken.sx, taken.sy, 0);
        arr[taken.sx][taken.sy] = 0;
        return prevMove;
    }

    // 같은 거리면 x 가 작고, y 가 작은 사람으로
    static Passenger findNearest(Queue<Passenger> q) {
        Passenger target = q.poll();

        while (!q.isEmpty()) {
            Passenger compare = q.poll();

            if (compare.sx < target.sx) {
                target = compare;
            } else if (compare.sx == target.sx && compare.sy < target.sy) {
                target = compare;
            }
        }

        return target;
    }
}