[백준] 1941. 소문난 칠공주

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

 

처음에는 5 X 5 그래프의 각 노드를 시작으로 그래프 탐색을 해서 7명을 모으는 것을 생각했다. 그런데 같은 조합이 여러 번 나올 수 있다. (학생 1 -> 2 -> 3인 조합과 학생 3 -> 2 -> 1의 조합은 같기 때문) 그리고 이때 이미 나온 조합인지 일일이 검사하는 건 매우 비효율적이다.

 

따라서 25명의 학생 중 7명의 학생 조합을 찾고(백트래킹), 이 조합의 학생들이 모두 연속된 자리인지, 그리고 S 값이 더 많은지 확인(bfs)하면 된다.

 

그런데 7명의 학생 조합을 찾을 때 중복된 조합을 생성하면 안된다. (ex, 학생 1 + 2, 학생 2 + 1은 같음) 따라서 5 X 5 배열을 숫자 0 ~ 24로 취급한 후, dfs의 start 매개 변수로 i + 1의 값을 전달하여 중복된 조합이 생성되지 않도록 했다. (dfs 메소드 참고!)

 

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int answer = 0;
    static char[][] map;
    static boolean[][] visited;

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

        map = new char[5][5];
        visited = new boolean[5][5];

        for (int i = 0; i < 5; i++) {
            String str = br.readLine();
            for (int j = 0; j < 5; j++) {
                map[i][j] = str.charAt(j);
            }
        }

        dfs(0, 0);

        System.out.println(answer);
    }

    // 1. 25명 중 7명의 조합 만들기
    public static void dfs(int cnt, int start) {

        if (cnt == 7) {
            if (canAnswer()) { // 2. 7명의 학생이 모두 연속된 자리이면서 S의 수가 더 많은지 확인
                answer++;
            }
            return;
        }

        for (int i = start; i < 25; i++) { // start부터 탐색하여 중복된 조합이 생기지 않도록!
            visited[i / 5][i % 5] = true;
            dfs(cnt + 1, i + 1);
            visited[i / 5][i % 5] = false;
        }
    }

    private static boolean canAnswer() {
        boolean[][] cpyVisited = new boolean[5][5];
        for (int i = 0; i < 5; i++) {
            cpyVisited[i] = visited[i].clone();
        }

        int y = 0, x = 0;
        outer: for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (cpyVisited[i][j]) {
                    y = i;
                    x = j;
                    break outer;
                }
            }
        }

        // bfs
        Queue<Node> que = new LinkedList<>();
        int totalCnt = 1;
        int sCnt = 0;
        if (map[y][x] == 'S') {
            sCnt++;
        }
        que.add(new Node(y, x));
        cpyVisited[y][x] = false; 

        while (!que.isEmpty()) {
            Node now = que.poll();
            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5 || !cpyVisited[ny][nx]) {
                    continue;
                }

                que.add(new Node(ny, nx));
                cpyVisited[ny][nx] = false;
                totalCnt++;
                if (map[ny][nx] == 'S') {
                    sCnt++;
                }
            }
        }

        return totalCnt == 7 && sCnt > (totalCnt - sCnt);
    }

    private static class Node {

        int y, x;

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