꽃길 [BOJ 14620]

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
• 주어진 자료는 무엇인가?
• 조건은 무엇인가?
• 우리가 문제를 풀기 위해 주어진 자료가 충분한가?
• 숨겨진 조건이나 자료가 있는가? 그렇다면 그 것을 다른 방법으로 해석해보라. 

    - 문제는 무엇인가?

-> 꽃을 심기 위한 최소 비용을 출력하라

-> 세 점을 선택하라

-> 그리고 그 세 점을 선택하면, 각각의 점에서 선택이 가능한 점을 선택해야 한다

-> 어떻게 그것을 판단하는가?

-> 최선의 로직이 무엇인가?

-> 점을 선택하고, 그 점이 선택 가능한지 판단한다

-> 그 다음에 전체 가격을 합한다

-> 그 중에서 최소 비용을 구한다

-> 이것을 어떻게 판단하는가?

-> 어떻게 모든 최적의 케이스를 계산하는가?

-> 모든 최적의 케이스를 계산한다는 것이 무엇인가?

-> 한 번 구했다

-> 그 다음 무엇을 해야 하는가?

-> 그 케이스를 취소해야 한다

-> 그리고 다른 케이스를 탐색해야 한다

-> 이것을 어떻게 하는가?

-> 어떻게 선택을 하는가?

-> 선택을 한다는 것이 무엇인가?

-> 

2. 계획

• 전에 비슷한 문제를 알고 있는가?
• 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
• 비슷한 문제를 풀어본 적이 있다면 그 것을 활용할 수 있는가?
• 만약 문제를 풀 수 없다면 문제를 더 단순하게 하기 위해서 주어진 조건을 버려보아라
• 주어진 자료로부터 유용한 것을 이끌어 낼 수 있는가?
• 자료는 모두 사용했는가?
• 조건을 모두 사용했는가?
• 문제에 포함된 핵심적인 개념은 모두 고려했는가?

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

import java.util.*; 

public class Main {
    
    public static int N;
    public static int[][]map;
    public static boolean[][] visited;
    public static int minSum = Integer.MAX_VALUE;
    
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1}; 
    
    
    public boolean isInside(int x, int y){
        if(0<=x && x<N && 0<=y && y<N){
            return true;
        }else{
            return false;
        }
    }
    
    
    public boolean isSelectable(int x, int y){
         
          if(visited[x][y]){
              return false;
          }else{
              
              for(int i=0; i<4; i++){
                  int nx = x + dx[i];
                  int ny = y + dy[i];
                  if(isInside(nx, ny) && visited[nx][ny] == false){
                      continue;
                  }else{
                      return false;
                  }
                  
              }
              
          }
          
          return true;
        
    }
    
    
    public void visit(int x, int y, boolean value){
        
        if(value){
            visited[x][y] = true;
        }else{
            visited[x][y] = false;
        }
        
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(value){
                visited[nx][ny] = true;
            }else{
                visited[nx][ny] = false;
            }
        }
        
    }
    
    public int calculate(){
        
        int sum = 0;
        
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(visited[i][j]){
                    sum += map[i][j];
                }
            }
        }
        
        return sum; 
        
    }
    
    
    
    public void DFS(int cnt){
        
        if(cnt == 3){
            int sum = calculate();
            minSum = Math.min(minSum, sum); 
            return; 
        }
        
        
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(isSelectable(i,j)){
                    visit(i, j, true);
                    DFS(cnt+1);
                    visit(i, j, false);
                }
            }
        }
        
        
    }
    
    
    
    
    public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      Main T = new Main();
      
      N = sc.nextInt();
      map = new int[N][N];
      visited = new boolean[N][N];
      
      
      for(int i=0; i<N; i++){
          for(int j=0; j<N; j++){
              int num = sc.nextInt();
              map[i][j] = num;
          }
      }
      
      
      T.DFS(0);
      
      
      System.out.println(minSum); 
      
      
    }
}

4. 반성

• 문제를 다른 방식으로 해결할 수 있는가?
• 결과나 방법을 어떤 다른 문제에 활용할 수 있는가?
• 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?
• 어떻게 하면 더 효과적으로 문제를 해결할 수 있는가?

- 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?

-> 순열이 아닌, 조합의 케이스로 어떻게 구할 수 있을까?

-> 이 문제를 고려해야 한다

-> 왜냐하면 시간 복잡도를 줄여야 하는 케이스가 있을 수 있으므로