[JAVA] 백준, 14620번 꽃길

 

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

 

풀이

arr은 입력 받은 값이고 sumArr은 자신의 좌표를 포함한 상하좌우의 총합을 저장하는 배열이다.

이 문제는 배열을 전체 탐색하면서 모든 경우의 수를 고려해야 한다.

dfs()에서 모든 좌표에 대해서 탐색을 돌면서 방문하지 않은 좌표에 대해서 재귀적으로 호출한다.

 

현재 좌표를 방문 처리하고 해당 좌표에 대해서 다시 탐색을 한다. 탐색이 종료되면 방문 기록을 지워서 모든 경우의 수를 고려할 수 있도록 한다.

 

참고로 x, y = 1 ~ N -1 까지 탐색하는 이유는 sumArr 배열의 모서리 부분은 모두 0이 저장되어 있기 때문에 탐색할 필요가 없다. 모서리 부분은 꽃을 심을 수 없는 영역이기 때문이다.

코드

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

public class Main {

    static int N;
    static int[][] arr;
    static int[][] sumArr;
    static int result = Integer.MAX_VALUE;

    static int[] dx = {-1, 0, 1, 0, 0};
    static int[] dy = {0, 0, 0, -1, 1};

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

        N = Integer.parseInt(br.readLine());

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

        sumArr = new int[N][N];
        boolean[][] visited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (isNotOutOfRange(j, i)) {
                    sumArr[i][j] =
                        arr[i][j - 1] + arr[i][j + 1] + arr[i - 1][j] + arr[i + 1][j] + arr[i][j];
                }
            }
        }

        dfs(visited, 0, 0);

        System.out.println(result);
    }

    static void dfs(boolean[][] visited, int cnt, int sum) {

        // 최소 값보다 크므로 더이상 탐색할 필요 없다.
        if (sum >= result) {
            return;
        }

        // 탐색 종료 조건
        if (cnt == 3) {
            result = Math.min(result, sum);
            return;
        }

        for (int y = 1; y < N - 1; y++) {
            for (int x = 1; x < N - 1; x++) {
                if (isNotVisited(visited, x, y)) {
                    visit(visited, x, y); // 방문 처리
                    dfs(visited, cnt + 1, sum + sumArr[y][x]);
                    unVisit(visited, x, y); // 방문 취소 -> 모든 좌표에 대해서 탐색해야하기 때문이다.
                }
            }
        }

    }

    // 인덱스 벗어나는지 확인
    static boolean isNotOutOfRange(int x, int y) {
        if (x - 1 < 0 || x + 1 >= N || y - 1 < 0 || y + 1 >= N) {
            return false;
        }
        return true;
    }

    // 방문 여부 확인
    static boolean isNotVisited(boolean[][] visited, int x, int y) {
        for (int d = 0; d < 5; d++) {
            if (visited[y + dy[d]][x + dx[d]]) {
                return false;
            }
        }
        return true;
    }

    // 방문처리
    static void visit(boolean[][] visited, int x, int y) {
        for (int d = 0; d < 5; d++) {
            visited[y + dy[d]][x + dx[d]] = true;
        }
    }

    // 방문 취소
    static void unVisit(boolean[][] visited, int x, int y) {
        for (int d = 0; d < 5; d++) {
            visited[y + dy[d]][x + dx[d]] = false;
        }
    }
}