Skip to main content

1941 - 소문난 칠공주

info
  • 문제 보기: 1941 - 소문난 칠공주
  • 소요 시간: 54분 58초
  • 풀이 언어: java
  • 체감 난이도: 3️⃣~4️⃣ (3.3)
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

dfs bfs


풀이 코드​

info
  • 메모리: 103044 KB
  • 시간: 560 ms
import java.io.*;
import java.util.*;

public class Main
{
    static int[][] table = new int[5][5];
    static boolean[] visited = new boolean[25];
    static int[] selected = new int[7];
    static int[] dy = {-1, 0, 0, 1};
    static int[] dx = {0, -1, 1, 0};
    
    public static int dfs(int idx, int depth) {
        if (depth == 7) return bfs() ? 1 : 0;
        
        int res = 0;
        for (int i = idx+1; i < 25; ++i) {
            if (!visited[i]) {
                visited[i] = true;
                selected[depth] = i;
                res += dfs(i, depth+1);
                selected[depth] = -1;
                visited[i] = false;
            }
        }
        
        return res;
    }
    
    public static boolean bfs() {
        Deque<int[]> q = new ArrayDeque<>();
        boolean[] joined = new boolean[7]; // visited for 'selected'
        
        int yimCnt = 0;
        int somCnt = 0;
        
        int y = selected[0] / 5;
        int x = selected[0] % 5;
        q.add(new int[]{y, x});
        joined[0] = true;
        if (table[y][x] == 0) ++yimCnt; else ++somCnt;
        
        while (!q.isEmpty()) {
            int[] pos = q.pop();
            for (int d = 0; d < 4; ++d) {
                int ny = pos[0] + dy[d];
                int nx = pos[1] + dx[d];
                
                if (ny < 0 || 4 < ny || nx < 0 || 4 < nx) continue; // out of bound
                
                int sdx = 0; // find index of adj value in selected: 0으로 두면 어차피 밑에서 continue 처리됨
                for (int s = 0; s < 7; ++s)
                    if (selected[s] == ny*5+nx) sdx = s;
                    
                if (joined[sdx]) continue; // target value has already joined
                joined[sdx] = true; // else join
                
                q.add(new int[]{ny, nx});
                
                if (table[ny][nx] == 0) ++yimCnt; else ++somCnt;
                if (3 < yimCnt) return false; // 생존 불가
            }
        }
        
        return (yimCnt + somCnt == 7) ? true : false;
    }
    
    public static void main (String[] args) throws IOException {
        input();
        
        int ans = 0;
        for (int i = 0; i < 19; ++i) { // 0 ~ 25-7+1
            visited[i] = true;
            selected[0] = i;
            ans += dfs(i, 1);
            selected[0] = -1;
            visited[i] = false;
        }
        
        System.out.println(ans);
    }
    
    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        for (int i = 0; i < 5; ++i) {
            char[] line = br.readLine().toCharArray();
            for (int j = 0; j < 5; ++j) {
                table[i][j] = line[j] == 'S' ? 1 : 0;
            }
        }
    }
}

풀이 해설​

로직은 크게 3단계를 거친다.

  1. 5*5 = 25칸 중에 중복 없이, 순서 고려하지 않고 7칸을 뽑는다. 즉 25C7_{25}C_{7}.
  2. 뽑힌 7칸의 구성이 조건에 맞는지 판단하고, 맞으면 카운팅한다.
  3. 카운팅 총합을 출력한다.

여기서 1번은 dfs, 2번은 bfs를 사용했다.


📌 조건에 맞는 구성인지 검사​

조건은 다음의 2가지를 만족해야 한다.

  1. 임도연파의 수가 4명 이상이면 안된다.
  2. 모든 구성원들이 인접하게 연결되어야 한다. 인접의 정의는 4방향 기준이다.

boolean[] joined = new boolean[7]; // visited for 'selected'
int yimCnt = 0;
int somCnt = 0;

따라서 이 모든 조건을 카운터 변수 2개로 판단했다.

bfs를 돌리다가 임도연파의 카운터 수가 4 이상이 되는 순간엔 return false로 컷해버리면 되고,

1번 조건은 만족했지만 인접하지 않은 칸이 있어 bfs를 끝까지 수행했음에도 모든 칸을 방문하지 못한 경우가 있기에

이를 고려하여 이다솜파도 같이 카운트하고, bfs 종료시 두 카운터 합이 7이 되는지를 검사한다.

joined가 selected의 bfs 방문 여부 체크하는 일종의 visited 배열이어서, 이걸 스캔해서 판단해도 되지만 좀 멋이 떨어진다(?)


메모​

  • 처음에 7개를 어떻게 선택할지에 대한 발상만 좀 고민스럽고, 구현은 매우 수월했음