[BOJ] 14620: 꽃길 (JAVA)

문제

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

 

여담

방문 처리가 제대로 되지 않길래 잘 작성했는데 대체 뭐지? 했는데 방문 처리하는 좌표의 값을 잘못 넣어준 것이었다.. 이런 실수가 대체 몇 번인지 진짜.. 백준 풀 때 아주 나쁜 습관만 들어서 큰일났다..ㅋㅋ

 

풀이

화단의 한 변의 최대 길이가 10이고, 설치하는 꽃도 3개이므로 완전 탐색과 백트래킹을 사용해서 풀 수 있다.

 

설치한 꽃의 개수가 3이 될 때까지 완탐(=dfs 메소드)을 수행해서 최소 비용을 구하면 된다. dfs 메소드에서 중요한 부분은 방문 처리를 하는 부분이다. 꽃을 설치할 수 있을 때에만 방문 처리를 해야 하므로, 네 방향의 좌표를 저장하기 위한 배열을 하나 선언한다.

• Pos[] pos = new Pos[4]

 

그 후, 네 방향을 확인하고 꽃을 설치할 수 있는 경우에만 방문 처리를 하고 dfs 메소드를 재귀 호출한다. 재귀 호출이 끝나면 다시 원래 상태로 돌려놓아야 하므로, 방문 처리를 취소하면 된다.

• 위치 기록
  • pos[k] = new Pos(nx, ny)
• 방문 처리
  • visited[i][j] = true
  • visited[p.x][p.y] = true
• dfs 메소드 재귀 호출
  • dfs(cnt + 1, sum + total)
• 방문 처리 취소
  • visited[i][j] = false
  • visited[p.x][p.y] = false

 

자세한 내용은 아래 코드를 참고하면 된다. 

 

코드

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

public class Main {
    static int n, answer = Integer.MAX_VALUE;
    static int[][] board;
    static boolean[][] visited;
    static int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n][n];
        visited = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 하나 설치 > 방문 처리 & 합 구해서 넘기기
        // 하나 더 설치 > 겹치는지 확인 > 겹친다면 종료하고 그렇지 않다면 방문 처리 & 합 구해서 넘기기
        // 같은 방식으로 하나 더 설치
        // 최소 비용 갱신

        dfs(0,0);
        System.out.println(answer);
    }

    static void dfs(int cnt, int sum) {
        if (cnt == 3) { // 꽃 3개를 다 설치한 경우
            answer = Math.min(answer, sum); // 최소 비용으로 갱신
            return;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                if (visited[i][j]) continue;

                Pos[] pos = new Pos[4];
                boolean isOut = false;
                int total = board[i][j];
                for (int k = 0; k < 4; k++) {
                    int nx = i + move[k][0];
                    int ny = j + move[k][1];
                    // 격자를 벗어나거나 겹치는 꽃이 있다면 탐색 종료
                    if (nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny]) {
                        isOut = true;
                        break;
                    }
                    // 아니면 위치 기록
                    pos[k] = new Pos(nx, ny);
                    total += board[nx][ny];
                }
                if (isOut) continue;

                // 땅 방문 처리
                visited[i][j] = true;
                for (Pos p : pos) {
                    visited[p.x][p.y] = true;
                }
                dfs(cnt + 1, sum + total);
                // 땅 방문 처리 취소
                visited[i][j] = false;
                for (Pos p : pos) {
                    visited[p.x][p.y] = false;
                }
            }
        }
    }

    static class Pos {
        int x, y;

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

---