[백준 14500번] JAVA 테트로미노

풀이

 

처음에는 이런 유형의 문제를 처음 봤기 때문에, 도형을 만들고, 각각 돌려서 확인을 해야 하는지, 어떻게 확인을 할 수 있을지 감이 안 왔다. 구현해보려고 끄적이다가 답이 도저히 안 나와서 구글링을 통해 약간의 힌트를 얻었다.

 

보니 각 도형들의 크기는 네개의 칸으로 구성되어 있고, 상하좌우로 이동했을 때 보라색 테트로미노를 뺀 네 개의 도형을 만들 수 있었다. 즉 dfs, bfs 문제의 응용 버전이었던 것이다.

 

본인은 bfs로 구현하였고, 맵의 각 위치마다 depth가 4개인 모든 도형을 만들어 합을 비교하였다.

n과 m은 최대 500칸이고, 칸마다 dfs로 구현했을 때 만들어지는 최대 가짓수는 4^3 보라색 테트로미노를 제외한 테트로미노를 모든 칸에서 만든다고 가정했을 때 500*500 *64 즉 완전 탐색을 하더라도 16,000,000 이므로 요구사항인 2초 안에 가능하다.

 

private static void dfs(int x, int y, int depth, int sum) {
   if (depth == 4) {
      max = Math.max(max, sum);
      return;
   }

   for (int i = 0; i < 4; i++) {
      int tx = dx[i] + x;
      int ty = dy[i] + y;
      if (tx < 0 || tx >= n || ty < 0 || ty >= m || visit[tx][ty]) {
         continue;
      }
      visit[tx][ty] = true;
      dfs(tx, ty, depth + 1, sum + map[tx][ty]);
      visit[tx][ty] = false;
   }
}

 

dfs는 다른 문제와 다를 거없이 방문하지 않았을 경우에 다른 칸으로 이동하여 depth가 4일 때까지 만들었다.

보라색 테트로미노는 두 번째 칸에서 두 개의 칸을 이동을 해야하지만, 그림과 같이 가운데를 중심을 두고 세 개를 갈 수 있다면 도형을 만드는 방식으로 만들었다.

 

private static void makePurple(int start, int x, int y, int depth, int sum) {
   if (depth == 4) {
      max = Math.max(max, sum);
      return;
   }

   for (int i = start; i < 4; i++) {
      int tx = dx[i] + x;
      int ty = dy[i] + y;
      if (tx < 0 || tx >= n || ty < 0 || ty >= m || visit[tx][ty]) {
         continue;
      }
      makePurple(i + 1, x, y, depth + 1, sum + map[tx][ty]);
   }
}

 

좌표 x,y는 가만히 두고, visit과 상관없이 start로 상하좌우를 순서대로 구현하면, 중복이 되지 않는다. 순차적인 조합, 중복되지 않는 조합을 할 때도 가끔 응용한다.

 

전체 풀이

import java.util.Scanner;

public class Main {

   private static int[] dx = {1, -1, 0, 0};
   private static int[] dy = {0, 0, 1, -1};
   private static int[][] map;
   private static boolean[][] visit;
   private static int n;
   private static int m;
   private static int max = 0;

   public static void main(String[] args) {
      Scanner s = new Scanner(System.in);
      n = s.nextInt();
      m = s.nextInt();
      map = new int[n][m];
      visit = new boolean[n][m];
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
            map[i][j] = s.nextInt();
         }
      }

      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
            visit[i][j] = true;
            dfs(i, j, 1, map[i][j]);
            visit[i][j] = false;
            makePurple(0, i, j, 1, map[i][j]);
         }
      }
      System.out.println(max);
   }

   private static void makePurple(int start, int x, int y, int depth, int sum) {
      if (depth == 4) {
         max = Math.max(max, sum);
         return;
      }

      for (int i = start; i < 4; i++) {
         int tx = dx[i] + x;
         int ty = dy[i] + y;
         if (tx < 0 || tx >= n || ty < 0 || ty >= m || visit[tx][ty]) {
            continue;
         }
         makePurple(i + 1, x, y, depth + 1, sum + map[tx][ty]);
      }
   }

   private static void dfs(int x, int y, int depth, int sum) {
      if (depth == 4) {
         max = Math.max(max, sum);
         return;
      }

      for (int i = 0; i < 4; i++) {
         int tx = dx[i] + x;
         int ty = dy[i] + y;
         if (tx < 0 || tx >= n || ty < 0 || ty >= m || visit[tx][ty]) {
            continue;
         }
         visit[tx][ty] = true;
         dfs(tx, ty, depth + 1, sum + map[tx][ty]);
         visit[tx][ty] = false;

      }
   }
}