[백준] 14500번 - 테크로미노 (★) (JAVA)

[백준] 14500번 - 테크로미노 (!) (JAVA)

---

[접근 방법]

 

브루트포스 파트이기에 모든 경우의 수를 탐색해야 한다는 것은 알고있었다.

어떻게 탐색 할 것인가? 가 가장 어려웠다.

 

첫번째로 고려한 방법은 모든 경우를 일일이 생각하여 구현하는 방법이다.

(i , j)를 시작으로 하는 모든 경우의 수를 전부 고려한 후, 그중 최댓값을 구해서 N X M 보드의 모든 칸의 최대값을 비교하여 갱신할 계획이였다.

worst case = 500 * 500 * 13 = 3,250,000 으로 시간도 적합했다.

그러나 너무나 까다롭고 귀찮은 구현에 포기하였다.

 

두번째 고려한 방법은 다른 사람들의 풀이 방법을 보고 풀었다.

위 4가지 도형은 상하좌우 완전 탐색으로 구현하고, 

이 모형만 따로 구현하는 방법이다.

 

탐색중인 현재 위치와 이전까지 의 누적합, 탐색한 블럭수를 매개 변수로 받는 함수를 생성한 후,

해당 위치로 부터 상하좌우 값을 재귀적으로 탐색한다.

 

ㅜ 모형은 탐색한 블럭 수가 2인 경우, 현재 위치에서 다시 탐색을 하는 방식으로 구현하였다.

코드는 아래와 같다.

---

[JAVA 코드]

// 14500번 - 테트로미노
import java.util.*;
import java.io.*;

public class Main {

    static int N, M;
    static int[][] arr;
    static int max = Integer.MIN_VALUE;
    // 상하좌우 이동을 위한 배열
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};

    // 방문한적 있는지 판단
    static boolean[][] visit;

    // (row, col) : 위치, sum : 현재합, count : 현재 탐색한 블럭 수
    public static void dfs(int row, int col, int sum, int count){
        // 블럭 4개 탐색 => 탐색 끝
        if(count == 4){
            max = Math.max(max, sum);
            return;
        }

        // 상하좌우 블럭 4개 탐색
        for(int i=0; i<4; i++){
            int curRow = row + dx[i];
            int curCol = col + dy[i];

            // 보드 범위를 넘어가면 pass
            if (curRow < 0 || curRow >= N || curCol < 0 || curCol >= M){
                continue;
            }

            // 방문하지 않은 블럭
            if (!visit[curRow][curCol]){

                // ㅏ 모양 탐색
                if(count == 2){
                    visit[curRow][curCol] = true;
                    dfs(row, col, sum + arr[curRow][curCol], count + 1);
                    visit[curRow][curCol] = false;
                }

                visit[curRow][curCol] = true;
                dfs(curRow, curCol, sum + arr[curRow][curCol], count + 1);
                visit[curRow][curCol] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // row
        M = Integer.parseInt(st.nextToken()); // column
        arr = new int[N][M];
        visit = new boolean[N][M];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                visit[i][j] = true;
                dfs(i, j, arr[i][j], 1);
                visit[i][j] = false;
            }
        }

        bw.write(max + "\n");

        bw.flush();
        br.close();
        bw.close();      
    }
}

---

[Rewind]

 

1. 어려웠던 점

- 접근 방식 자체를 가늠할 수 없었다.

 - 다른 사람의 풀이를 보지 않았으면, 시작조차 할 수 없었다.

 

2. 알게된 점

- 단순 노가다 보단 창의적인 방식으로 해결해야 한다.

 

3. 개선 방향

- 비슷한 문제를 여러개 풀어야 한다.

- 창의적인 방식이 떠오를 수 있도록 다른 사람의 창의적은 풀이를 적극적으로 습득해야 한다.

---

[2회차 풀이]

// 14500번 - 테트로미노
import java.util.*;
import java.io.*;

public class Main {

    static int n, m;
    static boolean[][] visit; // 블럭 방문 여부
    static int[][] arr; // n * m 블럭
    static int max = Integer.MIN_VALUE; // 최댓값
    
    // 상하좌우
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    // 현재 위치 : (x, y) , 누적합 : sum, 탐색 블럭 수 : count
    public static void solve(int x, int y, int sum, int count){

        // 종료 조건 : 탐색한 블럭이 4개면 종료
        if (count == 4){
            max = Math.max(sum, max);
            return;
        }

        // 탐색 할 위치 (search_x, search_y)
        for(int i=0; i<4; i++){
            int search_x = x + dx[i];
            int search_y = y + dy[i];

            // 탐색 할 위치가 보드 영역을 벗어난 경우 : pass
            if (search_x < 0 || search_x >= n || search_y < 0 || search_y >= m){
                continue;
            }

            // 탐색할 블럭이 탐색되지 않은 곳인 경우
            if (!visit[search_x][search_y]){
                
                // 'ㅏ' 모양 고려
                if (count == 2){
                    visit[search_x][search_y] = true; // 탐색할 곳이니까 탐색했다고 표기
                    solve(x, y, sum + arr[search_x][search_y], count+1); // 제자리에서 탐색한번더
                    visit[search_x][search_y] = false; // 원상태 복원
                }

                visit[search_x][search_y] = true; 
                solve(search_x, search_y, sum + arr[search_x][search_y], count+1); 
                visit[search_x][search_y] = false; 
            }
        }
    }


    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // row
        m = Integer.parseInt(st.nextToken()); // column
        arr = new int[n][m];
        visit = new boolean[n][m];
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                visit[i][j] = true;
                solve(i, j, arr[i][j], 1);
                visit[i][j] = false;
            }
        }

        bw.write(max + "\n");
        
        bw.flush();
        br.close();
        bw.close();      
    }
}

느낀점 : 다시 풀어도 참 어려운 문제다.