PS/백준

[백준] 14620 꽃길 (Java)

m5n 2024. 10. 13. 13:44

백준 14520 꽃길 (Java)

 

출처

www.acmicpc.net/problem/14620

 

 

유형

브루트포스(완전 탐색), 백트래킹

 

배운점

  • 처음에는 3번의 조건을 모두 검사해야해서 for문을 6번 중첩해야하나 생각을 했음 ㅋㅋ (말도 안되는 소리)
  • 그러다가 백트래킹 방법에 대해서 접함. 

 

  • 백트래킹 (BackTraking)
    • 알고리즘 기법 중 하나로 재귀적으로 문제를 해결하되 현재 재귀를 통해 확인 중인 상태가 제한 조건에 위배가 되는지 판단하고, 해당 상태가 위배되는 경우 해당 상태를 제외하고 다음 단계로 넘어간다 
    • 백트래킹은 주로 DFS 방식으로 구현을 함
  • 구현할 때
    • 모든 경우의 수를 하다보니, 제한조건을 설정하는게 구현할 때 좋을 듯 함
    • 이 문제에서는 꽃이 3개이다 보니 dfs의 depth가 3이 될 때까지 재귀로 구현하도록 하였고 cost도 누적해서 계산을 해야하기 때문에 dfs(int depth, int cost)로 함수를 구현하였음

 

 

느낀점

  • 백트래킹을 구현할 때는 조건 설정부터 생각을 하자 
    • 어떤 조건일 때 실행을 할 것이고 어떤 조건일 때 넘어갈 것인지
    • 재귀가 다시 돌아왔을 때 어떤 로직을 수행할 것인지

 

정리

  • 완전 탐색을 해야한다고 판단이 되면 백트래킹을 고려하고, 이때 조건 설정을 잘 따져보자

 

 

코드

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

public class boj14620 {

    private static int answer = Integer.MAX_VALUE;
    private static int N;
    private static boolean[][] visited;
    private static int[][] ground;
    private static int[] dx = new int[] {-1, 0, 1, 0};
    private static int[] dy = new int[] {0, -1, 0, 1};

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        ground = 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) {
                ground[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0, 0);

        System.out.println(answer);
    }

    private static void dfs(int depth, int sum) {
        if(depth == 3) {
            answer = Math.min(answer, sum);
        }
        else {
            int cost = sum;

            for(int i = 1; i < N-1; ++i) {
                for(int j = 1; j < N-1; ++j) {

                    if(!visited[i][j] && canGrow(i,j)) {
                        cost += cost(i, j);
                        visitCheck(i, j);
                        dfs(depth+1, cost);

                        init(i, j);
                        cost -= cost(i, j);
                    }

                }
            }

        }
    }

    private static boolean canGrow(int x, int y) {
        for(int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(visited[nx][ny]) {
                return false;
            }
        }
        return true;
    }

    private static int cost(int x, int y) {
        int cost = ground[x][y];

        for(int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            cost += ground[nx][ny];
        }

        return cost;
    }

    private static void visitCheck(int x, int y) {
        visited[x][y] = true;

        for(int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            visited[nx][ny] = true;
        }
    }

    private static void init(int x, int y) {
        visited[x][y] = false;

        for(int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            visited[nx][ny] = false;
        }
    }
}

 

 

 

참고