[boj] 백준 골드4 14500 테트로미노 (Java) - DFS

[문제]

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

14500번: 테트로미노

 

[풀이]

이전에 풀었던 코드. 

 

이전에는 ㅏ, ㅓ, ㅜ, ㅗ 모양에 대해 하드코딩을 했었다. 

그러나 하드코딩을 하지 않아도 2칸이 선택되었을 때, 3번째 칸에 대해서는 방문 표시만 해두고 다시 원래의 좌표인 r, c에서 dfs 탐색을 진행하면 위의 4가지 모양에 대해서도 테트로미노의 합을 구할 수 있다.

 

[코드]

 

package bfs_dfs;

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

public class boj_14500_java {
    static int n, m;
    static int[][] board;
    static boolean[][] visited;
    static int[] dr = {0, 0, -1, 1};
    static int[] dc = {-1, 1, 0, 0};
    static int answer;
    public static void main(String[] args) throws Exception{
        //테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
        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];
        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());
            }
        }

        visited = new boolean[n][m];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                visited[i][j] = true;
                dfs(1, i, j, board[i][j]);
                visited[i][j] = false;
            }
        }

        System.out.println(answer);
    

    }

    public static void dfs(int count, int r, int c, int sum){
        if(count==4){
            answer = Math.max(answer, sum);
            return;
        }

        for(int i=0; i<4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];

            if(nr<0 || nc<0 || nr>=n || nc>=m || visited[nr][nc]) continue;

            visited[nr][nc] = true;

            if(count==2){ //ㅏ ㅓ ㅜ ㅗ. 칸 2개 선택 시 현재 위치에서 다시 탐색 시작
                dfs(count+1, r, c, sum+board[nr][nc]);
            }

            dfs(count+1, nr, nc, sum+board[nr][nc]);

            visited[nr][nc] = false;
        }

    }
}