[BOJ] 1941번 : 소문난 칠공주

1. problem :

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

 

2. solution 1 :

// Authored by : heheHwang
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/b318d03bfd694a57be91322ff1dcd4ef
#include <bits/stdc++.h>
using namespace std;

bool mask[25];
string board[5];
int ans;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  for (int i = 0; i < 5; i++)
    cin >> board[i];

  // 25명중 칠공주가 될 사람의 후보 조합을 뽑습니다.
  fill(mask + 7, mask+25, true);
  do {
    queue<pair<int, int>> q;
    // 구성원 중 이다솜파의 수, 가로세로로 인접한 사람의 수
    int dasom = 0, adj = 0;
    bool isp7[5][5] = {}, vis[5][5] = {};
    for (int i = 0; i < 25; i++)
      if (!mask[i]) {
        int x = i / 5, y = i % 5;
        isp7[x][y] = true;
        if (q.empty()) {
          q.push({x, y});
          vis[x][y] = true;
        }
      }
    while (!q.empty()) {
      int x, y;
      tie(x, y) = q.front();
      q.pop();
      adj++;
      dasom += board[x][y] == 'S';
      for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5 || vis[nx][ny] || !isp7[nx][ny])
          continue;
        q.push({nx, ny});
        vis[nx][ny] = true;
      }
    }
    ans += (adj >= 7 && dasom >= 4);

  } while (next_permutation(mask, mask + 25));
  cout << ans;
}
/*
25명 중 칠공주가 배치될 수 있는 모든 조합을 시도합니다.
경우의 수가 많아보이지만, 25C7 = 480700이므로
충분히 2초안에 수행될 수 있습니다.
서로 가로세로로 인접해야 한다는 2번 조건은 여러가지 방법으로
확인할 수 있으나, 본 풀이에서는 BFS를 이용하였습니다.
*/

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0C/solutions/1941.cpp

basic-algo-lecture/0x0C/solutions/1941.cpp at master · encrypted-def/basic-algo-lecture

bfs와 backtracking을 이용해야겠다고는 생각이 들었다. 하지만, 좌표는 어떻게 설정할 것이며, 반복은 어떻게 해야 하며 감이 안 잡혔다. 코드를 보니 예술이다. 외우자.