[백준/JAVA] 14620번: 꽃길

📖 문제

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

 

 

 

 

💡  풀이 방식

• 브루트포스 + 백트래킹

1. 격자를 입력받는다.

2. 완전탐색으로 모든 점을 확인한다. 해당 지점에서 꽃을 심을 수 있는 경우, 해당 자리와 상하좌우 자리에 대해 꽃을 심어보고, 뽑은 갯수를 +1하고, 비용을 더한 후 재귀호출한다. 그리고 다음 탐색을 위해 해당 자리와 상하좌우 자리에 대해 값을 초기화한다.

 

 

 

[x행 y열 위치에서 꽃을 심을 수 있는지 확인하는 함수 :  boolean isPossible(int x, int y)]

꽃을 심을 수 있는 조건

 - 방문한 적 없어야 함

 - 4방향 탐색 시

     - 꽃잎이 배열 화단 범위를 벗어나선 안 됨

     - 꽃잎 자리에 다른 꽃이 핀 경우(visited[nx][ny] == true)도 꽃을 심을 수 없음

 

[꽃 심고 비용 계산하는 메소드]

- 해당 자리와 해당 자리의 상하좌우 값을 모두 더한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int N;
    static int[][] board;
    static boolean[][] visited;
    
    static int answer = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        board = new int[N][N];
        visited = new boolean[N][N];
        
        for(int i = 0 ; i < N ; i++) {
            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);
    }
   
    private static void dfs(int cnt, int sum) {
        // 꽃 3개 심었다면, 최소 비용 갱신
        if(cnt == 3) {
            answer = Math.min(answer, sum);
            return;
        }
       
        // 모든 화단 탐색
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                // (i,j)에 꽃을 심을 수 있는 경우
                if(isPossible(i,j)) {
                    int tmpSum = getSum(i, j);
                   
                    // 꽃 심은 자리 & 상하좌우 방문처리
                    visited[i][j] = true;
                    for(int d = 0 ; d < 4 ; d++) {
                        int nx = i + dx[d];
                        int ny = j + dy[d];
                        
                        visited[nx][ny] = true;
                    }
                   
                    dfs(cnt + 1, sum + tmpSum);
                    
                    // 꽃 심은 자리 & 상하좌우 초기화
                    visited[i][j] = false;
                    for(int d = 0 ; d < 4 ; d++) {
                        int nx = i + dx[d];
                        int ny = j + dy[d];
                       
                        visited[nx][ny] = false;
                    }
                }
            }
        }
    }
   
    // x행 y열에 꽃을 심을 수 있는지 판별하는 메소드
    private static boolean isPossible(int x, int y) {
        if(visited[x][y])   return false;
       
        for(int d = 0 ; d < 4 ; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            
            if(nx < 0 || nx >= N || ny < 0 || ny >= N)  return false;
            if(visited[nx][ny]) return false;
        }
       
       return true;
    }
   
    // x행 y열에 꽃을 심었을 때의 비용 계산하는 메소드
    private static int getSum(int x, int y) {
        int sum = board[x][y];
        
        for(int d = 0 ; d < 4 ; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            
            sum += board[nx][ny];
        }
        
        return sum;
    }
}

 

 

➕ 다른 풀이 방식

- 브루트포스 말고 내가 꽃술이 생겨날 수 있는 위치를 리스트에 저장해서 활용하고자 했던 방식이 비슷하시다!

[백준 Java]14620 꽃길

 

 

---

💦 어려웠던 점

- "어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다" 이 처리를 하는 부분이 좀 헷갈려서 시간을 오래 잡았다,

- 브루트포스 안 하고 0이 아닌 점에 대해 3개를 조합해서 뽑고, 꽃을 심기 위한 최소 비용을 출력하려고 했었다. (그리고 해결하지 못 했닿)

 

 

🧐 새로 알게 된 내용

- 브루트포스하면서 백트래킹하는 방법 다시 상기시키기,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

 

[백준_14620번] 꽃길