백준 14500번 : 테트로미노(Java)

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

14500번: 테트로미노

---

[풀이]

• 'ㅜ'자 모양은 DFS로 탐색하는 것이 불가능 하지만, 그 외의 모양은 DFS로 탐색이 가능합니다.
• 그렇기에, 'ㅜ'자는 별개의 메소드로 값을 구하고, 다른 모양들은 DFS를 통해 값을 구했습니다.
• total 변수가 4일 경우에는 탐색을 멈추도록 했습니다.
• 별개의 메소드로 'ㅜ'를 구할 때 모양이 돌아가는 경우도 고려해서 조건문을 구현했습니다.
• N과 M , x와 y에 헷갈리지 않도록 메소드를 구현해야 합니다.
  
  
• 제대로 풀지 못해서 주말에 다시 풀 예정!

---

[코드]

 

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

public class Main {
    static int N, M, answer;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {-1, 1, 0, 0,};

    static void dfs(int y, int x, int total, int sum) {
        if (total == 4) {
            answer = Math.max(answer, sum);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if (nextX < 0 || nextX >= M || nextY < 0 || nextY >= N)
                continue;
            if (visited[nextY][nextX])
                continue;

            visited[nextY][nextX] = true;
            dfs(nextY, nextX, total + 1, sum + arr[nextY][nextX]);
            visited[nextY][nextX] = false;


        }
    }

    static void exception(int y, int x) {
        if (y - 1 >= 0 && x - 1 >= 0 && x + 1 < M) {
            int temp1 = arr[y][x] + arr[y][x - 1] + arr[y][x + 1] + arr[y - 1][x];
            answer = Math.max(answer, temp1);
        }
        if (x - 1 >= 0 && x + 1 < M && y + 1 < N) {
            int temp2 = arr[y][x] + arr[y][x - 1] + arr[y][x + 1] + arr[y + 1][x];
            answer = Math.max(answer, temp2);
        }
        if (x + 1 < M && y + 1 < N && y - 1 >= 0) {
            int temp3 = arr[y][x + 1] + arr[y - 1][x] + arr[y + 1][x] + arr[y][x];
            answer = Math.max(answer, temp3);
        }
        if (x - 1 >= 0 && y - 1 >= 0 && y + 1 < N) {
            int temp4 = arr[y][x - 1] + arr[y - 1][x] + arr[y + 1][x] + arr[y][x];
            answer = Math.max(answer, temp4);
        }
    }

    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());
        answer = 0;
        arr = 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++) {
                arr[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, 0, 0);
                visited[i][j] = false;
                exception(i, j);
            }
        }

        System.out.println(answer);
    }
}