백준 1941번 소문난 칠공주 :: 마이구미

이 글은 백준 알고리즘 문제 1941번 "소문난 칠공주" 를 풀이한다.

기본적인 DFS를 통한 백트래킹을 활용해서는 이 문제를 해결할 수 없다.

문제 접근에 있어, 아이디어가 필요한 문제이다.

1941번 - https://www.acmicpc.net/problem/1941

DFS, BFS - http://mygumi.tistory.com/102

Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc

총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다.

위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.

1. 이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.
2. 강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.
3. 화합과 번영을 위해, 위해 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다.
4. 그러나 생존을 위해, ‘이다솜파’가 반드시 우위를 점해야 한다. 따라서 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.

여학생반의 자리 배치도가 주어졌을 때, ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 구하는 프로그램을 작성하시오.

문제는 이다솜파 학생이 4명이상인 인접한 경우를 찾는 문제가 된다.

기본적인 DFS 로는 문제를 해결할 수 없다.

왜냐하면 십자가 모양 같은 경우는 기본적인 DFS로는 찾을 수가 없기 때문이다.

여기서 아이디어가 필요하다.

이 문제는 풀고나니 거의 대다수가 비슷한 생각을 가지고 푸는 것을 볼 수 있었다.

정사각형은 5 * 5 로 고정되어있고, 이 의미는 25명이 고정이라고 볼 수 있다.

여기서 로또 문제를 풀어봤다면, 로또 문제가 생각날 수 있다. (6603번 로또)

로또처럼 몇개 중 7개를 고르는 경우를 모두 뽑을 수 있다.

이 경우도 마찬가지로 25명 중에 7명의 경우를 모두 뽑아볼 수 있다.

최종적인 아이디어는 다음과 같다.

25명 중 7명을 뽑되, 이다솜파의 학생이 4명이상인 경우를 뽑는다.

뽑은 경우가 서로 연결되어있는 지 탐색한다.

25명 중 7명을 뽑는 방법은 다음과 같다.

우선 학생을 번호라고 생각한다.

0  1  2  3  4
5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24

다음과 같이 7개의 번호를 뽑는 경우는 무수히 많다.

0 1 2 3 4 5 6
0 1 2 3 4 5 7
..............
0 1 5 13 18 20 22

0 ~ 24 각각을 기준 정점으로 모든 경우를 DFS 탐색할 수 있다.

그 과정 중 이다솜파의 학생의 수를 체크하면서, 한번 걸러줄 수 있다.

// array => 주어진 입력
// visited => 방문 번호
// map => 연결 요소인지 확인하기 위한 방문 좌표
public static void dfs(int n, int cnt, int s) {
    if (array[n / 5][n % 5] == 'S') {
        ++s;
    }

    visited[n] = true;
    map[n / 5][n % 5] = true;

    if (7 == cnt) {
        if (s >= 4) {
            find();
        }
    } else {
        for (int i = n + 1; i < 25; i++) {
            if (!visited[i]) {
                dfs(i, cnt + 1, s);
            }
        }
    }
    // backtracking
    visited[n] = false;
    map[n / 5][n % 5] = false;
}

각 번호는 나누기와 나머지 연산을 이용해서 행과 열을 구할 수 있다.

행과 열을 통한 map 배열은 구해진 경우가 연결되었는지 판단하기 위해서 사용한다.

25명 중 이다솜파가 4명이상인 7명을 뽑은 후, 이 경우가 연결되었는지만 판단하면 문제를 해결할 수 있다.

연결 여부는 기본적인 DFS를 활용할 수 있다.

이 문제는 알고리즘은 구현 능력보다는 문제를 접근하는 아이디어를 통해 해결할 수 있다.

전체 소스를 통해 이해하길 바란다.

static int ans, cnt;
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, -1, 0, 1 };
static char[][] array;
static boolean[][] map;
static boolean[] visited;
 
private void solve() {
    array = new char[5][5];
 
    for (int i = 0; i < 5; i++) {
        array[i] = sc.readLine().toCharArray();
    }
 
    for (int i = 0; i < 25; i++) {
        visited = new boolean[25];
        map = new boolean[5][5];
        dfs(i, 1, 0);
    }
    System.out.println(ans);
}
 
public static void dfs(int n, int cnt, int s) {
    if (array[n / 5][n % 5] == 'S') {
        ++s;
    }
 
    visited[n] = true;
    map[n / 5][n % 5] = true;
 
    if (7 == cnt) {
        if (s >= 4) {
            find();
        }
    } else {
        for (int i = n + 1; i < 25; i++) {
            if (!visited[i]) {
                dfs(i, cnt + 1, s);
            }
        }
    }
    // backtracking
    visited[n] = false;
    map[n / 5][n % 5] = false;
}
 
public static void find() {
    for (int i = 0; i < 25; i++) {
        if (visited[i]) {
            int y = i / 5;
            int x = i % 5;
 
            boolean[][] visited = new boolean[5][5];
            visited[y][x] = true;
            cnt = 1;
            isComponent(y, x, visited);
            return;
        }
    }
}
 
public static void isComponent(int y, int x, boolean[][] checked) {
    if (7 == cnt) {
        ++ans;
    } else {
        for (int i = 0; i < 4; i++) {
            int ny = dy[i] + y;
            int nx = dx[i] + x;
 
            if (0 <= ny && ny < 5 && 0 <= nx && nx < 5) {
                if (map[ny][nx] && !checked[ny][nx]) {
                    checked[ny][nx] = true;
                    ++cnt;
                    isComponent(ny, nx, checked);
                }
            }
        }
    }
}