BOJ 1941: 소문난 칠공주

문제풀이

다솜이와 도연이 팀을 정수로 변환해서 저장해놨다.
다솜이가 더 많아야 하므로 다솜이는 1, 도연이는 -1로 해서 총합이 양수일때는 다솜이 팀이 더 많다.

• 총 25개의 자리가 있으므로 25개 중 7자리를 고르는 choice 함수를 정의했다.
• 7자리를 고른 경우 중 다솜이네 팀이 더 많은 즉, 총합이 양수인 경우에만 서로 인접한 자리에 있는지 확인하는 checkTeam 함수를 호출한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[][] map = new int[5][5];
    static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 다솜: 1, 도연: -1
        for(int i = 0; i < 5; i++) {
            String temp = br.readLine();
            for(int j = 0; j < 5; j++) {
                char t = temp.charAt(j);
                if(t == 'S') {
                    map[i][j] = 1;
                }
                else {
                    map[i][j] = -1;
                }
            }
        }

        boolean[] visit = new boolean[25];
        choice(0, visit, 0, 0);

        System.out.println(answer);
    }

    public static void choice(int count, boolean[] visit, int index, int sum) {
        if(count == 7) {
            if (sum > 0) {
                boolean[][] team = new boolean[5][5];
                for(int i = 0; i < 25; i++) {
                    team[i / 5][i % 5] = visit[i];
                }
                int[][] check = new int[5][5];
                int number = 1;
                boolean flag = true;
                for(int i = 0; i < 5; i++) {
                    for(int j = 0; j < 5; j++) {
                        if(check[i][j] == 0 && team[i][j]) {
                            if(number > 1) {
                                flag = false;
                                continue;
                            }
                            checkTeam(check, number, i, j, team);
                            number++;
                        }
                    }
                    if(flag == false) {
                        continue;
                    }
                }
                if (flag) {
                    answer++;
                }
            }
            return;
        }
        if(index > 24) {
            return;
        }
        visit[index] = true;
        choice(count + 1, visit, index + 1, sum + map[index / 5][index % 5]);
        visit[index] = false;
        choice(count, visit, index + 1, sum);
    }
    static int[] dirI = {0, 0, 1, -1};
    static int[] dirJ = {1, -1, 0, 0};
    public static void checkTeam(int[][] check, int number, int i, int j, boolean[][] team){
        check[i][j] = number;
        for(int index = 0; index < 4; index++ ) {
            int nextI = i + dirI[index];
            int nextJ = j + dirJ[index];

            if(nextI < 0 || nextI >= 5 || nextJ < 0 || nextJ >= 5) {
                continue;
            }
            if(team[nextI][nextJ] && check[nextI][nextJ] == 0) {
                checkTeam(check, number, nextI, nextJ, team);
            }
        }
    }
}

백준
github