소문난 칠공주 백준 1941번 c++

문제

소문난 칠공주 백준 1941

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

// 1941 소문난 칠공주

int room[5][5]; // 입력받음
bool check[25];  // 조합
int temproom[5][5];
bool vis[5][5]; // 방문 체크
int answer;
int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};

void checkad(int startx, int starty){

  fill(vis[0], vis[5], 0);

  queue<pair<int,int>> qu;
  qu.push({startx, starty});
  vis[startx][starty] = true;

  int checkcnt = 0;

  while(!qu.empty()){
    int cx = qu.front().X;
    int cy = qu.front().Y;
    qu.pop();
    checkcnt++;

    if(checkcnt==7) break;

    for(int i = 0; i < 4; i++){
      int nx = dx[i] + cx;
      int ny = dy[i] + cy;

      if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
      if(!vis[nx][ny] && temproom[nx][ny] == 1) {
        vis[nx][ny] = true;
        qu.push({nx, ny});
      }
    }
  }

  if(checkcnt == 7) answer++;
}

void permu(){

  do{
    fill(temproom[0], temproom[5], 0);

    int cnts = 0, startx =0 , starty =0 ;

    for(int i = 0; i < 25; i++){
      if(!check[i]){
        int x = i/5; // 행
        int y = i%5; // 열
        temproom[x][y] = 1; // 선택한 7칸 표시.
        startx = x, starty = y;
        if(1 == room[x][y]) cnts++; // 이다솜파 카운트
      }
    }

    if(cnts >= 4) checkad(startx, starty); // 이다솜파 4명 이상이면 인접 체크 호출

  }while(next_permutation(check, check+25));
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  string st;

  for(int i = 0; i < 5; i++){
    cin >> st;
    for(int j = 0; j < 5; j++){
      if(st[j] == 'Y') room[i][j] = 2;
      else room[i][j] = 1; // S 이다솜파
    }
  }

  for(int i = 7; i < 25; i++) check[i] = true;

  permu();
  cout << answer;

  return 0;
}

리뷰

조합과 bfs가 혼합된 유형이었다.
2차원 배열 fill 함수를 틀리게 구현해서 2시간 동안 고생했다.

로직의 순서는 아래와 같다.

 

 

1. 주어진 학생들위치 배열 room에 입력받기
2. false가 7개, true가 18개로 구성된 check 배열 만들기.
3. next_permutation 으로 check배열의 순열을 돌린다. check 배열 false index로 25칸 중에 7칸을 고르는 조합 만들기.
4. 현재 조합 중에서 (선택된 7칸에서) 이다솜파가 4명 이상 포함되어 있는지 검사하기
5. 이다솜파가 4명이상 포함되어 있는 경우에, 선택된 7칸이 서로 모두 인접한지 검사하기.
6. BFS를 돌릴때, 선택된 7개의 칸에 포함되면서도 처음으로 방문한 칸인지 검사해야 한다.