[BOJ] 1941. 소문난 칠공주(조합, DFS, BFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

단 4가지 규칙만 잘 지키면 된다.

규칙 1 : 7명의 여학생들로 구성

- 5x5 이차원 배열에서의 조합으로 7칸의 좌표를 선택.

규칙 2 : 7명의 자리는 서로 가로나 세로로 반드시 인접

- 선택된 7칸의 좌표는 모두 인접해야 함.

규칙 3 : 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다.

- 이건 규칙 4에 포함.

규칙 4 : 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함

- 선택된 7칸의 좌표에 '이다솜파'학생이 적어도 4명 이상이 포함

정리해보면,

총 7명의 학생 조합을 뽑는데, 7명중 최소 4명은 '이다솜파'여야 한다.

이 상태에서 이 7명의 학생들이 인접해있는지 확인해보면 된다.

그렇다 사실 말은 쉽다..

코드로 옮겨보자.

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class BOJ1941 {
 
    static int N = 5, res = 0, selected[];
    static char map[][];
    static boolean visited[], adjVisited[];
    static int dx[] = { -1, 0, 1, 0 };
    static int dy[] = { 0, 1, 0, -1 };
    static Queue<Integer> q;
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        map = new char[N][N];
        for (int i = 0; i < N; i++) 
            map[i] = br.readLine().toCharArray();
 
        // 이차원 배열을 일차원 배열로 표현
        visited = new boolean[N*N];
        // 선택된 칠공주
        selected = new int[7];
        
        // 칠공주 조합을 찾으러
        find(0, 0, 0);
        
        System.out.println(res);
    }
 
    public static void find(int idx, int cnt, int cntS) {
        // 7명의 여학생으로 구성,
        if (cnt == 7) {
            // '솜'파 학생이 4명 이상이라면
            if (cntS >= 4) {
                // 인접 확인
                if(checkAdj())
                    res++;
                return;
            }
            // '솜'파가 4명 이상이 아니면 그냥 return..
            return;
        }
        
        for (int i = idx; i < N*N; i++) {
            visited[i] = true;
            
            selected[cnt] = i;
            // '솜'파일 경우,
            if(map[i/N][i%N] == 'S') find(i + 1, cnt + 1, cntS + 1);
            else find(i + 1, cnt + 1, cntS);
            
            visited[i] = false;
        }
    }
    
    public static boolean checkAdj() {
        int cnt = 1;
        adjVisited = new boolean[N*N];
        q = new LinkedList<>();
        // 임의 한 명 위치를 Queue에 넣고
        q.add(selected[0]);
        // 7명이 모두 인접해있는지 확인해보자. 
        while(!q.isEmpty()) {
            int now = q.poll();
            adjVisited[now] = true;
            
            for (int d = 0; d < 4; d++) {
                int xx = (now/N) + dx[d];
                int yy = (now%N) + dy[d];
                // 범위를 벗어나면 pass
                if(xx < 0 || yy < 0 || xx >= N || yy >= N) continue;
                // 이미 확인한 애면 pass
                if(adjVisited[xx*N+yy]) continue;
                // 인접한 앤데 공주가 아니면 pass
                if(!visited[xx*N+yy]) continue;
                // 인접한 애가 같은 공주네?
                cnt++;
                adjVisited[xx*N+yy] = true;
                q.add(xx*N+yy);
            }
        }
        // 임의 한 명 이랑 인접한 공주가 모두 7명이 되면 true
        if(cnt == 7) return true;
        else return false;
    }
}

line 25) 5x5 이차원배열을 5*5 일차원 배열로 표현하였다.

  예를 들어, 일차원배열의 index [13]은 [13/5][13%5] = [2][3] 로 표현할 수 있고

            [2][3]는 일차원배열의 2x5+3 = 13 으로 표현할 수 있다.

line 35~59) 7명의 학생 조합을 뽑는 재귀함수

line 37) 만일 7명의 학생이 뽑혔는데,

line 39) '솜'파 학생이 4명 이상이라면

line 41) 인접했는지 확인하고 인접했다면 카운트해준다.

line 46) '솜'파 학생이 4명 미만이면 더이상 확인할 필요도 없다.

line 49~58) 5x5 이차원배열을 5*5 일차원 배열로 표현했으니까 0 ~ 5*5 까지의 조합을 구할 것이다.

line 50~52) 선택된 학생을 체크하고, 선택 리스트에 넣어주자.

line 54) 선택된 학생이 '솜'파 학생일 경우, '솜'파 학생을 카운트해주는 cntS에 +1 을 해서 넘겨주고

line 55) '솜'파 학생이 아니면 cntS는 그대로 넘겨주자.

line 57) 해당 학생이 선택되었을 경우를 확인했으니, 이제 선택되지 않았을 때를 확인해야하므로 false

line 61~90) 선택된 7명의 학생들이 인접했는지 확인하는 함수

     여기는 흔한 BFS 코드와 유사하다.

line 70) 다만 여기서도 따로 방문 체크를 해주어야 한다. 

line 88) 임의로 선택해서 queue에 넣어줬던 학생이랑 인접한 학생이 모두 7명이 되면 true를 return

* 결코 쉬운(?) 문제는 아닌 것 같다.

조합과 탐색이 합쳐진 나름으로 좋은 문제인것 같다.

처음에 너무 쉽게 접근했다가 좀 많이 틀리긴 했지만... 하핳