[백준 14500번] 자바 테트로미노 lv > gold4

 

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

14500번: 테트로미노

 

문제 설명

예제 입력 1 복사

5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1

예제 출력 1 복사

19

예제 입력 2 복사

4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

예제 출력 2 복사

20

예제 입력 3 복사

4 10
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1

예제 출력 3 복사

7

문제 해석

여기서 우리가 주목해야할 것은 두가지이다.

1. 대칭 및 회전이 상관 없다는 점

2. ㅏ, ㅓ, ㅗ, ㅜ 모양은 두번째 점에서 다시 탐색을 해야한다는 점

 

이것만 유의해두면 의외로 쉬운 문제였다!

 

 

* 실패한 구현 로직 *

1. board 행렬에서 제일 최대값을 찾는다.

2. 거기서 부터 완전탐색을 진행한다.

 

왜 틀렸느냐? 만일 최대값이 가운데에 있는 경우 뒤에서부터 완전탐색하는것이 더 좋은 경우도 있는데 나는 그런 경우를 막아놨으니 실패한 것 같다.. ㅎㅎ 

진짜 row, col별로 처음부터 완전탐색으로 변경해보기로 했다!!

실패한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ14500{

    static int N;
    static int M;
    static int[][] board;
    static boolean[][] visited;
    static int[] maxPoint = new int[2];
    static int maxValue = Integer.MIN_VALUE;
    static int maxSum = 0;
    static int[] dr = {1, 0, -1, 0};
    static int[] dc = {0, 1, 0, -1};



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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = new int[N][M];
        visited = new boolean[N][M];
        int initsum = 0;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if (maxValue < board[i][j]) {
                    maxValue = board[i][j];
                    maxPoint[0] = i;
                    maxPoint[1] = j;
                    initsum = board[i][j];
                }
            }
        }
        visited[maxPoint[0]][maxPoint[1]] = true;
        dfs(maxPoint[0], maxPoint[1], initsum, 1);

        System.out.println(maxSum);
    }

    public static void dfs(int row, int col, int sum, int cnt) {
        if (cnt == 4) {
            maxSum = Math.max(maxSum, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int rNext = row + dr[i];
            int cNext = col + dc[i];

            if (rNext < 0 || rNext >= N || cNext < 0 || cNext >= M) {
                continue;
            }

            if (!visited[rNext][cNext]) {
                int tmpSum = sum + board[rNext][cNext];
                if (cnt == 2) { // ㅗ, ㅓ, ㅏ, ㅜ 와 같은 모양은 연속적인 완전탐색이 아니라 두번째 칸에서 다시 시작해줘야함.
                    visited[rNext][cNext] = true;
                    dfs(row, col, tmpSum, cnt + 1);
                    visited[rNext][cNext] = false;
                }

                visited[rNext][cNext] = true;
                dfs(rNext, cNext, tmpSum, cnt + 1);
                visited[rNext][cNext] = false;
            }
        }
    }
}

 

* retry 구현 로직 *

1. 처음부터 완전탐색을 진행

retry 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ14500{

    static int N;
    static int M;
    static int[][] board;
    static boolean[][] visited;
    static int maxSum = 0;
    static int[] dr = {1, 0, -1, 0};
    static int[] dc = {0, 1, 0, -1};



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

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

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                initsum = board[i][j];
                visited[i][j] = true;
                dfs(i, j, initsum, 1);
                visited[i][j] = false;
            }
        }
        System.out.println(maxSum);
    }

    public static void dfs(int row, int col, int sum, int cnt) {
        if (cnt == 4) {
            maxSum = Math.max(maxSum, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int rNext = row + dr[i];
            int cNext = col + dc[i];

            if (rNext < 0 || rNext >= N || cNext < 0 || cNext >= M) {
                continue;
            }

            if (!visited[rNext][cNext]) {
                int tmpSum = sum + board[rNext][cNext];
                if (cnt == 2) { // ㅗ, ㅓ, ㅏ, ㅜ 와 같은 모양은 연속적인 완전탐색이 아니라 두번째 칸에서 다시 시작해줘야함.
                    visited[rNext][cNext] = true;
                    dfs(row, col, tmpSum, cnt + 1);
                    visited[rNext][cNext] = false;
                }

                visited[rNext][cNext] = true;
                dfs(rNext, cNext, tmpSum, cnt + 1);
                visited[rNext][cNext] = false;
            }
        }
    }
}

 

참고로 내 풀이법이 맞는 것 같은데 반례도 마땅히 생각나지 않을 땐 해당 문제의 게시판 내용을 잘 훑어보자!

https://www.acmicpc.net/board/view/119217 

글 읽기 - << 테케 공유 >>