[문제 유형]완전 탐색 유형

쉬운 문제를 어렵게 풀지 말자. 문제를 접했을 시, 노가다가 가능한지 항상 우선적으로 생각하자.

 

완전 탐색(exhaustive search, 철저한 검색이라는 뜻.)은 말 그대로 경우의 수를 모조리 찾아보는 탐색법이다. 브루트 포스(한국말로 노가다)라고도 한다.

 

 

1. 순열/조합 유형

 

 

2. 재귀 함수를 사용하는 유형. (feat 완전 탐색 레시피 : https://sanghoonly.tistory.com/25)

 

 

3. 재귀 함수를 사용하지 않는 유형.

 

 

 

 

+ 최적화 문제 또한 완전 탐색으로 접근할 수 있다. 사실, 완전 탐색은 최적화 문제를 풀기위한 가장 기초적이고 직관적인 방법인데, 그냥 전부 답을 생성한 다음 그중에서 제일 좋은 것을 골라내면 되기 때문이다. (ex. 외판원 문제)

 

---

 

1. 순열/조합 유형

 

 

 

- 주어진 원소의 모든 순열 및 조합을 생성. 순열/조합 코드 작성시, 재귀 함수 호출 가능.

 

ex)

- N과 M 시리즈 (https://sanghoonly.tistory.com/22 , https://sanghoonly.tistory.com/23)

- 다음 순열, 이전 순열, 모든 순열 (https://sanghoonly.tistory.com/24 )

- 차이를 최대로 (https://www.acmicpc.net/problem/10819, next_permutation으로 모든 순열에서 차이를 계산하며 최댓값 도출.)

- 로또 (https://www.acmicpc.net/problem/6603, 결국 nC6을 프린트.)

 

 

 

 

 

---

 

 

 

 

 

2. 재귀 함수를 사용하는 유형. (feat 완전 탐색 레시피 : https://sanghoonly.tistory.com/25)

 

- 함수를 재귀적으로 호출하여, 가능한 경우의 수를 조건에 맞는지 모두 검사. 완전 탐색 레시피를 적용할 수 있는 일반적인 유형.

- 주로 for문을 돌면서, 배열에다 한 요소를 넣고 그 배열을 인자로 재귀 호출을 한 다음 호출이 끝난 후 그 요소를 빼며 검사한다.

 

ex)

- 1, 2, 3 더하기 (https://www.acmicpc.net/problem/9095)

- 암호 만들기 (https://www.acmicpc.net/problem/1759)

- 스타트와 링크 (https://www.acmicpc.net/problem/14889)

- 링크와 스타트 (https://www.acmicpc.net/problem/15661)

 

암호 만들기 예시 코드

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

using namespace std;

void printPassword(vector<char> &password)
{
  for (auto item : password)
    cout << item;
  cout << '\n';
}

bool isRightPassword(vector<char> &password)
{
  int cnt = 0;

  for (auto item : password)
    if (item == 'a' || item == 'e' || item == 'u' || item == 'i' || item == 'o')
      cnt++;

  return (cnt && (password.size() - cnt) >= 2) ? true : false;
}

void possiblePassword(int L, int C, char *words, vector<char> &passwords)
{
  if (!L)
  {
    if (isRightPassword(passwords))
      printPassword(passwords);
  }

  for (int i = 0; C > i; i++)
  {
    if (!passwords.empty() && passwords.back() >= words[i])
      continue;
    passwords.push_back(words[i]);
    possiblePassword(L - 1, C - 1, words + 1, passwords);
    passwords.pop_back();
  }
}

int main(void)
{
  int L, C;
  vector<char> passwords;

  cin >> L >> C;

  char words[C];

  for (int i = 0; C > i; i++)
    cin >> words[i];

  sort(words, words + C);

  possiblePassword(L, C, words, passwords);

  return 0;
}

 

 

 

---

3. 재귀 함수를 사용하지 않는 유형.

 

- for문 등을 통해, 함수를 재귀적으로 호출하지 않는 선에서 모든 가능성을 탐색하는 유형.

- 여러 의미에서 진정한 노가다. 빡구현 피지컬을 요구하는 문제도 더러 있음.

 

 

ex)

- 사탕 게임 : https://www.acmicpc.net/problem/3085
- 날짜 계산 : https://www.acmicpc.net/problem/1476
- 테트로미노 : https://www.acmicpc.net/problem/14500
- 카잉 달력 : https://www.acmicpc.net/problem/6064
- 수 이어 쓰기 1 : https://www.acmicpc.net/problem/1748

 

테트로미노 예시 코드.

tets 요소중에 하나 잘못 적어서 삑나면 그때부터 머리아픔.

#include <iostream>

using namespace std;

int tets[19][4][2] = {
    // ㅡ
    {{0, 0}, {0, 1}, {0, 2}, {0, 3}},
    {{0, 0}, {1, 0}, {2, 0}, {3, 0}},
    // ㅁ
    {{0, 0}, {0, 1}, {1, 0}, {1, 1}},
    // L
    {{0, 0}, {1, 0}, {2, 0}, {2, 1}},
    {{0, 1}, {1, 1}, {2, 1}, {2, 0}},
    {{0, 0}, {1, 0}, {0, 1}, {0, 2}},
    {{0, 0}, {0, 1}, {0, 2}, {1, 2}},
    {{0, 0}, {0, 1}, {1, 0}, {2, 0}},
    {{0, 0}, {0, 1}, {1, 1}, {2, 1}},
    {{0, 0}, {1, 0}, {1, 1}, {1, 2}},
    {{1, 0}, {1, 1}, {1, 2}, {0, 2}},
    //Z
    {{0, 0}, {1, 0}, {1, 1}, {2, 1}},
    {{0, 1}, {1, 1}, {1, 0}, {2, 0}},
    {{1, 0}, {1, 1}, {0, 1}, {0, 2}},
    {{0, 0}, {0, 1}, {1, 1}, {1, 2}},

    // ㅜ
    {{0, 0}, {0, 1}, {1, 1}, {0, 2}},
    {{1, 0}, {0, 1}, {1, 1}, {1, 2}},
    {{0, 0}, {1, 0}, {1, 1}, {2, 0}},
    {{1, 0}, {0, 1}, {1, 1}, {2, 1}},
};

int board[500][500];

int main(void)
{
  int N, M, k, nx, ny, cand, largest = 0;

  cin >> N;
  cin >> M;

  for (int i = 0; N > i; i++)
    for (int j = 0; M > j; j++)
    {
      cin >> k;
      board[i][j] = k;
    }

  for (int x = 0; N > x; x++)
    for (int y = 0; M > y; y++)
      for (int figIdx = 0; 19 > figIdx; figIdx++)
      {
        cand = 0;
        for (int pos = 0; 4 > pos; pos++)
        {
          nx = x + tets[figIdx][pos][0];
          ny = y + tets[figIdx][pos][1];

          if (nx < 0 || ny < 0 || nx >= N || ny >= M)
            break;

          cand += board[nx][ny];
        }
        if (!cand)
          continue;

        largest = max(largest, cand);
      }

  cout << largest << '\n';

  return 0;
}