[Java] 백준 14620 꽃길 - 실버2

 

• 완전 탐색해야하는 문제!
• 백트래킹을 사용한다
• dfs방식으로 해를 찾고, visit 배열을 되돌리는 방법을 사용
• 시간복잡도 문제로 꼭 가지치기를 해줘야한다

 

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

//[baekjoon] java-1058
public class Main {

  private static int min = 3001; //(5*3*200)
  private static int size;
  private static int[][] arr;
  private static boolean[][] visit;

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

    size = Integer.parseInt(br.readLine());
    arr = new int[size][size];
    visit = new boolean[size][size];
    StringTokenizer st;
    //입력받기
    for (int i=0; i<size; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j<size; j++)
        arr[i][j] = Integer.parseInt(st.nextToken());
    }

    dfs(1,0,0,0);

    System.out.println(min);
  }

  static void dfs(int x, int y, int cnt, int sum) {

    if (sum > min)
      return;

    if (cnt == 3) {
      min = sum;
      return;
    }

    for (int i = x; i< size-1; i++) {
      for (int j = 1; j < size -1; j++) {
        if (i == x && j<=y)
          continue;

        if (!isOverlap(i, j)) {
          changeVisit(i, j, true);
          dfs(i, j, cnt+1, sum + arr[i][j] + arr[i+1][j] + arr[i][j+1] + arr[i-1][j] + arr[i][j-1]);
          changeVisit(i, j, false);
        }
      }
    }
  }

  static void changeVisit(int i, int j, boolean isVisit) {
    visit[i][j] = isVisit;
    visit[i-1][j] = isVisit;
    visit[i][j-1] = isVisit;
    visit[i+1][j] = isVisit;
    visit[i][j+1] = isVisit;
  }

  static boolean isOverlap(int i, int j) {
    return visit[i][j] || visit[i+1][j] ||visit[i][j+1] ||visit[i-1][j] ||visit[i][j-1];
  }
}

• 입력을 받아 화단의 가격을 arr 2차원 배열에 저장한다
  • 가장자리 부분은 어차피 심을 수 없으니 씨앗을 심을 수 있는 인덱스 범위는 1~(size-2)로 생각할 수 있다
• dfs를 수행해준다. 
• 만약 화단에 심을 수 있는 경우라면 꽃의 위치에 해당하는 visit 배열 값을 true로 설정해준다
  • 그리고 해당 인덱스를 넣어 dfs를 호출해준다
  • dfs가 끝났다면 해당하는 해를 모두 구한 뒤이기 때문에 visit 값을 원복시킨다
• 만약 현재까지 더한 값이 min값보다 크면 dfs를 중단시킨다(중요)
  • 백트래킹에서 가장 중요한 건 가지치기인데, 이부분임

 

가지치기를 했을때와 안했을 때 시간차이가 극명한 것을 확인가능(20배 가까이 차이가 난다)