[백준/Kotlin] 테트로미노(14500) + Java 코드 추가

문제

https://www.acmicpc.net/problem/14500

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

 

[ 입력 ]

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

 

[ 출력 ]

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

 

 

---

풀이

- 모든 위치에서 출발하는 경우를 계산해서 최대값 구하기 / dfs 이용

- ㅗ 모양일 때를 주의해서 풀이

 

// 백준 - 테트로미노(14500)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer
import kotlin.math.max

val dx = arrayOf(1, -1, 0, 0)
val dy = arrayOf(0, 0, 1, -1)

var N = 0
var M = 0
var maxSum = 0

var paper: Array<Array<Int>> = arrayOf()
var visited: Array<Array<Boolean>> = arrayOf()

fun main() {
  val br = BufferedReader(InputStreamReader(System.`in`))
  var st = StringTokenizer(br.readLine())

  N = st.nextToken().toInt()
  M = st.nextToken().toInt()

  paper = Array(N, {Array(M, {0})})
  visited = Array(N, {Array(M, {false})})

  for(i: Int in 0..N-1) {
    st = StringTokenizer(br.readLine())
    for(j: Int in 0..M-1) {
      paper[i][j] = st.nextToken().toInt()
    }
  }

  // 모든 지점에서 출발해보기
  for(i: Int in 0..N-1) {
    for(j: Int in 0..M-1) {
      visited[i][j] = true
      maxTetromino(i, j, paper[i][j], 1)
      visited[i][j] = false
    }
  }

  print(maxSum)
}

// 상하좌우 움직임으로 4개 정사각형 합 찾기
fun maxTetromino(x: Int, y: Int, sum: Int, cnt: Int) {
  // 테트로미노 완성
  if(cnt == 4) {
    maxSum = max(sum, maxSum) // 최대값 구하기
    return
  }

  for(i: Int in 0..3) {
    val moveX = x + dx[i]
    val moveY = y + dy[i]

    // 범위 벗어나면 패스
    if(moveX < 0 || moveX >= N || moveY < 0 || moveY >= M) continue

    // 현재 조합 중인 테트로미노 조각에 포함되지 않은 경우
    if(!visited[moveX][moveY]) {
      // ㅗ, ㅜ, ㅏ, ㅓ 모양 테트로미노는 중간에 양쪽으로 갈리기 때문에
      // 중간에 현재 위치에서 다른 방향으로 이동하도록
      if(cnt == 2) {
        visited[moveX][moveY] = true
        maxTetromino(x, y, sum + paper[moveX][moveY], cnt + 1)
        visited[moveX][moveY] = false
      }
      visited[moveX][moveY] = true
      maxTetromino(moveX, moveY, sum + paper[moveX][moveY], cnt + 1)
      visited[moveX][moveY] = false
    }
  }
}

 

 

+) 약 1년 전에 Java로 풀었던 코드가 있어서 함께 첨부 / 풀이 방법은 동일하다

// 백준 - 테트로미노(14500)
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  static int N, M;
  static int[][] paper;
  static boolean[][] visited;
  static int max = 0; // 최대값 저장

  // 상하좌우 이동
  static int[] dx = {-1, 1, 0, 0};
  static int[] dy = {0, 0, -1, 1};
  public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(bf.readLine());

    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());

    paper = new int[N][M];
    visited = new boolean[N][M];

    // 입력
    for(int i = 0; i < N; i++) {
      st = new StringTokenizer(bf.readLine());
      for(int j = 0; j < M; j++) {
        paper[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    // 모든 경우의 수 계산
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < M; j++) {
        visited[i][j]= true;
        maxTetromino(i, j, paper[i][j], 1);
        visited[i][j] = false;
      }
    }

    System.out.print(max);
  }

  // 상하좌우 움직임으로 4개 합 찾기
  static void maxTetromino(int x, int y, int sum, int cnt){
    // 테트로미노 모양 완성
    if(cnt == 4) {
      max = Math.max(sum, max);
      return;
    }

    // 상하좌우 탐색
    for(int i = 0; i < 4; i++) {
      int moveX = x + dx[i];
      int moveY = y + dy[i];

      // 범위 벗어나는지 확인 = 벗어나면 패스
      if(moveX < 0 || moveX >= N || moveY < 0 || moveY >= M) {
        continue;
      }

      // 방문하지 않았는지 체크
      if(!visited[moveX][moveY]) {
        // ㅗ 모양 테트로미노는 중간에 양쪽으로 갈리기 때문에 한 번 더 체크
        if(cnt == 2) {
          visited[moveX][moveY] = true;
          maxTetromino(x, y, sum + paper[moveX][moveY], cnt + 1); // 이동 후 위치 말고 현 위치로 전달
          visited[moveX][moveY] = false;
        }

        visited[moveX][moveY] = true;
        maxTetromino(moveX, moveY, sum + paper[moveX][moveY], cnt + 1);
        visited[moveX][moveY] = false;
      }
    }
  }
}