105. 소문난 칠공주 (백준 1941) [JAVA]

문제

문제 링크 : https://www.acmicpc.net/problem/1941

문제

총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다.

위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.

1. 이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.
2. 강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.
3. 화합과 번영을 위해, 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다.
4. 그러나 생존을 위해, ‘이다솜파’가 반드시 우위를 점해야 한다. 따라서 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.

여학생반의 자리 배치도가 주어졌을 때, ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 구하는 프로그램을 작성하시오.

입력

'S'(이다‘솜’파의 학생을 나타냄) 또는 'Y'(임도‘연’파의 학생을 나타냄)을 값으로 갖는 5*5 행렬이 공백 없이 첫째 줄부터 다섯 줄에 걸쳐 주어진다.

출력

첫째 줄에 ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 출력한다.

 

풀이

그냥 DFS나 BFS를 사용해서 풀면 풀기 어렵다.

왜냐하면 예제와 같이 T모양 같은 부분이 안되기 때문.

어차피 5*5로 크기는 고정이고, 안에 Y나 S의 개수와는 상관없이 시간복잡도가 고정이므로 모든 가짓수를 고려하기로 생각했다.

1. 조합을 통해 (25C7) 모든 경우의 수를 뽑아낸다.
2. 노드들이 이어져있는지 확인한다
3. S가 4개이상인지 확인한다.

일단 조합을 통해 0~24중 7개의 숫자를 뽑아낸다.

이후 BFS를 통해 노드들이 이어져 있는지 확인한다.

만약 노드들이 인접해있다면, 어느 노드에서 시작하더라도 7개의 노드 모두 방문하게 될 것이다.

이때 숫자 -> 좌표로 변환하기 쉽게 하기 위해 0~24에 대응되는 X, Y 좌표는 미리 계산해둔다.

인접 노드를 탐색할 때, 굳이 모든 맵을 방문할 필요 없이

0번노드 (시작으로 고정)을 두고 -> 나머지 6개의 노드만 계속 검사하면 될 것이다.

그리고 S의 개수를 세어주면 된다.

 

코드

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    //파벌
    static char[][] map = new char[5][5];

    static int[] moveX = {1,-1,0,0};
    static int[] moveY = {0,0,1,-1};
    static int[] combX = new int[25];
    static int[] combY = new int[25];

    //연속해서 7개->S가 적어도 4개
    //DFS, BFS를 사용하면 T모양 같은게 안됨
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for(int i=0; i<5; i++){
            map[i] = br.readLine().toCharArray();
        }

        //좌표화
        for(int i=0; i<25; i++){
            combX[i] = i % 5;
            combY[i] = i / 5;
        }

        Combination(new int[7], 0,0,7);
        System.out.println(answer);
    }

    //25개중 7개 뽑기
    public static void Combination(int[] combination, int index, int count, int left){

        if(left == 0){
            BFS(combination);
            return;
        }

        if(count == 25) return;

        combination[index] = count;
        Combination(combination,index+1, count+1, left-1);
        Combination(combination,index,count+1,left);
    }

    public static void BFS(int[] comb){

        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[7];

        q.add(comb[0]);
        int count = 1, countS = 0;

        while (!q.isEmpty()){
            int cur = q.poll();
            if(map[combY[cur]][combX[cur]] == 'S') countS++;

            for(int i=0; i<4; i++){
                for(int a=1; a<7; a++){

                    if(!visited[a] && combX[cur]+moveX[i] == combX[comb[a]] && combY[cur]+ moveY[i] == combY[comb[a]]){
                        visited[a] = true;
                        q.add(comb[a]);
                        count++;
                    }

                }
            }

        }
        if(count == 7){
            if(countS >= 4){
                answer++;
            }
        }
    }
}

 

결과