[백준 1941] 소문난 칠공주

www.acmicpc.net/problem/1941

1941번: 소문난 칠공주

백트래킹 응용문제이다. 어렵당...ㅠㅠ

7명의 사람이 모두 연결되어 있어야 하고 + 그 중에 'S'가 4개 이상인 경우의 수를 세는 문제이다.

 

처음에 인접 배열만 이동가능하게 했더니 중복으로 인해 값이 다르게 나왔다.

 

이 문제의 포인트는 7명의 사람에 대한 모든 경우의 수를 구해서 조건을 만족하는지 확인하는 것이라고 생각한다. 

'S'의 경우 dfs를 진행하면서 카운트가 가능하여 따로 함수를 만들지 않아도 되지만 (물론 따로 만들어도 가능 심지어 이게 더 빠름) 인접한 행렬은 한번에 체크하는 방법이 있는지... 잘 모르겠다.

 

암튼 정리하자면

1.  25명의 자리가 존재하므로 각 자리에 0 ~ 24까지 번호를 붙여서 백트래킹을 진행한다.

2. 이차원 배열에 적용하고 싶다면 row = idx / 5, col = idx % 5이다. 

3. 7명의 사람과 4명 이상의 'S' 조건이 만족된다면 인접한지 확인하고 result++;

3-1. 인접 확인은 bfs를 사용했다.

#include <stdio.h>
#include <queue>
#include <string.h>

using namespace std;

char students[6][6];
int visited[25];
int result;

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

bool isNear()
{
  queue<pair<int, int>> q;
  int tmpVisited[5][5];

  memset(tmpVisited, 0, sizeof(tmpVisited));

  for (int i = 0; i < 25; i++)
  {
    int row = i / 5;
    int col = i % 5;

    if (visited[i])
    {
      q.push(make_pair(row, col));
      tmpVisited[row][col] = 1;
      break;
    }
  }

  int adj = 0;
  while (!q.empty())
  {
    int row = q.front().first;
    int col = q.front().second;

    q.pop();
    adj++;

    for (int i = 0; i < 4; i++)
    {
      int nextR = row + dx[i];
      int nextC = col + dy[i];

      if (nextR < 0 || nextC < 0 || nextR > 4 || nextC > 4 || tmpVisited[nextR][nextC])
      {
        continue;
      }

      if (visited[nextR * 5 + nextC])
      {
        q.push(make_pair(nextR, nextC));
        tmpVisited[nextR][nextC] = 1;
      }
    }
  }

  if (adj == 7)
  {
    return true;
  }

  return false;
}
void DFS(int idx, int cnt, int s)
{
  if (cnt == 7 && s >= 4)
  {
    if (isNear())
    {
      result++;
    }
    return;
  }

  for (int i = idx; i < 25; i++)
  {
    if (visited[i])
      continue;
    visited[i] = 1;
    if (students[i / 5][i % 5] == 'S')
    {
      DFS(i, cnt + 1, s + 1);
    }
    else
    {
      DFS(i, cnt + 1, s);
    }
    visited[i] = 0;
  }
}

int main(void)
{
  for (int i = 0; i < 5; i++)
  {
    scanf("%s", students[i]);
  }
  DFS(0, 0, 0);
  printf("%d\n", result);
  return 0;
}