백준 1941 소문난 칠공주 - JAVA

1941 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
public class Main {
    private static int count = 0;
    private static char[][] studs = new char[5][5];
    private static int[] selected = new int[7];
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < 5; i++) {
            String input = br.readLine();
            for (int j = 0; j < 5; j++) {
                studs[i][j] = input.charAt(j);
            }
        }
        comb(0, 0, 0);
        bw.write(String.valueOf(count));
        bw.flush();
    }
    private static void comb(int depth, int start, int cntS) {
        if (depth == 7) {
            if (cntS >= 4 && isConnected()) count++;
            return;
        }
        for (int i = start; i < 25; i++) {
            char c = studs[i / 5][i % 5];
            selected[depth] = i;
            comb(depth + 1, i + 1, cntS + (c == 'S' ? 1 : 0));
        }
    }
    private static boolean isConnected() {
        boolean[] visited = new boolean[7];
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(0);
        visited[0] = true;
        int princessCount = 1;
        while(!queue.isEmpty()) {
            int cur = queue.poll();
            int x = selected[cur] / 5;
            int y = selected[cur] % 5;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                int next = nx * 5 + ny;
                if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
                for (int j = 0; j < 7; j++) {
                    if (!visited[j] && selected[j] == next) {
                        visited[j] = true;
                        princessCount++;
                        queue.offer(j);
                    }
                }
            }
        }
        return princessCount == 7;
    }
}

 

알고리즘 설명

---

최근 카카오 코테를 보고 썰려서 기부니가 좋지 않습니다. 너무 거만했던 탓일까요... 꽤 잘 풀 줄 알았는데 아직 갈 길은 먼 것 같습니다.

 

문제 자체는 어렵지 않습니다. 문제에서 말하는 조건은 다음과 같습니다.

 

1. 칠공주 7명은 가로 또는 세로로 인접해 있어야 한다.
2. 칠공주 안에 S(이다솜파) 학생이 최소 4명 이상 포함되어야 한다.

따라서 해결 방법은 다음과 같이 접근할 수 있습니다.

1. 조합으로 7명 선택
   • 25명 중 7명을 선택합니다.
   • 선택된 7명 중 S가 4명 이상인지 확인합니다.
   • 25번 반복하는 방식(row : index / 5, col : index % 5)이나 2중 for문을 사용하는 방식 모두 성능 차이는 거의 없습니다.
2. BFS로 연결 여부 확인
   • 선택된 7명이 가로 또는 세로로 모두 연결되어 있는지 확인합니다.
   • BFS를 사용하여 첫 학생을 기준으로 탐색하며, 모든 선택된 학생을 방문할 수 있는지 체크합니다.
3. 조건을 만족하면 결과를 카운트

조합이 칠공주가 가능한지 확인하기 위해 selected 배열을 매 반복문 마다 변경하는 백트래킹이 핵심이라고 할 수 있습니다.

 

코드 해석

---

먼저 studs[5][5] 배열에 각 학생의 정보를 저장하고, 25명 중 7명을 선택하는 조합을 생성합니다. 선택된 7명을 selected[7] 배열에 기록합니다. 이때, 반복문의 시작 인덱스를 변수로 설정하고, 해당 인덱스 이상부터만 선택가능하도록 하여 동일한 멤버가 순서만 다르게 들어가는 순열이 발생하지 않도록 합니다.

 

현재 선택된 학생 중 S(이다솜파) 학생 수를 cntS에 기록합니다. 7명을 모두 선택했을 때 cntS >= 4인지 확인합니다. 4명 이상이면 연결 여부를 확인하기 위해 isConnected()를 호출합니다.

 

isConnected는 BFS 기반 함수입니다.

선택된 7명을 담은 selected 중 첫 번째 학생의 원소번호를 큐에 넣고 방문 처리합니다. 큐에서 학생의 원소 번호를 꺼내 selected 배열 상의 위치로 변경하고, 상하좌우로 인접한 칸을 탐색합니다. 인접 칸이 선택된 학생 중 하나이면 방문 처리 후 큐에 넣습니다. 모든 큐 탐색이 끝난 후, 연결된 학생 수가 7명인지 확인합니다. 7명이 맞다면 true를 반환해 칠공주를 완성할 수 있는 경우의 개수를 담는 count의 변수값을 증가 시킵니다.