[백준][C++] 14500: 테트로미노

문제 링크: https://www.acmicpc.net/problem/14500

 

이건 뭐 별 내용 아니지만 전 테트리스를 좋아합니다. 잘하구요. 옛날에 한게임 테트리스 할 때 정말 재밌게 했는데.. 서버 닫았을 때 참 슬펐습니다. 증말 재밌게 했거든요

그 때 이벤트로 받은 열쇠고리인데 진짜 희귀템입니다. 허허

 

테트로미노(테트리스 컴퍼니는 테트리미노라고 부릅니다) 종류는 이렇게 7종류가 있고요, 각각의 색은 민트, 노랑, 보라 등 규정으로 정해져 있습니다.

 

 

서론이 좀 길었네요..

이 문제는 완전탐색으로 풀어야 합니다. 모든 모양(회전 포함)을 체크하는 노가다를 하셔도 되지만 전 손이 아프니 dfs로 짰습니다.

그런데 주의할 점이 있는데 dfs로 짤 때 T미노(위 사진 보라색)를 생각하셔서 dfs 코드를 작성해주셔야 합니다. 그냥 dfs 상하좌우로 움직이는 것만 하면 T자 경로가 나올수 없죠?

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

enum DIRECTION {
  UP,
  RIGHT,
  DOWN,
  LEFT
};

int n, m;
int arr[500][500];
int max_sum;
const int dir[][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };  //y, x


bool is_ok(int y, int x) {
  return (y>=0 && y<n && x>=0 && x<m);
}

void dfs(vector<pair<int, int>>& visited, int sum) {
  // base
  if (visited.size() == 4) {
    max_sum = max(max_sum, sum);
    return;
  }
  else if (visited.size() == 2) {
    //ㅗ 모양 테트리미노 처리
    //visited 가로모양일 때
    int next_y_1, next_x_1, next_y_2, next_x_2;
    if (visited[0].first == visited[1].first) {
      //ㅏ
      next_y_1 = visited[0].first  + dir[DIRECTION::UP][0];
      next_x_1 = visited[0].second + dir[DIRECTION::UP][1];
      next_y_2 = visited[0].first  + dir[DIRECTION::DOWN][0];
      next_x_2 = visited[0].second + dir[DIRECTION::DOWN][1];

      if (is_ok(next_y_1, next_x_1) && is_ok(next_y_2, next_x_2)) {
        visited.push_back(make_pair(next_y_1, next_x_1));
        visited.push_back(make_pair(next_y_2, next_x_2));
        dfs(visited, sum + arr[next_y_1][next_x_1] + arr[next_y_2][next_x_2]);
        visited.pop_back();
        visited.pop_back();
      }

      //ㅓ
      next_y_1 = visited[1].first  + dir[DIRECTION::UP][0];
      next_x_1 = visited[1].second + dir[DIRECTION::UP][1];
      next_y_2 = visited[1].first  + dir[DIRECTION::DOWN][0];
      next_x_2 = visited[1].second + dir[DIRECTION::DOWN][1];

      if (is_ok(next_y_1, next_x_1) && is_ok(next_y_2, next_x_2)) {
        visited.push_back(make_pair(next_y_1, next_x_1));
        visited.push_back(make_pair(next_y_2, next_x_2));
        dfs(visited, sum + arr[next_y_1][next_x_1] + arr[next_y_2][next_x_2]);
        visited.pop_back();
        visited.pop_back();
      }
    }
    else {
      //ㅜ
      next_y_1 = visited[0].first  + dir[DIRECTION::LEFT][0];
      next_x_1 = visited[0].second + dir[DIRECTION::LEFT][1];
      next_y_2 = visited[0].first  + dir[DIRECTION::RIGHT][0];
      next_x_2 = visited[0].second + dir[DIRECTION::RIGHT][1];

      if (is_ok(next_y_1, next_x_1) && is_ok(next_y_2, next_x_2)) {
        visited.push_back(make_pair(next_y_1, next_x_1));
        visited.push_back(make_pair(next_y_2, next_x_2));
        dfs(visited, sum + arr[next_y_1][next_x_1] + arr[next_y_2][next_x_2]);
        visited.pop_back();
        visited.pop_back();
      }

      //ㅗ
      next_y_1 = visited[1].first  + dir[DIRECTION::LEFT][0];
      next_x_1 = visited[1].second + dir[DIRECTION::LEFT][1];
      next_y_2 = visited[1].first  + dir[DIRECTION::RIGHT][0];
      next_x_2 = visited[1].second + dir[DIRECTION::RIGHT][1];

      if (is_ok(next_y_1, next_x_1) && is_ok(next_y_2, next_x_2)) {
        visited.push_back(make_pair(next_y_1, next_x_1));
        visited.push_back(make_pair(next_y_2, next_x_2));
        dfs(visited, sum + arr[next_y_1][next_x_1] + arr[next_y_2][next_x_2]);
        visited.pop_back();
        visited.pop_back();
      }
    }
  }

  auto curr = visited.back();
  for (int i = 0; i < 4; ++i) {
    auto next_y = curr.first + dir[i][0],
      next_x = curr.second + dir[i][1];
    auto next = make_pair(next_y, next_x);
    if (is_ok(next_y, next_x) && find(visited.begin(), visited.end(), next)==visited.end()) {
      visited.push_back(next);
      dfs(visited, sum + arr[next_y][next_x]);
      visited.pop_back();
    }
  }
}


int main(int argc, char** argv)
{
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
#endif

  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      cin >> arr[i][j];
    }
  }

  max_sum = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      vector<pair<int, int>> v{ make_pair(i, j) };
      dfs(v, arr[i][j]);
    }
  }
  cout << max_sum;

  return 0;
}

제 코드인데요, T미노 처리때문에 코드가 좀 드러워 보이네요. 정리는 귀찮아서 생략했습니다

사실 이렇게 짜는 것보다 노가다 해서 모든 좌표에서 테트로미노 모양 별 계산하는게 더 빠릅니다. dfs 함수스택이랑 visited 계산 등등 때문에 그런 것 같네요.