[BOJ][백트래킹][골3][1941] 소문난 칠공주

문제 링크

문제 링크

풀이

알고리즘

2차원 N자리 K진수를 적용해서 해결하는 문제입니다. 선택한다/안한다의 방법을 적용합니다.

[이론][완전탐색][N자리 K진수] Chapter 4를 확인해보세요.

정답 코드

#include <bits/stdc++.h>

#define MAX 5
using namespace std;
typedef long long ll;

int n = 0, k = 0; //N:배열의 길이 , K: 진수
int v[MAX];

vector<string> input(5);
bool selected[MAX][MAX]; // 칠공주 선택에 사용
bool visited[MAX][MAX]; // dfs에서 방문처리에 사용
int ans = 0;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int dfs(int x, int y) {
  visited[x][y] = true;
  int nx = 0, ny = 0;
  int ret = 1;

  for (int k = 0; k < 4; k++) {
    nx = x + dx[k];
    ny = y + dy[k];
    if (nx < 0 || nx >= 5) continue;
    if (ny < 0 || ny >= 5) continue;
    if (selected[nx][ny] && !visited[nx][ny]) {
      ret += dfs(nx, ny);
    }
  }
  return ret;
}

bool check() {
  memset(visited, false, sizeof(visited));

  for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
      if (selected[i][j] && !visited[i][j]) {
        if (dfs(i, j) != 7) {
          return false;
        }
      }
    }
  }
  return true;
}

void recur(int x, int y, int cnt, int scnt) {
  if (cnt == 7) {
    if (scnt >= 4 && check()) ans++;
    return;
  }

  if (y == 5) {
    y = 0;
    x++;
  }

  if (x == 5) {
    return;
  }

  selected[x][y] = true;
  recur(x, y + 1, cnt + 1, scnt + (input[x][y] == 'S'));
  selected[x][y] = false;

  recur(x, y + 1, cnt, scnt);
}

int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  for (int i = 0; i < 5; i++) {
    cin >> input[i];
  }
  recur(0, 0, 0, 0);
  cout << ans << "\n";
  return 0;
}

Success Notice: 2 차원 N 자리 K진수 개념을 사용한 문제를 풀어봤습니다. 수고하셨습니다.