백준 - 소문난 칠공주

문제

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

풀이

처음에는 단순하게 한 지점에서 dfs를 하여 답을 구하려 했으나 중복되는 경우를 판단하기가 어려웠다. 5x5 배열을 1부터 25까지 수를 갖는 1차원 배열로 생각하고 7개의 수를 뽑는 조합으로 생각한 다음, 이다솜 파가 4명 이상인지와 7개의 수가 인접하여 있는지 판단하여 답을 구할 수 있다.

유의할 점

DFS를 활용한 2차원 배열에서 특정 요소들이 인접하여 있는지 확인
2차원 배열을 1차원의 연속된 수로 생각하고 조합을 이용한 풀이

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Main {
    static int N=5;
    static char[][] people;
    static int answer= 0;
    static int[][] map;
    static int[] result = new int[7];
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0,-1, 0, 1};
    static boolean[][] visited2;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        people = new char[5][5]; //주어진 배열 저장
        map = new int[5][5];
        for (int i = 0; i < N; i++) {
            people[i] = br.readLine().toCharArray();
        }

        dfs(0,0);
        System.out.println(answer);
    }
    static void dfs(int len, int index){
        if(len ==7 ){
            if(countS() && checkAdj()) answer++;
            return;
        }
        for(int i=index; i<25; i++) {
            result[len] = i;
            map[i/5][i%5] = 1; //인접 여부 확인
            dfs(len + 1, i + 1);
            map[i/5][i%5]=0; 
        }
    }
    static boolean checkAdj( ){ //인접 여부 확인

        visited2 = new boolean[5][5];
        Queue<int[]> q = new LinkedList<>();
        for(int i=0; i<5; i++){
            for (int j = 0; j < 5; j++) {
                    int count =0;
                if(map[i][j]==1) {
                    q.add(new int[]{i, j});
                    visited2[i][j]  = true;
                }
                while (!q.isEmpty()) {
                    int[] pos = q.poll();

                    for (int k = 0; k < 4; k++) {
                        int nx = pos[0] + dx[k];
                        int ny = pos[1] + dy[k];

                        if(nx<0 || ny<0 || nx>=5 || ny>=5) continue;
                        if(visited2[nx][ny] || map[nx][ny]==0) continue;
                        visited2[nx][ny] = true;
                        q.add(new int[]{nx, ny});
                    }
                    count++;
                }
                if(count == 7 ) return true;
            }
        }
        return false;
    }
    static boolean countS (){ //이다솜파 인원 확인
        int count= 0;
        for(int i=0; i<result.length; i++){
            int x= result[i]/5;
            int y= result[i]%5;
            if(people[x][y] == 'S')  count++;
        }
        if(count>=4) return true;
        return false;
    }

}