백준 - 소문난 칠공주(JAVA)

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

1941번: 소문난 칠공주

문제설명

문제를 처음 보면 단순한 DFS/BFS 문제로 느껴진다. 그러나 단순 탐색으로 찾는다면 많은

반례들이 있다. 예를 들어 십자가 모양으로 있는 TK를 통과하진 못한다.

사실 5x5 배열에 제한시간이 2초라는 것은 단순 탐색으로는 풀 수 없다는 걸 뜻한다.

그러므로 5x5 = 25개의 학생중에 7명을 뽑는다고 생각해야한다.

알고리즘

1. 25명의 학생중 7명을 뽑는다.

 

2. 뽑은 학생들중 2가지를 체크한다. 뽑힌 학생들이 인접했는지와 '이다솜파'가 우위를 정했는지 이다.

 

비트 마스킹으로 풀 수 도 있다. 모든 경로에 대해 다 따로 check 한다. 빠르지만 복잡하다.

 

1. 기존 DFS 방식으로 푸는 대신 check 배열을 비트마스킹한다.

 

2. 위치를 비트로 찾고 check를 통해 경로의 중복을 확인한다.

주의사항

1. 일차원 배열로 표시하려면 y 좌표는 /5 x좌표는 %5가 된다.

구현 코드

public class Main_소문난칠공주 {

    static char map[][];
    static boolean check[];
    static int temp[];
    static int dir[][] = {{1,0},{-1,0},{0,-1},{0,1}};
    static int result;
    public static void main(String[] args) throws IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        map = new char[5][5];
        check = new boolean[25];
        temp = new int[7];
        for (int i = 0; i < 5; i++) {
            String s = in.readLine();
            for (int j = 0; j < 5; j++) {
                map[i][j] = s.charAt(j);
            }
        }
        result = 0;
        DFS(0,0); //좌표,카운트,s개수,t개수
        System.out.println(result);
    }

    private static void DFS(int cnt,int idx) {
        if(cnt == 7)
        {
            if(adj() && che())
                result++;
            return;
        }
        for (int k = idx; k < 25; k++) {
            //7개를 뽑는다.
            // 7개중 y가 4개이상이면 안된다.
            // 7개를 좌표로 맵핑하여 인접한지 확인
            if(!check[k])
            {
                check[k] = true;
                temp[cnt] = k;
                DFS(cnt+1,k);
                check[k] = false;
            }
        }
    }

    private static boolean che() { //우위를 정했는지에 대한 체크함수
        int s_cnt=0;
        for (int i = 0; i < 25; i++) {
            if(check[i])
            {
                int y = i/5;
                int x = i%5;
                if(map[y][x] == 'S')
                    s_cnt++;
            }
            if(s_cnt >=4)
                return true;
        }
        return false;
    }

    private static boolean adj() { //bfs를 이용한다.
        int id=0;
        for (int i = 0; i < 25; i++) {
            if(check[i])
            {
                id=i;
                break;
            }

        }
        LinkedList<int []> queue = new LinkedList<int[]>();
        queue.offer(new int[] {id/5,id%5}); //암거나 하나 넣음
        boolean adj_check[][] = new boolean[5][5];
        adj_check[id/5][id%5] = true;
        int cnt = 1;
        while(!queue.isEmpty())
        {
            int temp1[] = queue.poll();
            int y = temp1[0];
            int x = temp1[1];
            for (int i = 0; i < 4; i++) {
                int ny = y+dir[i][0];
                int nx = x+dir[i][1];
                if(ny > -1 && nx>-1 && nx < 5 && ny < 5 && check[ny*5+nx] && !adj_check[ny][nx])
                {
                    adj_check[ny][nx] = true;
                    queue.offer(new int[] {ny,nx});
                    cnt++;
                }
            }
        }
        if(cnt == 7)
            return true;
        else 
            return false;
    }
}