[백준] 14500번 테트로미노 Java 풀이

PROBLEM

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

SOLUTION

테트로미노에 해당하는 도형들 중 ㅗ 모양을 제외한 나머지 4개는 DFS로 탐색 가능하다. 각 도형은 회전이나 대칭이 가능하므로 깊이를 4까지 제한을 두고 DFS를 하면 된다.

ㅗ 모양은 추가적으로 처리해준다. 회전이나 대칭을 하면 ㅗ, ㅏ, ㅓ, ㅜ 모양이 되며 이 4가지에 대해서도 계산을 해야한다. 아래 코드에서 이러한 모양들에 대해서 oh라는 이름으로 사용한다.

(0, 0)부터 (N, M)까지 각 좌표에 대해서 깊이 4만큼 DFS도 하고, ㅗ 모양도 확인하면 모든 테트로미노를 탐색할 수 있고, 최대값을 찾을 수 있다.

SOURCE CODE (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

import java.io.*;
import java.util.*;

public class Main {
  static int N, M, answer;
  static int[][] map;
  static boolean[][] visited;

  // ㅗ에서 꼬다리를 기준으로 4칸의 상대적 좌표
  static int[][][] OH = {
      { { 0, 0 }, { 1, -1 }, { 1, 0 }, { 1, 1 } },   // ㅗ
      { { 0, 0 }, { -1, -1}, { 0, -1}, { 1, -1} },   // ㅏ
      { { 0, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 } },   // ㅓ
      { { 0, 0 }, { -1, -1}, { -1, 0}, { -1, 1} },   // ㅜ
  };
  // 4방탐색 좌표
  static int[] dr = { -1, 1, 0, 0 };
  static int[] dc = { 0, 0, -1, 1 };

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk;

    stk = new StringTokenizer(br.readLine());
    N = Integer.parseInt(stk.nextToken());
    M = Integer.parseInt(stk.nextToken());

    map = new int[N][M];
    visited = new boolean[N][M];
    for (int i = 0; i < N; i++) {
      stk = new StringTokenizer(br.readLine());
      for (int j = 0; j < M; j++) {
        map[i][j] = Integer.parseInt(stk.nextToken());
      }
    }

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        // 각 좌표별로, 4칸만 DFS (ㅗ를 제외한 나머지 확인 가능)
        visited[i][j] = true;
        dfs(i, j, 0, 0);
        visited[i][j] = false;

        // ㅗ 확인
        checkOh(i, j);
      }
    }

    System.out.println(answer);
  }

  private static void checkOh(int r, int c) {
    for (int i = 0; i < 4; i++) {
      int[][] oh = OH[i];             // ㅗ, ㅓ, ㅏ, ㅜ 중 하나
      int result = 0;

      for (int j = 0; j < 4; j++) {   // (r,c)를 기준으로 ㅗ를 만드는데
        int nr = r + oh[j][0];
        int nc = c + oh[j][1];
        if (isOut(nr, nc))  break;    // 범위를 벗어나면 빠져나가

        result += map[nr][nc];        // 해당 모양의 점수 확인
      }

      answer = Math.max(result, answer);
    }
  }

  private static boolean isOut(int r, int c) {
    return r < 0 || r >= N || c < 0 || c >= M;
  }

  private static void dfs(int r, int c, int depth, int score) {
    if (depth == 4) {
      answer = Math.max(answer, score);
      return;
    }

    // DFS 하면서 점수 누적
    score += map[r][c];

    for (int d = 0; d < 4; d++) {
      int nr = r + dr[d];
      int nc = c + dc[d];
      if (isOut(nr, nc))    continue;
      if (visited[nr][nc])  continue;

      visited[nr][nc] = true;
      dfs(nr, nc, depth + 1, score);
      visited[nr][nc] = false;
    }
  }
}

OFF THE RECORD

DFS를 이용할 수 있다는 것까지는 파악했으나, ㅗ 모양 처리를 예외적으로 처리하는 방식을 생각하지 못해 다른 사람들의 풀이를 참조했다. DFS를 사용하는 코드들을 보면 처음에 DFS를 호출할 때, 현재 좌표를 포함하는 코드와 포함하지 않는 코드가 있었다.

나는 당연히 좌표를 순회하면서 ‘현재 좌표로부터 이어지는(현재 좌표를 포함하는) 4칸을 확인한다’ 라고 이해하며 따라했다가 ‘이게 왜 돌아가지’라며 헤맸다. 어설프게 따라했다가 시간낭비한 것이다.

차이점은 “처음 dfs를 호출할 때 현재 좌표를 visited처리를 해주느냐”, 그리고 “dfs 함수 내에서 점수에 누적하는 것은 이동할 좌표인가 현재 좌표인가”이다.

아래 코드는 참조한 코드와 내 코드의 다른 점에 해당하는 부분만 가져왔다. 주석처리 한 부분이 내 코드이고, 그렇지 않은 부분이 참조한 코드의 로직이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

  // main에서 처음 dfs를 호출할 때,
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      //// 내 코드
      // visited[i][j] = true;
      // dfs(i, j, 0, 0);
      // visited[i][j] = false;
      //// 내 코드

      //// 참조한 코드
      dfs(i, j, 0, 0);
      //// 참조한 코드

      checkOh(i, j);
    }
  }

  // dfs 함수
  private static void dfs(int r, int c, int depth, int score) {
    if (depth == 4) {
      answer = Math.max(answer, score);
      return;
    }

    //// 내 코드
    // score += map[r][c];
    //// 내 코드

    for (int d = 0; d < 4; d++) {
      int nr = r + dr[d];
      int nc = c + dc[d];
      if (isOut(nr, nc))    continue;
      if (visited[nr][nc])  continue;

      visited[nr][nc] = true;

      //// 내 코드
      // dfs(nr, nc, depth + 1, score);
      //// 내 코드

      //// 참조한 코드
      dfs(nr, nc, depth + 1, score+map[nr][nc]);
      //// 참조한 코드

      visited[nr][nc] = false;
    }
  }
  • 참조한 코드는 현재 좌표를 포함하지 않는 4칸을 탐색한다.
  • 내 코드는 현재 좌표를 포함하는 4칸을 탐색한다.

두 코드 모두 정답이 되는 것을 확인했으며, 시간 차이는 근소하게 내 코드가 앞섰다. 위에가 참조한 코드, 아래가 내 코드를 제출한 결과이다. 코드제출결과

확실하게 로직을 이해하고 DFS를 사용해야 헤메지 않을 수 있다.

댓글 남기기

관련있는 다른 게시글