[백준] 1941. 소문난 칠공주 (Java) ⭐️

[BOJ] 1941. 소문난 칠공주

📌 풀이 과정

1. 조합으로 7개의 자리 선택

• 선택된 좌표는 2차원 배열의 인덱스를 1차원 인덱스로 변환하여 princess[] 배열에 저장한다.

• 선택된 자리가 임도연파(Y)인 경우, doyeon 값 증가 시킨다.

• 만약 doyeon 값이 3을 초과하면 해당 경로는 유효하지 않다.
  이다솜파(S)가 적어도 4명 이상이어야 한다.

2. BFS 탐색으로 인접한 7개의 자리인지 확인

• visited 배열은 7개의 자리가 모두 인접한지 확인하기 위해 사용한다.
  visited[k]는 princess[k]에 대응하는 자리가 방문되었는지 여부를 나타낸다.
  
  

💡 visited 배열 1차원으로 변환하기

int index = row * 5 + col;

5x5 크기의 2차원 배열은 인덱스가 (row, col)로 주어진다.
여기서 row는 해당 좌표의 행, col은 열을 나타낸다.
이 공식을 사용하면 2차원 좌표를 1차원 배열의 인덱스 하나로 표현할 수 있다.

예를 들어

만약 우리가 5x5 배열에서 특정 좌표 (row, col)를 visited 배열에 저장해야 한다고 하자.

• 좌표 (0, 0)은 1차원 배열에서 0 * 5 + 0 = 0번째 위치에 해당한다.
• 좌표 (1, 3)은 1 * 5 + 3 = 8번째 위치에 해당한다.
• 좌표 (4, 4)는 4 * 5 + 4 = 24번째 위치에 해당한다.

이런 방식으로 2차원 좌표를 하나의 인덱스로 변환해 관리할 수 있다.

👩🏻‍💻 제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    static int ans = 0;
    static char[][] map = new char[5][5];
    static int[] princess = new int[7];
    static boolean[] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

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

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

        pickSeven(0, 0, 0);
        System.out.println(ans);

    }

    static void pickSeven(int start, int cnt, int doyeon){
        if(doyeon > 3) return; // 임도연파가 3명 초과할 경우 종료

        if(cnt == 7){ // 7개의 자리를 뽑았다면 모두 인접된 자리인지 확인
            visited = new boolean[7];
            bfs();
            return;
        }

        for(int i = start; i < 25; i++){
            princess[cnt] = i;
            pickSeven(i + 1, cnt + 1, (map[i / 5][i % 5] == 'Y') ? doyeon + 1 : doyeon);
        }

    }

    static void bfs(){
        Queue<int[]> q = new LinkedList<>();
        int x = princess[0] / 5;
        int y = princess[0] % 5;

        int cnt = 1;
        visited[0] = true;
        q.add(new int[]{x, y});

        while(!q.isEmpty()){
            int[] cur = q.poll();
            x = cur[0]; y = cur[1];

            for(int i = 0; i < dx.length; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;

                int nxt = 5 * nx + ny; // 1차원 인덱스로 변환
                for(int k = 0; k < 7; k++){
                    if(!visited[k] && nxt == princess[k]){
                        visited[k] = true;
                        cnt++;
                        q.add(new int[]{nx, ny});
                    }
                }
            }
        }

        if(cnt == 7) ans++;
    }
}