[JAVA] 백준 1941 - 소문난 칠공주

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

 

 

언뜻 보면 쉬워보였는데, 순수 dfs로 풀게되면 풀기 매우 까다롭다

 

1. 25C7로 25개의 좌표중에 7개를 고른 후, 

2. S의 수가 4 이상인 좌표만 추린다.

3. 그 좌표들을 dfs로 탐색하여 연결되어있는지 확인한다.

 

이정도인데,

 

1번은 조합을 구하는 dfs로 구하면 쉽게 구할수있고,

2번도 조건문으로 쉽게 구할수있다.

3번은 구현하면서 조금 해멨는데 연결만되어있는지 확인하기위해선 visited를 백트래킹할 필요없다는것을 생각하지못하였다.

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {


    static int[][] map = new int[5][5];
    static boolean[][] visited;
    static boolean[][] visited2 = new boolean[5][5];
    static ArrayList<Point> list = new ArrayList<>();
    static int ans;
    static int count;
    static int startX;
    static int startY;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 5; i++) {
            String[] lines = br.readLine().split("");
            for (int j = 0; j < 5; j++) {
                int ele = lines[j].equals("Y") ? 0 : 1;
                map[i][j] = ele;
                list.add(new Point(i, j));
            }
        }
        visited = new boolean[5][5];
        dfs(0, 0, 0);
        System.out.println(ans);


    }

    static void dfs(int depth, int total, int S) {
        if (total == 7 && S >= 4) {
            count = 1;
            visited2 = new boolean[5][5];
            visited2[startX][startY] = true;
            dfs2(startX,startY);
            if(count == 7) {
                ans++;
            }
            return;
        }
        for (int i = depth; i < 25; i++) {
            Point p = list.get(i);
            visited[p.x][p.y] = true;
            int c = map[p.x][p.y] == 1 ? S + 1 : S;
            startX = p.x;
            startY = p.y;
            dfs(i + 1, total + 1, c);
            visited[p.x][p.y] = false;
        }


    }

    static void dfs2(int x , int y){

        for(int i = 0 ; i < 4 ; i++){
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if(nextX < 0 || nextX >= 5 || nextY < 0 || nextY >= 5) continue;
            if(!visited[nextX][nextY]) continue;
            if(visited2[nextX][nextY]) continue;

            count++;
            visited2[nextX][nextY] = true;
            dfs2(nextX, nextY);
        }
    }

}

class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}