백준 1941 소문난 칠공주

작성일 | In |

Problem : 소문난 칠공주

유형 : Backtracking

해결 전략

  • 먼저 7명을 조합을 이용하여 뽑아본다.
  • 총 25명으로 구성되어 있으니, 25명중 7명을 뽑는 경우의 수는 25 C 7로 480699 이 나온다.
  • BFS를 이용하여 서로 연결되어있는지를 확인한다.
    • 480699 x 25 < 2억 이므로 해결 가능하다.

주의할 점

  • 일반적인 DFS, BFS 기법으로 풀리지 않는다.
    • 십자가 모양이 있기 때문이다. 모든 조합의 경우를 따져볼 수 없다
  • 미리 조합을 만들어보고, 검증만 BFS로 하면된다.

풀이

칠공주 조합을 만들어본다.

  • 25명이니 7명을 선택하고 permutation을 통해 480699가지의 조합을 만든다.

팀을 구성한 인원들을 체크한다.

  • 조합에서 1이 위치한 곳이 팀을 이루는 인원이 존재하는 곳이다.
  • 만약 n이 3이고 1이 5에 있다면
0 1 2
3 4 5
6 7 8

팀원들이 전부 연결 되어있는지 확인한다.

  • 팀구성원중 아무나 한명을 BFS 시작점으로 잡고 BFS를 해본다.
    • 필자의 경우, 마지막으로 구성된 팀원을 시작점으로 삼았다.
  • 만약 7명이 전부 연결되어 있다면, 칠공주 결성이 가능하다.

코드

2021-09-27 코드 수정

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>

#define pii pair<int,int>
using namespace std;

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

char board[5][5];
bool canGo[5][5];
bool visited[5][5];

vector<int> member(25 - 7, 0);

queue<pii > location;

int n = 5;

void init() {
  memset(canGo, false, sizeof(canGo));
  memset(visited, false, sizeof(visited));
  location = queue<pii >();
}

bool locationCheck() {
  int memberCount = 0;

  while (!location.empty()) {
    pii cur = location.front();
    location.pop();
    memberCount++;

    for (int dir = 0; dir < 4; ++dir) {
      int nx = cur.first + dx[dir];
      int ny = cur.second + dy[dir];

      if (nx < 0 or nx >= n or ny < 0 or ny >= n)continue;
      if (visited[nx][ny])continue;
      if (!canGo[nx][ny])continue;

      visited[nx][ny] = true;
      location.push({nx, ny});
    }
  }

  return memberCount == 7;
}

bool teamCheck() {
  int Y_count = 0;

  int x, y;
  for (int i = 0; i < 25; ++i) {
    if (member[i] != 1)continue;
    x = i / n;
    y = i % n;
    if (board[x][y] == 'Y') Y_count++;

    canGo[x][y] = true;
    if (Y_count >= 4) return false;
  }

  visited[x][y] = true;
  location.push({x, y});
  return locationCheck();
}

int solve() {
  int answer = 0;

  do {
    init();
    if (teamCheck()) answer++;
  } while (next_permutation(member.begin(), member.end()));

  return answer;
}

void input() {
  string line;
  for (int i = 0; i < n; ++i) {
    cin >> line;
    for (int ii = 0; ii < n; ++ii) {
      board[i][ii] = line[ii];
    }
  }
  for (int i = 0; i < 7; ++i) member.push_back(1);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  freopen("input.txt", "r", stdin);

  input();
  cout << solve() << "\n";

  return 0;
}

피드백

  • 일반적인 BFS, DFS가 불가능함을 빨리 캐치했어야 했다.
  • 모든 조합의 수를 만들어보고 해보는것도 하나의 솔루션이 될 수 있다.