[JAVA] 14620 - 꽃길 🩶2: 방문배열을 야무지게 활용하는 완탐 문제

들어가며

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

각 땅에는 가격이 매겨져 있고, 꽃 씨앗을 심으면 상하좌우로 꽃이 핀다. 3개의 꽃이 필 수 있는 경우의 수 중에서 가격의 최소를 구하면 되는 문제이다.

결국 모든 경우의 수를 돌아야 하기에 완전탐색인 문제인 것은 분명하다. 그리고 시간복잡도도 100C3(=: 백만 정도)로 매우 넉넉하다! 

본문으로

사실 아래처럼 생각을 정리하긴 했는데,, 꽃을 놓고 지우는 로직이 구현자체가 처음에 잘 떠오르지 않아서 이 글을 작성한다.

그렇다. 꽃 놓을 수 있는 확인을 먼저하고, 놓을 수 있으면 꽃을 놓은 다음 재귀적으로 꽃 개수가 3일때까지 탐색한다. 그리고 꽃을 지워줘야 하는 것이 완탐 로직의 핵심이었다.

아래는 정답 로직이다.

public class Main {

    static int N, ret;
    static int[][] maps;
    static int[][] visited;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    static void go(int cnt, int cost) {

        if (cnt == 3) {
            ret = Math.min(cost, ret);
            return;
        }
        if (cost > ret) { // 가지치기
            return;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (canFlower(i, j)) {
                    go(cnt + 1, cost + makeFlower(i, j));
                    eraseFlower(i, j);
                }
            }
        }

    }

    static boolean canFlower(int y, int x) {
        if (visited[y][x] != 0) {
            return false;
        }

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || nx < 0 || ny >= N || nx >= N) {
                return false;
            }
            if (visited[ny][nx] != 0) {
                return false;
            }
        }
        return true;
    }

    static int makeFlower(int y, int x) {
        int sum = maps[y][x];
        visited[y][x] = 1;
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || nx < 0 || ny >= N || nx >= N) {
                continue;
            }
            visited[ny][nx] = 1;
            sum += maps[ny][nx];
        }
        return sum;
    }

    static void eraseFlower(int y, int x) {
        visited[y][x] = 0;
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || nx < 0 || ny >= N || nx >= N) {
                continue;
            }
            visited[ny][nx] = 0;
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());

        maps = new int[N][N];
        visited = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            for (int j = 0; j < N; j++) {
                maps[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        ret = Integer.MAX_VALUE;
        go(0, 0);

        System.out.println(ret);
    }
}

마무리하며

완탐 문제는 생각의 흐름만 잘 정리해서, 범위와 전역 지역 변수를 적절히 선언 후 메서드만 뽑아낼 수 있다면 쉽게 풀리는 것 같다. 하지만 그 생각을 코드로 구현하는 것은 아직 미숙하다. 이 부분은 연습만이 살길이다!

꼭 시간복잡도 확인 -> 완탐으로 풀리는지 -> 메서드 정리 -> 구현 순서대로 연습하자. 파이팅이다!!