공부흔적

문제 링크

풀이 )

  0번 스위치를 시작으로 15번 스위치까지 각각 4번씩 눌러가면서 재귀호출을 통해서 모든 경우의 수에 대해서 탐색한다.

  전체 경우의 수가 4^10(≒10^6)이므로 시간초과가 나지 않는다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> push[10] = {
    {0, 1, 2},
    {3, 7, 9, 11},
    {4, 10, 14, 15},
    {0, 4, 5, 6, 7},
    {6, 7, 8, 10, 12},
    {0, 2, 14, 15},
    {3, 14, 15},
    {4, 5, 7, 14, 15},
    {1, 2, 3, 4, 5},
    {3, 4, 5, 9, 13}
};
int clocks[16];

int dfs(int num){
    if(num == 10){
        for(int i = 0; i < 16; ++i){
            if(clocks[i] != 12)
                return 1e7;
        }
        return 0;
    }

    int ret = 1e7;
    for(int i = 0; i < 4; ++i){
        ret = min(ret, i+dfs(num+1));
        int len = push[num].size();
        for(int i = 0; i < len; ++i){
            clocks[push[num][i]] = clocks[push[num][i]]%12+3;
        }
    }
    return ret;
}

int main(void){
    int c;
    cin >> c;
    while(c--){
        for(int i = 0; i < 16; ++i)
            cin >> clocks[i];

            int ans = dfs(0);
            if(ans >= 1e7)
                ans = -1;
            cout << ans << '\n';
    }
}

문제 링크

풀이 )

  먼저 입력받은 '.'의 개수를 세서 3으로 나누어떨어지지 않는 경우 '0'을 출력하고 종료한다.

  '.'의 개수를 3으로 나누어 보드에 들어가는 총 블록의 수를 세고, DFS로 보드에 블록을 채워준다.

  DFS 함수 내에서는 기저사례로 남은 블록 수가 0일 때 1을 반환하게 한다.

  board에서 위에서부터 보면서 첫 '.'을 찾고, 그 위치에서 4종류의 블록을 넣어보면서 다음 블록을 채워 넣는다.

#include <iostream>
#include <string>

using namespace std;

int block[4][3][2] = {
    {{0, 0}, {1, 0}, {1, 1}},
    {{0, 0}, {0, 1}, {1, 1}},
    {{0, 0}, {1, 0}, {0, 1}},
    {{0, 0}, {1, 0}, {1, -1}}
};

int h, w;

int dfs(string board[], int numBlock){
    if(!numBlock)
        return 1;

    int x = -1, y = -1;
    for(int i = 0; i < h; ++i){
        for(int j = 0; j < w; ++j){
            if(board[i][j] == '.'){
                x = i;
                y = j;
                break;
            }
        }
        if(y != -1)
            break;
    }

    int ret = 0;
    for(int i = 0; i < 4; ++i){
        bool flag = 0;
        for(int j = 0; j < 3; ++j){
            int nx = x+block[i][j][0];
            int ny = y+block[i][j][1];
            if(nx < 0 || nx >= h || ny < 0 || ny >= w || board[nx][ny] == '#'){
                flag = true;
                break;
            }
        }
        if(flag)
            continue;

        for(int j = 0; j < 3; ++j){
            int nx = x+block[i][j][0];
            int ny = y+block[i][j][1];
            board[nx][ny] = '#';
        }
        ret += dfs(board, numBlock-1);
        for(int j = 0; j < 3; ++j){
            int nx = x+block[i][j][0];
            int ny = y+block[i][j][1];
            board[nx][ny] = '.';
        }
    }
    return ret;
}

int main(void){
    int c;
    cin >> c;
    while(c--){
        cin >> h >> w;
        string* board = new string[h];
        int numBlock = 0;
        for(int i = 0; i < h; ++i){
            cin >> board[i];
            for(int j = 0; j < w; ++j){
                if(board[i][j] == '.')
                    numBlock++;
            }
        }
        if(numBlock%3){
            cout << 0 << '\n';
            continue;
        }
        numBlock/=3;

        cout << dfs(board, numBlock) << '\n';
    }
}

문제 링크

풀이 )

  짝이 되는 경우 사람이 2명씩 빠지게 되므로 남는 인원이 2명씩 줄게 되고 0명이 되는 경우 모두 짝을 이루기 때문에 답을 1 증가시킨다.

  친구 관계를 나타내는 2차원 배열과 이미 짝이 만들어졌는지 여부를 확인할 배열을 만들어서 아직 짝이 아니고 친구 관계인 2명의 친구를 짝으로 만들어주고 다른 모든 방법에 대해 확인해 보기 위해 재귀함수 호출 이후 반복문이 돌기 전에 짝으로 만들어진 부분을 지워준다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int c, n, m;
int rel[10][10];
int visited[10];
int ans;

void rec(int remain){
  if(remain == 0){
    ans++;
    return;
  }

  int first, second;
  for(int i = 0; i < n-1; ++i){
    for(int j = i+1; j < n; ++j){
      if(rel[i][j] && !visited[i] && !visited[j]){
        visited[i]++;
        visited[j]++;
        rec(remain-2);
        visited[i]--;
        visited[j]--;
      }
    }
  }
}

int fac(int num){
  if(num < 3)
    return num;
  return num * fac(num-1);
}

int main(void){

  cin >> c;
  while(c--){
    cin >> n >> m;
    ans = 0;
    fill(visited, visited+n, 0);
    for(int i = 0; i < n; ++i)
      fill(rel[i], rel[i]+n, 0);
    for(int i = 0; i < m; ++i){
      int first, second;
      cin >> first >> second;
      rel[first][second] = 1;
      rel[second][first] = 1;
    }

    rec(n);
    ans /= fac(n/2);
    cout << ans << endl;
  }
}

주의점 )

• 재귀함수 속에서의 i와 j의 대소관계를 항상 유지하여 중복 제거
• ans /= fac(n/2)을 통해 짝의 순서로 인해 생기는 중복 제거