[C++] 백준 14500 : 테스토미노

#include <iostream>
#include <algorithm> // max
using namespace std;

int map[501][501]; // 0부터 시작
bool visited[501][501] = {false}; // 테스토미노

// 상하좌우 탐색
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int Max = -1; // 최댓값

int N, M; // 세로, 가로

// ㅗㅜㅏㅓ는 DFS로 탐색 불가능
void testimony(int x, int y){ // x, y 는 가운데 좌표
  //세로 : x, 가로 : y, 조건문 잘 쓰기 모두 만족해야할 때는 &&

  //ㅗ
  if(x - 1 >= 0 && y - 1 >= 0 && y + 1 < M){
    Max = max(Max, map[x-1][y] + map[x][y-1] + map[x][y] + map[x][y+1]);
  }
  //ㅜ
  if(x + 1 < N && y - 1 >= 0 && y + 1 < M){
    Max = max(Max, map[x+1][y] + map[x][y] + map[x][y-1] + map[x][y+1]);
  }
  //ㅏ
  if(x - 1 >= 0 && x + 1 < N && y + 1 < M){
    Max = max(Max, map[x-1][y] + map[x+1][y] + map[x][y] + map[x][y+1]);
  }
  //ㅓ  
  if(x - 1 >= 0 && x + 1 < N && y - 1 >= 0){
    Max = max(Max, map[x-1][y] + map[x+1][y] + map[x][y] + map[x][y-1]);
  }

  return;
}

void DFS(int x, int y, int sum, int cnt){
  if(cnt == 4){ // 테스토미노 사각형 4개로 구성

    // printf("******\n");
    // for(int i=0; i<N; i++){
    //   for(int j=0; j<M; j++){
    //     printf("%d ", visited[i][j]);
    //   }
    //   printf("\n");
    // }
    
    // 시간 초과된 값 찾기 코드
    // int tmp = 0;
    // for(int i=0; i<N; i++){
    //   for(int j=0; j<M; j++){
    //     if(visited[i][j]){
    //       tmp += map[i][j]; // 테스토미노 값 찾기
    //     }
    //   }
    // }

    Max = max(Max, sum); // 최댓값 저장
    return;
  }

  for(int i = 0; i < 4; i++){
    int nx = x + dx[i];
    int ny = y + dy[i];

    if(nx < 0 || ny < 0 || nx >= N || ny >= M){
      continue; // 맵 초과시
    }

    if(!visited[nx][ny]){
      visited[nx][ny] = true;
      DFS(nx, ny, sum + map[nx][ny], cnt + 1);
      visited[nx][ny] = false; // 초기화
    }
  }
}

int main(){
  scanf("%d %d", &N, &M);

  for(int i=0; i<N; i++){
    for(int j=0; j<M; j++){
      scanf("%d", &map[i][j]); // 맵 입력받기
    }
  }

  for(int i=0; i<N; i++){
    for(int j=0; j<M; j++){
      visited[i][j] = true;
      DFS(i, j, map[i][j], 1); // 모든 시작점에 대해서 찾기
      testimony(i, j); // ㅗ 모양 찾기
      visited[i][j] = false; // 초기화
    }
  }

  printf("%d", Max); // 최댓값 출력

  return 0;
}

• 원래 인접한 사각형으로 테스토미노가 이어지기 때문에 BFS를 사용하려고 했지만 브루트포스로 모든 경우의 값을 찾아야하기에 전역 큐를 사용하면 원하는대로 값이 잘 나오지 않았다. 때문에 DFS를 사용하게 되었다.

• ㅗ,ㅜ,ㅓ,ㅏ 의 경우에는 DFS로 찾을 수 없다. 따라서 좌표를 직접 지정하여 해당 경우를 따로 찾아주어야한다. 이 때 조건을 잘 찾아야한다. 여기서 조건문을 잘못 세워서 꽤 틀렸다. x, y의 순서로 배열을 사용하면 세로가 x, 가로가 y가 된다. 헷갈리지 말자.

• 값의 합을 DFS에서 구할때는 이것도 재귀 함수의 매개 변수로 넘겨주는 것이 for문으로 다시 탐색을 하는 것보다 시간이 적게 걸린다.

• 모든 점에서 테스토미노의 시작점으로 두고 찾아야하기 때문에 브루트포스 알고리즘을 이용했다고 볼 수 있다. DFS에서 방문 여부를 사용하되 초기화 시켜야한다면 DFS 호출의 전 후 코드에 방문 여부를 체크하고 다시 초기화시켜주면 된다.