[JAVA 15] 1941. 칠공주

 

1941. 칠공주 (G3)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2  초	256  MB	14973	8066	5223	51.810 %

 

문제

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

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

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

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

입력

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

출력

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

 

---

 

summary

 

‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 구하기

 

• 7명의 여학생들로 구성
• 서로 가로나 세로로 반드시 인접
• 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함

 

strategy

완전 탐색 (N = 5) 은 맞다. 근데 모든 경우의 수를 찾아야 하는 것이기 때문에 시간 초과가 난다. 조합을 같이 활용해야 한다. (25C7 = 480700)

 

• 7명을 선택한다 (comb()), 방문표시(boolean visited[])
• 7명을 기록한다 (int team[])
• 4명이상인지 확인한다. (check)
• 모두 붙어있는지 확인한다. (Queue), 방문표시(booelan select[] true 가 선택된 자리)

 

note

• 5*5 행렬

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

public class Main {

    static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    static char[][] board = new char[5][5];
    static int[] team = new int[7]; // 사람(좌석) 기록
    static boolean[] visited = new boolean[25]; // 사람(좌석) 방문 여부 기록
    
    static int result = 0;
    
    public static void main(String[] args) throws IOException {

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

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

        comb(0, 0);

        System.out.println(result);
    }

    /* 25명 중 7명 조합 */
    public static void comb(int cnt, int start) { 
        if(cnt == 7) {
            if(check()) result++;
            return; 
        }

        for(int i = start; i < 25; i++) { 
            visited[i] = true;
            team[cnt] = i; 
            comb(cnt + 1, i + 1);
            visited[i] = false;
        }
    }

    public static boolean check() {
        // team 인원 중 4명이 임도연파인지 체크
        int Y = 0;
        for(int person : team) {
            if(board[person/5][person%5] == 'Y') Y++;
        }
        if(Y >= 4) return false; // 종료

        /* 좌석이 붙어 있는지 확인 */
        boolean[][] select = new boolean[5][5]; 
        for(int person : team) { // BFS 방문 처리용 초기설정
            select[person/5][person%5] = true;
        }

        Queue<Integer> q = new ArrayDeque<>();
        q.offer(team[0]);
        select[team[0]/5][team[0]%5] = false; 

        int sum = 1;
        while(!q.isEmpty()) {
            int current = q.poll();

            for(int[] d : dir) { // 4방 체크
                int mx = current / 5 + d[0];
                int my = current % 5 + d[1];

                if(mx < 0 || mx >= 5 || my < 0 || my >= 5) continue;
                if(select[mx][my] == false) continue;

                select[mx][my] = false;
                q.offer(mx * 5 + my);
                sum++;
            }
        }

        if(sum == 7) return true; 
        else return false;
    }
}

 

 

문제	결과	메모리	시간	언어코드	길이
1941	맞았습니다!!	145388 KB	320 ms	Java 11 / 수정	2261

 

MEMO

- 좌석 위치는 2차행렬인데, 기록을 1차행렬로 하는 방식 익혀둬야 겠다. (몫이 행, 나머지가 열)

- 순열과 조합 한번 훑어야겠다.

 

https://velog.io/@jihun333/백준1941-소문난-칠공주자바