백준 1941번 소문난 칠공주[C++]

1. 문제 풀이

 백트래킹 + 너비우선탐색으로 풀이함, 5 * 5 배열의 위치값을 선형 자료구조에 모두 저장한 다음 백트래킹으로 7개의 위치를 뽑은 뒤 flood fill 기법으로 모두 연결되어 있는지 확인하면서 이다솜파의 개수를 카운팅해 소문난 칠공주인지를 판별했습니다. 

 

2. 코드

// Authored by : chjh2129
#include <bits/stdc++.h>
/*
  5 * 5의 위치 (i, j)를 모두 벡터에 저장한 다음

  백트래킹으로 7개의 위치 정보를 뽑아 가져온다.

  뽑아온 7개의 위치가 서로 연결되어있고 이다솜파가 4명인지 너비우선탐색으로 확인

  < 시간 복잡도 >
  BFS는 최대 7개의 칸만 확인한다 O(7 * 4) = O(1) // memset 사용으로 O(n*n)

  25개를 중복없이 7개를 뽑는 경우의 수는 25C7 = 48만
*/
using namespace std;

using pi = pair<int,int>;
#define X first
#define Y second

const int n = 5;
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

int ans; // 소문난 칠공주의 개수

string board[6];
bool isused[6][6];
bool vis[6][6];

vector<pi> pos;

// 뽑은 7개의 위치가 소문난 칠공주인지 확인
bool is_7_princess(pi st){
  memset(vis, 0, sizeof(vis)); // 방문 배열 초기화
  
  queue<pi> q;
  vis[st.X][st.Y] = 1;
  q.push(st);

  int cnt = 1; // 방문한 영역의 개수
  int dasom{}; // 이다솜파 학생의 수
  while(q.size()){
    auto [cx, cy] = q.front(); q.pop();
    if(board[cx][cy] == 'S') dasom++; // 이다솜파 학생임
    
    for(int dir = 0; dir < 4; dir++){
      int nx = cx + dx[dir];
      int ny = cy + dy[dir];
      
      if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue; // 배열 범위를 벗어남
      if(vis[nx][ny] || !isused[nx][ny]) continue; // 이미 방문했거나, 뽑았던 위치가 아님
      
      cnt++;
      vis[nx][ny] = 1;
      q.push({nx, ny});
    }
  }

  // 7명이 모두 연결되어있고, 이다솜파가 4명 이상이면 소문난 칠공주
  return cnt == 7 && dasom >= 4;
}

// 25개의 위치 중 중복없이 7개의 위치를 뽑는다.
void solve(int k, int idx){
  if(k == 7){
    if(is_7_princess(pos[idx])) ans++;
    return;
  }

  for(int i = idx; i < n * n; i++){
    auto [cx, cy] = pos[i];
    if(isused[cx][cy]) continue;
    isused[cx][cy] = 1;
    solve(k+1, i);
    isused[cx][cy] = 0;
  }
}

int main(){
  cin.tie(nullptr)->sync_with_stdio(false);

  // input
  for(int i = 0; i < n; i++){
    cin >> board[i];
    for(int j = 0; j < n; j++) pos.push_back({i, j}); 
  }

  // solve
  solve(0, 0);

  // output
  cout << ans;
}

 

3. 제출 결과