백준 1941 : 소문난 칠공주

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

1941번: 소문난 칠공주

[JAVA]

public class Main {
    static char[][] arr = new char[5][5];
    static int[] dy = { -1, 0, 0, 1 }, dx = { 0, -1, 1, 0 };
    static boolean[] b = new boolean[25];
    static int ret = 0;

    static boolean find(int y, int x) {
        boolean[][] check = new boolean[5][5];
        Queue<int[]> q = new LinkedList<>();
        check[y][x] = true;
        int vcnt = 1;
        q.offer(new int[] { y, x });
        while (!q.isEmpty()) {
            int[] s = q.poll();

            for (int i = 0; i < 4; i++) {
                int yy = s[0] + dy[i];
                int xx = s[1] + dx[i];
                if (0 <= yy && yy < 5 && 0 <= xx && xx < 5 && !check[yy][xx] && b[yy * 5 + xx]) {
                    vcnt += 1;
                    check[yy][xx] = true;
                    q.offer(new int[] { yy, xx });
                }
            }
        }
        return vcnt == 7 ? true : false;
    }

    static void dfs(int n, int pick, int sc) {
        sc += arr[n / 5][n % 5] == 'S' ? 1 : 0;
        b[n] = true;
        if (pick == 7) {
            if (sc >= 4) {
                if (find(n / 5, n % 5)) {
                    ret += 1;
                }
            }
        } else {
            for (int i = n + 1; i < 25; i++) {
                if (!b[i])
                    dfs(i, pick + 1, sc);
            }
        }
        b[n] = false;
    }

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

        for (int i = 0; i < 5; i++) {
            String in = br.readLine();
            for (int j = 0; j < 5; j++) {
                arr[i][j] = in.charAt(j);
            }
        }

        for (int i = 0; i < 25; i++) {
            dfs(i, 1, 0);
        }

        System.out.println(ret);

        br.close();
    }
}

---

 

[C++]

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

char arr[5][5];
bool b[25];
bool check[5][5];
int ret;
queue<pair<int, int>> q;
int dy[]{-1, 0, 0, 1}, dx[]{0, -1, 1, 0};

bool isFriends(int n)
{
    int y = n / 5;
    int x = n % 5;

    for (int i = 0; i < 5; i++)
    {
        fill(check[i], check[i] + 5, false);
    }
    int cnt = 1;
    check[y][x] = true;
    q.push(make_pair(y, x));
    while (!q.empty())
    {
        pair<int, int> p = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            y = p.first + dy[i];
            x = p.second + dx[i];
            if (0 <= y && y < 5 && 0 <= x && x < 5 && b[5 * y + x] && !check[y][x])
            {
                cnt++;
                check[y][x] = true;
                q.push(make_pair(y, x));
            }
        }
    }
    return cnt == 7 ? true : false;
}

void combine(int n, int pick, int s)
{
    b[n] = true;
    s += arr[n / 5][n % 5] == 'S' ? 1 : 0;
    if (pick == 7)
    {
        if (s >= 4 && isFriends(n))
            ret++;
    }
    else
    {
        for (int i = n + 1; i < 25; i++)
            combine(i, pick + 1, s);
    }
    b[n] = false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            cin >> arr[i][j];

    for (int i = 0; i < 25; i++)
        combine(i, 1, 0);

    cout << ret;
    return 0;
}

 

 

조합을 통해서 7명을 뽑고 이다솜(S)파가 4명이상일 경우에만 7명이 인접해있는지 확인한다.

 

---

처음 풀때는 DFS를 통해서 7명을 찾을려고 해서 풀지 못했다. 옆 행렬인 경우 (2,1)에서 시작해서 (4,2)와 (4,5)를 포함하는 경우의 수가 존재한다. (4,5) 경우에는 DFS로 탐색이 가능하지만 (4,2) 경로를 포함한 경우는 (2,2) 좌표에서 십자가모양으로 퍼지기 때문에 DFS로 탐색할 수 없다. 

그래서 조합을 통해서 25개의 좌표 중에서 7개를 먼저 선택하는 방식으로 문제를 풀 수 있었다.