[백준] Silver II. 꽃길

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

 

문제 유형

• 브루트포스
• 백트래킹

 

코드 

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

public class boj14620 {
    static int n;
    static int [][] board;
    static boolean[][] visited;
    static int[] dx = {1, 0, -1, 0, 0};
    static int[] dy = {0, 1, 0, -1, 0};
    static int res = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        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(res);
    }

    public static void dfs(int sum, int cnt) {
        if (cnt == 3) {
            res = Math.min(res, sum);
            return;
        }

        for(int i = 1; i < n - 1; i++){
            for(int j = 1; j < n - 1; j++){
                int tmp = 0;
                if (!visited[i][j] && check(i,j)) {
                    for(int dir = 0; dir < 5; dir++){
                        int nx = i + dx[dir];
                        int ny = j + dy[dir];
                        visited[nx][ny] = true;
                        tmp += board[nx][ny];
                    }
                    dfs(sum + tmp, cnt + 1);
                    for(int dir = 0; dir < 5; dir++){
                        int nx = i + dx[dir];
                        int ny = j + dy[dir];
                        visited[nx][ny] = false;
                    }
                }
            }
        }
    }

    public static boolean check(int i, int j) { // 현재 지점과 동서남북 중 하나라도 방문되어있다면 false를 리턴
        for(int dir = 0; dir < 5; dir++) {
            int nx = i + dx[dir];
            int ny = j + dy[dir];
            if (visited[nx][ny]) return false;
        }
        return true;
    }
}

 

회고

 

백트래킹 문제를 오랜만에 풀었더니 감을 다 잃은 것 같다. 

 

문제에서 서로 다른 씨앗을 세 개를 배치할 수 있고, 꽃이 피었을 때 다른 꽃과 닿으면 안된다.

-> 씨앗의 좌표의 동서남북을 체크하고, 해당 동서남북의 방문 여부를 체크해줘야 한다.

 

나의 로직은 이렇다.

1. (0,0)에서부터 백트래킹 탐색을 진행한다.

2. 1 ~ n-2까지 탐색을 진행하는데, 이 범위인 이유는 씨앗이 가장자리에 위치할 수 없기 때문에 범위를 이렇게 잡아놨다.

3. 해당 좌표가 방문되지 않았고, 동서남북 또한 방문되지 않은 경우에만 for문을 타게 해준다.

4. 해당 경우인 경우, 해당 좌표와 동서남북 좌표 모두 방문처리 해준다.

5. 재귀를 돌면서, cnt를 1 증가시켜주고 sum에는 현재와 동서남북의 비용을 모두 더해준다.

6. cnt가 3이 되는 경우, 재귀 종료조건으로 빠지는데 이 때 sum의 최솟값을 매번 갱신해준다.

7. 재귀가 종료된 경우, 해당 좌표와 동서남북 좌표 모두 방문처리를 초기화해서 모든 경우의 수를 찾을 수 있게 한다.