백준 14500번 : 테트로미노 자바

 

 

🧫 문제 분석

 

✔️ 출처

테트로미노 골드 4

 

📖 문제

 

완전탐색 + 백트래킹 문제다. 

 

5가지중 가운데 볼록한 모양을 제외하곤

상하좌우로 탐색하며 탐색한 깊이가 4이면 테트로미노가 만들어진다. 이때 각 수를 max와 비교한다. 

 

가운데 볼록한 모양(키보드 방향키 모양) 은 현 위치에서 상하좌우 4개중 3개를 뽑아서 처리한다. 

 

예를 들어 

dx, dy 0, 1, 2 번째 인덱스를 탐색하라고 "012 " 문자열을 만들어서 저장해놓는다는 것이다. 

현재 위치에서 dx, dy 만큼 더한 인덱스에 접근하면 

ㅓ 모양이 나온다. 

 

---

🔅 문제 풀이

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

public class Main {

    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int[][] graph;
    static boolean[][] visited;
    static ArrayList<String> list = new ArrayList<>();
    static int max = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        graph = 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++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }


        // 가운데 볼록 모양 인덱스 만들기
        for (int i = 0; i < 2; i++) {
            for (int j = i + 1; j < 3; j++) {
                for (int k = j + 1; k < 4; k++) {
                    sb.append(i).append(j).append(k);
                    list.add(sb.toString());
                    sb.delete(0, sb.length());
                }
            }
        }

        // 테트로미노 탐색
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph[i].length; j++) {
                visited[i][j] = true;
                recursion(i, j, 1, 0);
                findArrowShape(i,j);
                visited[i][j] = false;
            }
        }


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

    }

    private static void findArrowShape(int r, int c) {
        int tmp;

        for (String seq : list) {
            tmp = graph[r][c];
            for (int i = 0; i < seq.length(); i++) {
                int idx = seq.charAt(i) - '0';

                int nextRow = r + dy[idx];
                int nextCol = c + dx[idx];

                // 범위를 벗어나면 넘긴다.
                if (nextRow < 0 || nextRow >= graph.length
                        || nextCol < 0 || nextCol >= graph[0].length) continue;

                tmp += graph[nextRow][nextCol];
            }

            max = Math.max(max, tmp);
        }

    }


    private static void recursion(int r, int c, int depth, int cost) {
        if (depth == 4) {
            max = Math.max(max, cost + graph[r][c]);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nextRow = r + dy[i];
            int nextCol = c + dx[i];

            // 범위를 벗어나면 넘기기
            if (nextRow < 0 || nextRow >= graph.length
                    || nextCol < 0 || nextCol >= graph[0].length) continue;

            // 방문 했다면 넘기기
            if (visited[nextRow][nextCol]) continue;

            visited[nextRow][nextCol] = true;
            recursion(nextRow, nextCol, depth + 1, cost + graph[r][c]);
            visited[nextRow][nextCol] = false;
        }

    }

}

 

 

 

❗ 오답노트 / 필요한 지식

1.  어렵지 않은 문제인데 저 키보드 방향키 모양때문에 인덱스 조합 이상하게 만들어서 좀 걸렸다.