[백준] BOJ 18809 Gaaaaaaaaaarden (골드 1)

문제

---

https://www.acmicpc.net/problem/18809

18809번: Gaaaaaaaaaarden

---

해설

---

1. 해당 문제 해결을 위해서는 조합 + 조합을 구현해야 한다.
   1. N개의 가능한 토양에서 (G+R : 모든 배양액의 수)개를 선택해야한다. n C (g + r) → 1번 조합
   2. 선택한 토양에서 어디에 Green을 배치할지 (선택되지 않은 토양은 Red) (g + r) C g → 2번 조합
2. 조합은 NextPermutation 알고리즘을 이용하여 메서드로 빼고 2번의 조합을 구할때 하나의 메서드를 재사용한다.
3. 각각의 배양액을 다른 큐로 관리하고, 각각을 너비만큼 BFS를 수행한다.
4. 너비만큼 수행하면 같은 시간(너비)를 가지는 큐노드만 한번의 탐색에서 수행되므로
   같은 시간에 도착한 것을 확인할 수 있다.

---

주의사항

---

 

---

코드 (시뮬레이션 + 브루트포스)

---

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

public class BOJ18809 {
    static int N, M, G, R;
    static int[][] map;
    static int max = 0;
    static List<Pair> places;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    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());
        G = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        places = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 2) places.add(new Pair(i, j, 1));
            }
        }

        combinationPlace();
        System.out.println(max);
    }

    /**
     *  K개의 배양 가능한 토양의 개수에서 G + R개의 토양 선택 (조합)
     *  G + R개의 선택된 토양에서 G개의 토양에 G, 나머지에 R 두기 (조합)
     */

    //토양뽑기
    private static void combinationPlace() {
        int[] idxs = new int[places.size()];
        //places에서 조합으로 뽑아낼 인덱스
        for (int i = idxs.length - 1; i >= idxs.length - (G + R); i--) {
            idxs[i] = 1;
        }

        do {
            combinationColor(idxs);
        } while (nextPermutation(idxs));
    }

    //    뽑은 토양에서 다시 배치할 색 뽑기
    private static void combinationColor(int[] idxs) {
        int[] colors = new int[G + R];
        for (int i = colors.length - 1; i >= R; i--) {
            colors[i] = 1;
        }

        do {
            simulation(idxs, colors);
        } while (nextPermutation(colors));
    }

    private static void simulation(int[] idxs, int[] colors) {
        Queue<Pair> reds = new ArrayDeque<>();
        Queue<Pair> greens = new ArrayDeque<>();

        int idx = 0;
        int[][][] isv = new int[2][N][M];
        for (int i = 0; i < idxs.length; i++) {
            if (idxs[i] == 1) {
                Pair pair = places.get(i);
                if (colors[idx++] == 0) {
                    reds.offer(pair);
                    isv[1][pair.x][pair.y] = 1;
                } else {
                    greens.offer(pair);
                    isv[0][pair.x][pair.y] = 1;
                }

            }
        }

        bfs(reds, greens, isv);

    }

    private static void bfs(Queue<Pair> reds, Queue<Pair> greens, int[][][] isv) {
        int cnt = 0;

        while (!reds.isEmpty() || !greens.isEmpty()) {
            int size1 = greens.size();
            while (size1-- > 0) {
                cnt = go(greens, isv, cnt, 0);
            }
            int size2 = reds.size();
            while (size2-- > 0) {
                cnt = go(reds, isv, cnt, 1);
            }
        }
        max = Math.max(max, cnt);
    }

    public static int go(Queue<Pair> queue, int[][][] isv, int cnt, int flag){
        Pair p = queue.poll();
		/**
         * 4방 탐색에서 처리하지 않는 이유
         * 로직
         * 1. green이 너비만큼 먼저 이동
         * 2. red가 너비만큼 이동 
         * 3. 조건 : 너비 (사실상 시간)이 동일할 때 꽃이 핀다.
         * 4. 위 조건을 만족하려면 red가 이동할때 green의 너비와 같으면 꽃이 피는 것이다.
         * 5. 이때, green입장에서는 더 퍼지면 안되는 노드들이 이미 큐에 들어가있는 상태이다.
         *    ex) green(2,2)에 2초에 도착 -> 4방탐색하며 큐에 4개를 시간 3과함께 넣는다.
         *        현재 green(2,3)에 3초에 도착이라고 표시하고 큐에 넣은 상태
         */
         //red일때는 green, green일때는 red를 확인하는 것을 flag^1로 반대 확인
        if(isv[flag^1][p.x][p.y] == -1) return cnt;
        if(isv[flag^1][p.x][p.y] == p.t) {
            cnt++;
            isv[0][p.x][p.y] = -1;
            isv[1][p.x][p.y] = -1;
            return cnt;
        }

        for (int i = 0; i < 4; i++) {
            int nx = p.x + dx[i];
            int ny = p.y + dy[i];
			
            if (isValid(nx, ny) || isv[flag][nx][ny] != 0) continue;
            if(isv[flag^1][nx][ny] == 0 || isv[flag^1][nx][ny] == p.t + 1){
                queue.offer(new Pair(nx, ny, p.t + 1));
                isv[flag][nx][ny] = p.t + 1;
            }
        }
        return cnt;
    }

    private static boolean isValid(int nx, int ny) {
        return nx < 0 || ny < 0 || nx >= N || ny >= M || map[nx][ny] == 0;
    }

    public static boolean nextPermutation(int[] arr){
        int i = arr.length - 1;
        while (i > 0 && arr[i - 1] >= arr[i]) i--;
        if(i == 0) return false;
        int dest = i - 1;

        int j = arr.length - 1;
        while (j > dest && arr[dest] >= arr[j]) j--;
        swap(arr, j, dest);

        int k = arr.length - 1;
        while (i < k) swap(arr, i++, k--);

        return true;
    }

    private static void swap(int[] arr, int j, int dest) {
        int temp = arr[j];
        arr[j] = arr[dest];
        arr[dest] = temp;
    }
}

class Pair{
    int x, y, t;

    public Pair(int x, int y, int t) {
        this.x = x;
        this.y = y;
        this.t = t;
    }
}

---

결론

---

해설이 정말 간단하지만, 조합을 2번 수행해야 하고 BFS할 때 고려해야할 사항이 많았다.

특히 처음에 문제를 잘못 생각해서 배양액이 이미 있는 곳도 갈 수 있다고 생각해서 시간을 날렸고,

배양액 1개당 꽃이 1개만 필 수 있는 줄 알아서 배양액이 1개 생성되었을 때
해당 배양액으로 부터 BFS로 퍼져나온 모든 배양액을 추적해서 지워주도록 로직을 작성했었다..

문제를 잘 읽는 것도 중요하지만 이번 문제는 솔직히 설명이 조금은 부족하지 않았나 싶다 ㅠㅠ

하지만 결론적으로는 해결해서 너무 뿌듯했던 문제!!

---