급하게임개발

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

이 문제는 처음 보고 어떻게 풀어야지라는 생각이 너무들었다 골드 3부터는 여러알고리즘이 섞여 어떻게 딱풀어야지라고 생각이 안나는 거같다

이 문제는 일단 조합으로 우리는 2차원 배열에서 원소를 뽑아줄것이다 원소를 뽑을 때는 1차원 배열이라고 생각해서 뽑아야한다

즉 위표와 같이 0,0 은 0번 0,1은 1번 이라고 생각해야한다 이거를 구하는 방법은 다음과 같다
행/5 + 열%5 를 하면 몇번짼지 우리는 알수 있다 이를 바탕으로 우리는 일차원 배열에서 7개를 뽑은 후 해당 7개의 원소가 서로 이어져 있고 S의 갯수가 4보다 많은지만 검사하면 된다

검사는 우리가 조합으로 뽑은 7개의 원소를 bfs 로 검사한다 즉 bfs로 특정 방향들을 탐색 한다 만약 끊어져있는 부분이 생기면큐에 원소가 들어가지 않을 테니 연속되지 않음을 우리는 알수 있다 전체 코드는 아래와 같다

#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

char grid[5][5];
int ans = 0;
bool isConnected(vector<int> selected) {
    int dx[4] = { -1,1,0,0 };
    int dy[4] = { 0,0,-1,1 };
    int cnt = 1;
    bool isVisited[25] = { false, };
    bool sel[25] = { false, };

    for (int i = 0; i < 7; i++) {
        sel[selected[i]] = true;
    }

    queue<int> bfsQ;
    bfsQ.push(selected[0]);
    isVisited[selected[0]] = true;

    while (!bfsQ.empty()) {
        int cur = bfsQ.front();

        int r = cur / 5;
        int c = cur % 5;

        bfsQ.pop();

        for (int i = 0; i < 4; i++) {
            int nr = r + dx[i];
            int nc = c + dy[i];
            if (nr < 0 || nr >= 5 || nc < 0 || nc >= 5)
                continue;
            int nxt = nr * 5 + nc;


            if (!isVisited[nxt] && sel[nxt]) {
                isVisited[nxt] = true;
                bfsQ.push(nxt);
                cnt++;
            }
        }
    }

    return cnt == 7;
}
void dfs(int start, int count, int sCount, vector<int> selected) {
    if (count == 7) {
        if (sCount >= 4 && isConnected(selected)) {
            ans += 1;
        }
        return;
    }
    if (sCount + (7 - count) < 4)
        return;

    for (int i = start; i < 25; i++) {
        int r = i / 5;
        int c = i % 5;

        selected.push_back(i);

        if (grid[r][c] == 'S') {
            dfs(i + 1, count + 1, sCount + 1, selected);
        }
        else {
            dfs(i + 1, count + 1, sCount , selected);
        }

        selected.pop_back();
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 5x5 격자 입력 받기
    for (int i = 0; i < 5; i++) {
        string line;
        cin >> line;
        for (int j = 0; j < 5; j++) {
            grid[i][j] = line[j];
        }
    }

    vector<int> selected;
    dfs(0, 0, 0, selected);
    cout << ans << "\n";

    return 0;
}