[백준/BOJ] 14620번 : 꽃길 - Java(자바)

 

완전탐색 문제에 대한 연습이 필요하다고 생각했다.

 

그래서 여러 문제를 찾아보던 중, 재밌어 보이는 문제를 발견했다.

 

바로 꽃길.

 

이렇게 그래픽으로 예제를 보여주는 문제는 왠지 더 흥미진진하게 느껴진다.

 

 

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

 

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

14620번: 꽃길

 

---

 

처음 문제를 보고 떠오른 풀이는 아래와 같다.

 

 

그리고 이를 구현하였다.

 

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

class Seed {
    int x, y, price;

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

public class Main {
    static ArrayList<Seed> list;
    static int[] dx = {0, 0, -1, 1}; // 상하좌우
    static int[] dy = {-1, 1, 0, 0}; // 상하좌우
    static int[][] garden;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        garden = new int[n][n];
        
        ArrayList<Seed> candidateSeeds = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                garden[i][j] = Integer.parseInt(st.nextToken());

                // 가장 바깥 테두리는 돌지 않으면서 5평의 합을 가진 Seed 객체를 candidateSeeds에 담기
                if ((i > 0 && i < n - 1) && (j > 0 && j < n - 1)) {
                    candidateSeeds.add(new Seed(i, j));
                }
            }
        }

        // candidateSeeds의 5평 합 구하기
        for (Seed seed : candidateSeeds) {
            seed.price = calc5LandsPrice(seed);
        }

        // 5평의 합을 기준으로 정렬하기
        candidateSeeds.sort(new Comparator<Seed>() {
            @Override
            public int compare(Seed o1, Seed o2) {
                return Integer.compare(o1.price, o2.price);
            }
        });

        int ans = 0;
        list = new ArrayList<>();
        for (Seed seed : candidateSeeds) {
            if (list.size() < 3 && isNotDuplicatedPlace(seed)) {
                list.add(seed);
                ans += seed.price;
            }
        }
        System.out.println(ans);
    }

    public static int calc5LandsPrice(Seed seed) {
        int sum = garden[seed.x][seed.y];

        for (int i = 0; i < dx.length; i++) {
            int mX = seed.x + dx[i];
            int mY = seed.y + dy[i];

            sum += garden[mX][mY];
        }
        return sum;
    }

    public static boolean isNotDuplicatedPlace(Seed candidate) {
        for (Seed seed : list) {
            // Seed의 꽃이 개화할 5평을 감싸는 다이아몬드 위치에 다른 씨앗이 존재하면 중복이 됨
            if (Math.abs(seed.x - candidate.x) + Math.abs(seed.y - candidate.y) <= 2) {
                return false;
            }
        }
        return true;
    }
}

 

 

그런데 25%에서 틀렸다고 나왔다

 

나름 고쳐봤는데, 똑같은 케이스에서 틀려버렸다.

 

 

 

아무리 생각해도 맞은 것 같은데..

맞왜틀을 계속 떠올리며 2시간이 지났다.

 

 

[나동빈님 - https://www.youtube.com/watch?v=OZu_BRDqJEQ]

 

실버 딱지를 뗐다고 생각했는데, 내 실력은 여전히 실버에 머물러 있나보다.

 

 

그래서 결국 다음에 다시 생각해야겠다고 결심하고, 다른 문제를 풀었다.

 

 

그러나 2시간 정도가 지나서 "진짜 맞왜틀...?" 을 벗어나지 못해, 해당 문제로 다시 돌아왔다.

 

 

놀랍게도 바로 반례가 떠올랐다.

 

 

 

 

 

문제를 그리디하게 풀고 있었던 것이다.

 

 

빨간색 하이라이트가 제일 작은 값을 지닌다.

 

 

그러나 해당 위치에 꽃을 심으면, 최적해를 구할 수 없다.

 

 

그래서 백트래킹을 통해 구현하였다.

 

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

class Seed {
    int x, y;

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

public class Main {
    static ArrayList<Seed> candidateSeeds;
    static boolean[][] visited;
    static int[][] garden;
    static int[] dx = {0, 0, -1, 1}; // 상하좌우
    static int[] dy = {-1, 1, 0, 0}; // 상하좌우
    static int n;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        garden = new int[n][n];
        visited = new boolean[n][n];

        candidateSeeds = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                garden[i][j] = Integer.parseInt(st.nextToken());

                // 가장 바깥 테두리는 돌지 않으면서 5평의 합을 가진 Seed 객체를 candidateSeeds에 담기
                if ((i > 0 && i < n - 1) && (j > 0 && j < n - 1)) {
                    candidateSeeds.add(new Seed(i, j));
                }
            }
        }

        dfs(0, 0);
        System.out.println(min);

    }

    public static void dfs(int depth, int sum) {
        if (depth == 3) {
            min = Math.min(min, sum);
            return;
        }

        for (Seed seed : candidateSeeds) {
            if (isPossible(seed)) {
                setVisited(seed, true);
                dfs(depth + 1, sum + calc5LandsPrice(seed));
                setVisited(seed, false);
            }
        }
    }

    private static void setVisited(Seed seed, boolean flag) {
        visited[seed.x][seed.y] = flag;

        for (int i = 0; i < dx.length; i++) {
            int mX = seed.x + dx[i];
            int mY = seed.y + dy[i];

            visited[mX][mY] = flag;
        }
    }

    public static boolean isPossible(Seed seed) {
        if (visited[seed.x][seed.y]) {
            return false;
        }

        for (int i = 0; i < dx.length; i++) {
            int mX = seed.x + dx[i];
            int mY = seed.y + dy[i];

            if (visited[mX][mY]) {
                return false;
            }
        }
        return true;
    }

    public static int calc5LandsPrice(Seed seed) {
        int sum = garden[seed.x][seed.y];

        for (int i = 0; i < dx.length; i++) {
            int mX = seed.x + dx[i];
            int mY = seed.y + dy[i];

            sum += garden[mX][mY];
        }
        return sum;
    }
}