[백준] 1941번: 소문난 칠공주 - java

나의 코드

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

public class Main {

    static char[][] arr;
    static int[] selected;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        arr = new char[5][5];
        for (int i = 0; i < 5; i++) {
            String s = br.readLine();
            for (int j = 0; j < 5; j++) {
                arr[i][j] = s.charAt(j);
            }
        }

        selected = new int[7];
        combination(0, 0, 0);

        System.out.println(answer);
    }

    /**
     * 조합으로 7명의 학생을 구하고, 해당 경우의 수로 칠공주 규칙을 만족하는지 검사한다.
     *
     * @param idx:    현재 탐색중인 학생 idx (0~24)
     * @param cnt:    지금까지 고른 칠공주 수
     * @param cntLee: 지금까지 고른 칠공주 중 이다솜파의 수
     */
    public static void combination(int idx, int cnt, int cntLee) {

        if (cnt - cntLee > 3)
            return;

        if (cnt == 7) { // 7명의 칠공주를 모두 구한것
            if (cntLee >= 4) { // 이다솜파가 4명 이상 포함되어 있는 경우 공주들이 인접한지 검사하기
                if (check()) {
                    answer++;
                }
            }

            return;
        }

        for (int i = idx; i < 25; i++) {
            selected[cnt] = i;
            combination(i + 1, cnt + 1, arr[i / 5][i % 5] == 'S' ? cntLee + 1 : cntLee);
        }
    }

    /**
     * @return 공주들이 모두 인접한다면 true, 그렇지 않다면 false
     */
    public static boolean check() {
        Queue<Integer> q = new LinkedList<>();
        q.offer(selected[0]);

        HashSet<Integer> hs = new HashSet<>(); // 현재 선택된 공주들의 번호를 저장한 hs
        for (int i = 1; i < 7; i++) {
            hs.add(selected[i]);
        }

        int tmp = 1;
        while (!q.isEmpty()) {
            int now = q.poll();

            for (int i = 0; i < 4; i++) { // 상하좌우에 다른 공주가 인접해있는지 탐색
                int nx = now / 5 + dx[i];
                int ny = now % 5 + dy[i];
                int num = nx * 5 + ny;
                if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && hs.contains(num)) { // 인접한 공주가 있다면
                    q.add(num);
                    hs.remove(num);
                    tmp++;
                }
            }
        }
        if (tmp == 7) {
            return true;
        }
        return false;
    }
}

 

 

조합 + BFS 로 푼 문제!!

 

1. 조합

7명의 여학생 중 이다솜파가 4명 이상인 경우의 수를 조합으로 구한다.

   /**
     * 조합으로 7명의 학생을 구하고, 해당 경우의 수로 칠공주 규칙을 만족하는지 검사한다.
     *
     * @param idx:    현재 탐색중인 학생 idx (0~24)
     * @param cnt:    지금까지 고른 칠공주 수
     * @param cntLee: 지금까지 고른 칠공주 중 이다솜파의 수
     */
    public static void combination(int idx, int cnt, int cntLee) {

        if (cnt - cntLee > 3)
            return;

        if (cnt == 7) { // 7명의 칠공주를 모두 구한것
            if (cntLee >= 4) { // 이다솜파가 4명 이상 포함되어 있는 경우 공주들이 인접한지 검사하기
                if (check()) {
                    answer++;
                }
            }
            return;
        }

        for (int i = idx; i < 25; i++) {
            selected[cnt] = i;
            combination(i + 1, cnt + 1, arr[i / 5][i % 5] == 'S' ? cntLee + 1 : cntLee);
        }
    }

재귀를 통한 조합 구하기

 

i -> 중복을 피하기 위해 재귀호출을 할 때 i+1부터 탐색하도록 한다.

cnt : 지금까지 고른 칠공주 수

cntLee : 지금까지 고른 칠공주 중 이다솜파 수

종료 조건

• 임도연파가 4명이상일 경우 -> 칠공주 규칙에 맞지 않으므로 return
• 7명의 칠공주를 모두 구했을 때, 이다솜파가 4명이상인 경우 -> check() 를 통해 모든 공주들이 인접한지 검사한다.

 

 

2. BFS

     /**
     * @return 공주들이 모두 인접한다면 true, 그렇지 않다면 false
     */
    public static boolean check() {
        Queue<Integer> q = new LinkedList<>();
        q.offer(selected[0]);

        HashSet<Integer> hs = new HashSet<>(); // 현재 선택된 공주들의 번호를 저장한 hs
        for (int i = 1; i < 7; i++) {
            hs.add(selected[i]);
        }

        int tmp = 1;
        while (!q.isEmpty()) {
            int now = q.poll();

            for (int i = 0; i < 4; i++) { // 상하좌우에 다른 공주가 인접해있는지 탐색
                int nx = now / 5 + dx[i];
                int ny = now % 5 + dy[i];
                int num = nx * 5 + ny;
                if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && hs.contains(num)) { // 인접한 공주가 있다면
                    q.add(num);
                    hs.remove(num);
                    tmp++;
                }
            }
        }
        if (tmp == 7) {
            return true;
        }
        return false;
    }

BFS(상하좌우 탐색) 로 공주들이 모두 인접한지 검사하기

 

큐에는 선택한 칠공주 중 임의의 한명을 넣는다. ->   q.offer(selected[0]);

선택한 공주들의 번호를 저장하기 위해 HashSet 을 이용한다. 큐에 넣은 공주를 제외한 공주들의 번호를 넣는다.

for (int i = 1; i < 7; i++) {
            hs.add(selected[i]);
 }

 

큐가 빌때까지 BFS 를 탐색한다. while 문으로 모든 인접한 곳들을 탐색한 후, tmp가 7이라면 공주가 모두 인접함을 뜻한다.

BFS 탐색시, 공주의 상하좌우에 다른 공주가 존재한다면? 인접한 공주를 큐에 넣고, hashset 에서는 제거하며, tmp를 1 증가시킨다. 즉, 큐에는 항상 공주번호만 들어가는 것이다. 큐가 빌때까지 모두 돌았다는 것은 임의의 공주에서 시작해 상하좌우를 탐색하여 연결된 모든 곳을 탐색함을 뜻한다. 이때, 발견한 공주가 총 7명이라면 공주끼리 모두 인접함을 뜻하고, 그렇지 않다면 공주끼리 연결되어 있지 않음을 뜻하는 것이다.

if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && hs.contains(num)) {

// 공주의 상하좌우에 인접한 다른 공주가 있다면
                    q.add(num);
                    hs.remove(num);
                    tmp++;
}