링크

1941 소문난 칠공주

문제

풀이

이 문제는 풀다가 틀렸다고 떠서 뭐가 문제지 하면서 반례를 찾아봤다. 처음에 모든 경우에 bfs를 통해 탐색하면서 풀었지만 이렇게 풀면 틀렸다고 나온다. 그 이유는

이 경우는 bfs로 탐새갛면 절대 못푼다(십자가모양)
그래서 찾아본 풀이는

위의 좌표를 활용하여 랜덤으로 7개를 뽑아버려서 이어져있는지 체크하는 방식으로 풀었다.
조합을 사용하면 25C7로 480700의 조합 갯수가 나온다.

1. 0~24까지 번호를 랜덤으로 7개 뽑는다.
2. bfs를 통해 이어져있는지 확인한다.
3. S가 Y보다 많은지 체크한다.

대략 이 순서로 풀었다

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public static int[] dx = {1, 0, -1, 0};
    public static int[] dy = {0, 1, 0, -1};
    //5 * 5 좌표
    public static int[] mapDx = new int[25];
    public static int[] mapDy = new int[25];

    public static String[][] map = new String[5][5];
    public static boolean[][] visited = new boolean[5][5];
    public static int count = 0;

    public static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for(int i=0;i<map.length;i++){
            String arr[] = br.readLine().split("");
            for(int j=0;j<arr.length;j++){
                map[i][j] = arr[j];
            }
        }

        for(int i=0;i<25;i++){
            mapDx[i] = i / 5;
            mapDy[i] = i % 5;
//            System.out.println("mapDx[i] = " + mapDx[i] + " mapDy[i] = " + mapDy[i]);
        }

        randomPick(0, 0);
        System.out.println(count);



    }

    //랜덤 조합으로 7개 뽑기
    public static void randomPick(int dept, int lastIdx){
        if(dept == 7){
            //이어져있으면
            if(bfs()){
                int S = 0;
                int Y = 0;

                for(int element : list){
                    int x = mapDx[element];
                    int y = mapDy[element];

                    if(map[x][y].equals("S")){
                        S++;
                    } else{
                        Y++;
                    }
                }

                if(S > Y) count++;
            }
//            System.out.println(list);
            return;
        }

        // 0부터 24까지 랜덤으로 중복되지 않게 7개 뽑기
        for(int i=0;i<25;i++){
            if(!list.contains(i) && i >= lastIdx){
                list.add(i);
                dept+=1;
                randomPick(dept, i);
                dept -= 1;
                list.remove(list.size() - 1);
            }
        }

    }

    //뽑은 조합이 이어져있는지 체크
    public static boolean bfs(){
        visited = new boolean[5][5];
        for(int element : list){
            int newX = mapDx[element];
            int newY = mapDy[element];

            visited[newX][newY] = true;
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.add(mapDx[list.get(0)]);
        queue.add(mapDy[list.get(0)]);

        while(!queue.isEmpty()){
            int x = queue.poll();
            int y = queue.poll();
            visited[x][y] = false;

            for(int i=0;i<4;i++){
                int newX = x + dx[i];
                int newY = y + dy[i];

                if(newX < 0 || newY < 0 || newX >= visited.length || newY >= visited.length) continue;

                if(visited[newX][newY]){
                    queue.add(newX);
                    queue.add(newY);
                }
            }
        }

        for(int i=0;i<visited.length;i++){
            for(int j=0;j<visited.length;j++){
                if(visited[i][j]) return false;
            }
        }


        return true;
    }



}