자바(백준) 1941 소문난 칠공주

오답 노트 & 새로 알게 된 점

처음 문제 접근할 때, 백트레킹을 사용하여 조건을 세우면 문제가 풀릴 것이라고 생각했다.

그러나 아래와 사진과 같이 T자 형이나 +자 형은 백트래킹으로 구하는데 어려움이 있다.

그러면 어떠한 방법을 사용해야할까 생각을 했다.

 

문제에서 25명의 학생이 고정이라고 했으므로

각각의 학생에게 0~24의 번호를 부여한다.

 

중복을 허락하지 않은 조합을 이용하여 25명 중에 7명을 뽑고,

7명이 모두 이어져있는지 bfs로 확인하면 된다.

 

그렇다면 여기서 0~24를 어떻게 행과 열로 나타낼 수 있을까라는 생각을 해야한다.

위의 사진과 같은 테크닉을 사용하면 행과 열로 나타낼 수 있다.

이 문제에서 가장 중요한 방법이라고 생각이 든다.

 

그래서 bfs조건 중에 방문했냐, 범위를 넘느냐 조건에다가

해당 학생이 뽑혔는지 확인하는 조건도 추가해줘야 한다.

 

---

코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static String A[][];
    static int dx[] = {0, 0, 1, -1};
    static int dy[] = {1, -1, 0, 0};
    static boolean visit[];
    static int select[];
    static int ans;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        dfs(0,0, 0);
 
        System.out.println(ans);
    }
 
    static void dfs(int idx, int cnt,int cntS) {
        if(cnt == 7){
            if(cntS >= 4) {
                ans += bfs();
            }
            return;
        }
 
        for (int i = idx; i < 25; i++) {
            if(visit[i]) continue;
 
            select[cnt] = i;
            visit[i] = true;
            if(A[i/5][i%5].equals("S")) dfs(i+1, cnt + 1, cntS + 1);
            else dfs(i+1, cnt + 1, cntS);
            visit[i] = false;
            select[cnt] = -1;
        }
 
    }
 
    static int bfs() {
        Queue<Integer> q = new ArrayDeque<>();
        boolean vis[][] = new boolean[5][5];
        int cnt = 1;
        q.offer(select[0] / 5);
        q.offer(select[0] % 5);
        vis[select[0] / 5][select[0] % 5] = true;
 
        while (!q.isEmpty()) {
            int X = q.poll();
            int Y = q.poll();
 
            for (int i = 0; i < 4; i++) {
                int dX = X + dx[i];
                int dY = Y + dy[i];
 
                if(!isRangeTrue(dX,dY)) continue;
                if(vis[dX][dY]) continue;
                if(!visit[dX*5+dY]) continue;
                //dX*5+dY 번의 학생이 뽑혔는지 확인인
                cnt++;
                q.offer(dX);
                q.offer(dY);
                vis[dX][dY] = true;
            }
        }
 
        if(cnt == 7) return 1;
 
        else return 0;
 
    }
 
    static boolean isRangeTrue(int x, int y) {
        return x >= 0 && x < 5 && y >= 0 && y < 5;
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        A = new String[5][5];
        visit = new boolean[25];
        select = new int[7];
 
        for (int i = 0; i < 5; i++) {
            String str = br.readLine();
            for (int j = 0; j < 5; j++) {
                A[i][j] = str.charAt(j) + "";
            }
        }
    }
}