백준 1941 - 소문난 칠공주(Java)

장준혁·2024년 4월 13일

Java coding test

coding-test

목록 보기

13/21

🔍 문제

💻 제출

📌 입력

📌 출력

🤔 생각

생각해야 할 조건이 몇 가지 존재한다.

연속되어 있는 여학생 7명을 선정 해야한다.
선정할때 '임도연파'가 4명이상 포함 되어 있을 수 없다.

7명의 학생을 선정 할 때는

반복문 을 사용 한 자리 선정 ([백준 14502 - 연구소] 에서 사용)
아래 코드는 연구소 문제 기준으로 작성 된 코드


if (depth == 3) {
            bfs(); //벽이 완성 된 상태의 바이러스 안전지대 확인
            return;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) { //벽을 세울 수 있는 빈 공간 이라면
                    map[i][j] = 1; //현재 위치에 벽을 세우고
                    dfs(depth + 1); //depth 1 추가 후 재귀
                    map[i][j] = 0; //현재 위치를 다시 빈공간으로 복귀
                    //이어서 반복분
                }
            }
        }

2차원 배열을 1차원으로 나열하여 계산


if (pY >= 4) { //임도연 파가 4명 이상이면 return
            return;
        }

        if (num == 7) { //이다솜 파가 4명 이상인 상태
            checkLinked(start - 1);
        } else {
            for (int i = start; i < (SIZE * SIZE); i++) {
                visited[i / SIZE][i % SIZE] = true;
                getPrincess(num + 1, map[i / SIZE][i % SIZE] == 'Y' ? pY + 1 : pY, i+1);
                visited[i / SIZE][i % SIZE] = false;
            }
        }

2차원 배열을 1차원 배열로 위 그림과 같이 표현 할 수 있고 가로 길이(M)로 나누게 된다면 2차원의 index를 구할 수 있다.

📝 코드


import java.io.*;
import java.util.*;

public class Main {
    static final int SIZE = 5;
    static char[][] map;
    static boolean[][] visited;
    static boolean[][] bfsVisited;
    static int[] dx = {0, 1, 0, -1}; //동 남 서 북
    static int[] dy = {1, 0, -1, 0}; //동 남 서 북
    static long result = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        map = new char[SIZE][SIZE];
        visited = new boolean[SIZE][SIZE];

        for (int i = 0; i < SIZE; i++) {
            String line = br.readLine();
            map[i] = line.toCharArray();
        }

        getPrincess(0, 0,0);

        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }

    static void getPrincess(int num, int pY, int start) {
        if (pY >= 4) { //임도연 파가 4명 이상이면 return
            return;
        }

        if (num == 7) { //이다솜 파가 4명 이상인 상태
            checkLinked(start - 1);
        } else {
            for (int i = start; i < (SIZE * SIZE); i++) {
                visited[i / SIZE][i % SIZE] = true;
                getPrincess(num + 1, map[i / SIZE][i % SIZE] == 'Y' ? pY + 1 : pY, i+1);
                visited[i / SIZE][i % SIZE] = false;
            }
        }
    }

    static void checkLinked(int start) {
        bfsVisited = new boolean[SIZE][SIZE];

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{start / SIZE, start % SIZE});

        bfsVisited[start / SIZE][start % SIZE] = true;
        int cnt = 1;

        while (!q.isEmpty()) {
            int size = q.size();

            for (int s = 0; s < size; s++) {
                int[] poll = q.poll();
                int x = poll[0];
                int y = poll[1];

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

                    if (0 <= nx && nx < SIZE && 0 <= ny && ny < SIZE) {
                        if (visited[nx][ny] == true && bfsVisited[nx][ny] == false){
                            q.offer(new int[] {nx,ny});
                            cnt++;
                            bfsVisited[nx][ny] = true;
                        }
                    }
                }

            }
        }

        if (cnt == 7){
            result++;
        }
    }
}

7명의 여학생을 배정하고 연속되어 있는지를 확인 할 때는 visited 배열을 사용했는데
해당 배열만으로 진행한다면 큐에 데이터를 넣고 꺼내는 과정에서 탐색했던 부분을 반복할 우려가 있다.
따라서 진행했던 부분을 중복하여 탐색하지 않기 위해서 추가 배열 bfsVisited를 선언해서 진행해 주었다.

연속 여부를 체크하는 BFS 탐색이 끝난다면 cnt를 계산 해주는데 cnt를 연속되어 있는 학생의 숫자이다.
cnt == 7이면 칠공주가 완성된 것이다.