BOJ 1941) 소문난 칠공주 (C++)

1941번: 소문난 칠공주

 처음에는 각 점에 대해 DFS나 BFS로 탐색을 시도하려고 했는데 그럴 경우 다음과 같은 경우가 탐색이 되지 않았다. 

		O
O	O	O	O	O
		O

 

				O
O	O	O	O	O
		O

어떻게 해야 하나 머리를 싸매다가 https://transferhwang.tistory.com/294 님의 블로그에서 도움을 얻었다. 

1. 7명의 학생을 뽑는다. 

2. 해당 학생들 중 이다솜파가 4명 이상인지, 모든 학생이 인접해 있는지를 검사한다. 

#include <bits/stdc++.h>
using namespace std;

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
string arr[5];
bool visited[25];
bool checked[5][5];
int ans=0;

bool moreThanFour(){
  int cnt=0;
  for(int i=0;i<25;i++){
    if(visited[i]&&arr[i/5][i%5]=='S'){
      cnt++;
    }
  }
  if(cnt>=4) return true;
  else return false;
}

bool nearBy(){
  queue<pair<int,int>> q; // **
  memset(checked, false, sizeof(checked));
  for(int i=0;i<25;i++){
    if(visited[i]){
      q.push({i/5,i%5});
      break;
    }
  }

  int cnt=1;
  while(!q.empty()){
    int x=q.front().first;
    int y=q.front().second;
    checked[x][y]=true;
    q.pop();

    if(cnt==7) return true;
    for(int i=0;i<4;i++){
      int nx=x+dx[i];
      int ny=y+dy[i];
      if(nx<0||ny<0||nx>=5||ny>=5) continue;
      if(checked[nx][ny]||!visited[nx*5+ny]) continue;
      q.push({nx,ny});
      checked[nx][ny]=true;
      cnt++;
    }
  }
  return false;
}

void dfs(int idx, int cnt){
  if(cnt==7){
    if(moreThanFour() && nearBy()) ans++;
    return ;
  } else {
    for(int i = idx; i<25;i++){
      if(!visited[i]){
        visited[i]=true;
        dfs(i, cnt+1);
        visited[i]=false;
      }
    }
  }
}

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

  for(int i=0;i<5;i++){
    cin>>arr[i];
  }
  dfs(0,0);
  cout<<ans;
}

코드 상에서 큐를 전역 선언을 해서 오답이 떴다가 while문 안으로 옮겼더니 정답 처리가 되었다. 처음에는 이유를 몰랐는데 cnt가 7이 되면 바로 탈출을 하기 때문에 큐에서 미처 빠져나오지 못한 원소들이 있을 수 있다는 것을 깨달았다.