[백준, Java] 1941번, 소문난 칠공주, (조합, BFS, 백트레킹)

문제 링크

1941번: 소문난 칠공주

총 25명의 여학생들로 이러우진 여학생반은 5x5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생의 두각을 나타내...

www.acmicpc.net

주의사항

JAVA를 사용하여 프로그램을 사용하였습니다.
백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

문제 설명

접근 방법

이 문제에 핵심

1. 모든 여학생은 '이다솜파', '임도연파'로 구성되어 있습니다.

2. 7명의 칠공주를 결성할 때, 모두 가로, 세로로 연결되어 있어야 하며, '이다솜파'가 최소 4명 이상 있어야 합니다.

3. 5 × 5 행렬로 여학생들의 정보가 주어질 때 소문난 칠공주를 만드는 경우의 개수를 결과로 출력합니다.

알고리즘 진행 순서.

1. 입력된 정보를 저장합니다.

2. 백트래킹으로 여학생들의 조합을 만든 뒤, 가로,세로 인접한지 BFS을 통해서 탐색합니다.

3. 탐색을 통해 소문난 칠공주 경우의 수를 결과로 출력합니다.

여학생 조합 구하기(백트래킹)

여학생의 조합을 구할 때에는 소문난 칠공주의 조합을 고려해야 합니다.

'이다솜파'가 최소 4명이 있어야 한다

→ 즉, '임도연파'가 4명 이상 있으면 소문난 칠공주를 만들지 못합니다.

'임도연파'의 여학생의 개수를 고려해서 백트래킹으로 여학생의 조합을 만들면 됩니다.

순차적으로 조합을 만들면서, 조합에 포함된 '임도연파'의 여학생 수가 4명 이상이 된다면 해당 탐색을 종료하도록 합니다.

추가적으로 5 × 5 형식의 여학생들이 조합에 포함되었는지 확인하는 것은 2차원 배열을 1차원으로 펼쳐놓은 것으로 진행하였습니다.

(1, 1) 배열의 값은 행렬의 6번째 값(0번째부터 시작)입니다.

위에 내용처럼 해당 내용들을 1차원의 n번째 값으로 표현하면 아래의 점화식을 이용할 수 있습니다.

점화식 : row * 5 + col;

(1, 1) = 1 × 5 + 1 = 6

n번째 값을 row와 col으로 다시 바꾸는 방법

row : n ÷ 5

col : n mod(%) 5

표현할 수 있습니다.

6번째 값

row : 6 ÷ 5 = 1

col : 6 mod(%) 5 = 1

(1, 1)

여학생 인접한지 확인하기(BFS)

인접하다? = 가로, 세로로 연결되어 있다.

조합 임의의 학생을 기준으로 BFS을 통해서 조합의 모든 여학생을 방문할 수 있는지 확인하는 것입니다.

가로, 세로 인접한 학생들을 방문할 때에는 조합에 존재하는지 확인하는 로직이 추가된 BFS으로 확인하시면 됩니다.

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

예제입력 1.

1. 입력된 정보를 저장합니다.

[여학생 5 × 5 배열]

Y	Y	Y	Y	Y
S	Y	S	Y	S
Y	Y	Y	Y	Y
Y	S	Y	S	Y
Y	Y	Y	Y	Y

2. 백트래킹으로 여학생들의 조합을 만든 뒤, 가로,세로 인접한지 BFS을 통해서 탐색합니다.

백트래킹을 통해서 여학생의 조합을 만드는 과정을 진행합니다.

Y	Y	Y	Y	Y
S	Y	S	Y	S
Y	Y	Y	Y	Y
Y	S	Y	S	Y
Y	Y	Y	Y	Y

조합을 만들다가, 위 표처럼 Y의 개수가 4개가 된다면??

소문난 칠공주를 만들 수 없기 때문에 해당 조합 탐색은 종료합니다.

※ 모든 조합의 개수가 매우 많기 때문에 결과가 되는 조합과 연결되지 않는 조합 1개를 탐색하겠습니다.

Y	Y	Y	Y	Y
S	Y	S	Y	S
Y	Y	Y	Y	Y
Y	S	Y	S	Y
Y	Y	Y	Y	Y

Y의 개수 : 3개

S의 개수 : 4개

소문난 칠공주의 조건을 만족하기 때문에 인접한지 BFS으로 탐색합니다.

[보라 : 조합의 포함된 여학생, 빨강 : BFS 방문한 여학생]

Y	Y	Y	Y	Y
S	Y	S	Y	S
Y	Y	Y	Y	Y
Y	S	Y	S	Y
Y	Y	Y	Y	Y

Y	Y	Y	Y	Y
S	Y	S	Y	S
Y	Y	Y	Y	Y
Y	S	Y	S	Y
Y	Y	Y	Y	Y

Y	Y	Y	Y	Y
S	Y	S	Y	S
Y	Y	Y	Y	Y
Y	S	Y	S	Y
Y	Y	Y	Y	Y

...

Y	Y	Y	Y	Y
S	Y	S	Y	S
Y	Y	Y	Y	Y
Y	S	Y	S	Y
Y	Y	Y	Y	Y

모두 인접하기 때문에 해당 경우 소문난 칠공주를 만들 수 있습니다.

Y	Y	Y	Y	Y
S	Y	S	Y	S
Y	Y	Y	Y	Y
Y	S	Y	S	Y
Y	Y	Y	Y	Y

Y의 개수 : 3개

S의 개수 : 4개

소문난 칠공주의 조건을 만족하기 때문에 인접한지 BFS으로 탐색합니다.

[보라 : 조합의 포함된 여학생, 빨강 : BFS 방문한 여학생]

Y	Y	Y	Y	Y
S	Y	S	Y	S
Y	Y	Y	Y	Y
Y	S	Y	S	Y
Y	Y	Y	Y	Y

Y	Y	Y	Y	Y
S	Y	S	Y	S
Y	Y	Y	Y	Y
Y	S	Y	S	Y
Y	Y	Y	Y	Y

...

Y	Y	Y	Y	Y
S	Y	S	Y	S
Y	Y	Y	Y	Y
Y	S	Y	S	Y
Y	Y	Y	Y	Y

모두 인접하기 때문에 해당 경우 소문난 칠공주를 만들 수 있습니다.

Y	Y	Y	Y	Y
S	Y	S	Y	S
Y	Y	Y	Y	Y
Y	S	Y	S	Y
Y	Y	Y	Y	Y

Y의 개수 : 3개

S의 개수 : 4개

소문난 칠공주의 조건을 만족하기 때문에 인접한지 BFS으로 탐색합니다.

[보라 : 조합의 포함된 여학생, 빨강 : BFS 방문한 여학생]

Y	Y	Y	Y	Y
S	Y	S	Y	S
Y	Y	Y	Y	Y
Y	S	Y	S	Y
Y	Y	Y	Y	Y

Y	Y	Y	Y	Y
S	Y	S	Y	S
Y	Y	Y	Y	Y
Y	S	Y	S	Y
Y	Y	Y	Y	Y

Y	Y	Y	Y	Y
S	Y	S	Y	S
Y	Y	Y	Y	Y
Y	S	Y	S	Y
Y	Y	Y	Y	Y

모두 인접하기 않아서 해당 경우 소문난 칠공주를 만들 수 없습니다.

3. 탐색을 통해 소문난 칠공주 경우의 수를 결과로 출력합니다.

탐색으로 얻은 소문난 칠공주의 경우 : 2가지

2 결과로 출력합니다.

BufferedReader를 사용하여 입력되는 정보를 저장합니다.
search를 이용하여 소문난 칠공주 경우의 수를 탐색합니다.
탐색한 소문난 칠공주 경우의 수를 Bufferedwriter 저장합니다.
BufferedWriter에 저장된 결과를 출력합니다.

search함수는 백트래킹을 이용해서 '임도연파'가 4명이상 존재하지 않는 여학생의 조합을 탐색합니다.
bfs함수는 여학생 조합이 서로 상하좌우 인접해서 연결되어 있는지 확인합니다.
inSpace함수는 5 × 5 행렬안에 존재하는지 좌표를 확인하는 함수입니다.

결과코드

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

public class Main {
    //BFS에서 좌표 관련 정보 클래스
    static class Info{
        int r, c;
        public Info(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    //여학생 정보 배열
    static char[][] squre;
    static int result;
    //여학생 조합시, 사용 확인 배열
    static boolean[]  totalVisited;
    //상하좌우 y, x 변경 값
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        squre = new char[5][5];
        totalVisited = new boolean[25];
        //입력되는 여학생 행렬 저장
        for(int i=0;i<5;i++){
            String line = br.readLine();
            for(int j=0;j<5;j++){
                squre[i][j] = line.charAt(j);
            }
        }
        //백트레킹으로 소문난 칠공주 경우의 개수 구하기
        search(0, 0, 0);
        //소문난 칠공주 경우의 개수 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //백트레킹으로 소문난 칠공주에 대한 조합을 구하는 함수
    static void search(int idx, int depth, int yCnt){

        //'임도연파'가 4명 이상일 경우
        if(yCnt >= 4){
            return;
        }

        //조합을 완성시켰을 때
        if(depth == 7){
            int curIdx = idx-1;
            //BFS을 통해서 연결되어 있는지 확인
            if(bfs(curIdx / 5, curIdx % 5)){
                result++;
            }
            return;
        }

        //조합에 다음 여학생 탐색
        for(int i = idx; i<25; i++){
            totalVisited[i] = true;
            //'임도연파'인 경우
            if(squre[i/5][i%5] == 'Y'){
                search(i+1, depth+1, yCnt+1);
            }else{		//'이다솜파'인 경우
                search(i+1, depth+1, yCnt);
            }
            totalVisited[i] = false;
        }
    }
    //BFS을 통해서 조합 내 여학생들이 연결되어 있는지 확인하는 함수
    static boolean bfs(int r, int c){
        Queue<Info> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[5][5];
        visited[r][c] = true;
        queue.offer(new Info(r, c));
        //연결된 여학생의 수
        int cnt = 1;
        //BFS 탐색 진행
        while(!queue.isEmpty()){

            Info cur = queue.poll();
            //인접한 상하좌우 탐색
            for(int i=0;i<4;i++){
                int nr = cur.r + dr[i];
                int nc = cur.c + dc[i];
                int nxt = nr * 5 + nc;
                //행렬에 범위 내이며, 방문하지 않았으며, 조합 내 포함되어 있으면
                if(inSpace(nr, nc) && !visited[nr][nc] && totalVisited[nxt]){
                    visited[nr][nc] = true;
                    queue.offer(new Info(nr, nc));
                    cnt++;
                }
            }
        }
        //인접한 여학생이 7명인 경우 true, 아니면 false
        return cnt == 7;
    }
    //좌표 이동 시, 5×5 행렬안에 존재하는지 확인하는 함수
    static boolean inSpace(int r, int c){
        //행렬안에 존재할 때
        if(r >= 0 && c >= 0 && r < 5 && c < 5){
            return true;
        }
        return false;
    }
}

저작자표시

'백준' 카테고리의 다른 글

[백준, Java] 17240번, Team Selection, (그리드) (0)	2024.05.06
[백준, Java] 1256번, 사전, (조합, 다이나믹 프로그래밍) (0)	2024.04.30
[백준, Java] 24551번, 일이 너무 많아..., (정수론) (2)	2024.04.25
[백준, Java] 25330번, SHOW ME THE DUNGEON, (백트래킹) (0)	2024.04.17
[백준, Java] 16457번, 단풍잎 이야기, (완전 탐색) (2)	2024.04.15

찬형이의 공부방

[백준, Java] 1941번, 소문난 칠공주, (조합, BFS, 백트레킹)

문제 링크

주의사항

문제 설명