[백준_14500] 테트로미노.java

목차

1. 문제 해석
2. 사고 과정
3. 코드 구현
4. 회고록

---

문제 해석

폴리오미노 : 1X1 정사각형 이어 붙임
겹침 X, 도형 모두 연결, 변끼리만 연결

4개 이어 붙인-> 테트로미노
회전 or 대칭 가능
한 개의 테트로미노가 놓인 칸에 쓰혀 있는 수들의 합 최대

4 <= N, M <= 500

한 칸씩 조사할 때마다 5가지 경우의 수 돌려보면서
최대합 저장

 

---

사고 과정

한 개의 테트로미노에 대해 회전, 대칭, 모든 종류를 케이스별로 메서드 짜기엔 너무 무리
-> 완전 탐색 알고리즘 활용

그렇다면 DFS or BFS ?

ㅁ 모양과 ㅗ,ㅜ,ㅏ,ㅓ 모양에서 bfs의 경우 네 방향 완전탐색에서의 어려움이 있음

-> DFS 활용하기

**Point

ㅁ, ㅏ, ㅜ, ㅓ, ㅗ의 경우 각 이동 횟수가 2일 때, 추가로 네 방향 탐색을 시행해야만 한다

 

---

코드 구현

 

DFS의 응용

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

public class 테트로미노 {

    static int N, M, max;
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0}; //우하좌상

    static boolean[][] visited;
    static int[][] paper;

    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());
        paper = new int[N][M];
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.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; //방문 체크
                dfs(i, j, 1,paper[i][j]);
                visited[i][j] = false; //방문 체크 풀기
            }
        }
        System.out.println(max);
    }

    private static void dfs(int r, int c,int d, int score) { //가능한 커버 영역 3가지
        if(d ==4){ //이동 4번 했으면 그만!
            isMax(score);
            return;
        }

        for (int dir = 0; dir < 4; dir++) { //네 방향 완전 탐색
            int nr = r + dr[dir];
            int nc = c + dc[dir];

            if (nr >= N || nr < 0 || nc >= M || nc < 0) continue;
            if (visited[nr][nc]) continue;  // 범위, 방문 여부 확인

            if (d == 2) { //**가장 중요한 부분, 거리가 2일 경우 탐색 진행 추가 필요 
                visited[nr][nc] = true; 
                dfs(r,c,d+1,score+paper[nr][nc]); //
                visited[nr][nc] = false;
            }

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

        }
    }

    private static void isMax(int num) {
        if (max < num)
            max = num;
    }
}

---

회고록

DFS의 응용을 활용한 문제로 ㅏ,ㅗ,ㅓ,ㅜ 형태를 탐색함에 있어서 상당한 고난을 겪었음

 

✍ 중간에 ㅁ,ㅏ,ㅗ,ㅓ,ㅜ 형태를 탐색하는 메서드를 추가했지만 시간초과로 통과하지 못했고, 스스로도 코드에 대한 만족감이 안됐음, 결국 ㅁ,ㅏ,ㅗ,ㅓ,ㅜ 모두 거리가 2인 탐색에서 추가탐색을 진행해야 하는 공통점을 찾고, 이를 DFS형태로 구현

DFS 구현에 대한 이해도를 높이기에 훌륭한 문제