[softeer] 나무 조경

05 May 2023 in Algorithm on Algorithm

https://softeer.ai/app/assessment/index.html?xid=463433&xsrfToken=RIqEWvn41LnQkwxiIN8GGp07U2bXSlYE&testType=practice

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

public class Main {
    static boolean[][] visited;
    static int[][] box;
    static int result = 0;
    static int n;
    static int[] dx = new int[]{-1,0,1,0};
    static int[] dy = new int[]{0,1,0,-1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        visited = new boolean[n][n];
        box = new int[n][n];

        for(int x = 0 ; x < n ; x++){
            for(int y = 0 ; y < n ; y++){
                box[x][y] = sc.nextInt();
            }
        }

        dfs(0,0);

        System.out.println(result);

    }

    static void dfs(int cnt, int sum){
        if(cnt == 4 || (n == 2 && cnt == 2) ){
            result = Math.max(result, sum);
        }else{

            for(int x = 0 ; x < n ; x++){
                for(int y = 0 ; y < n ; y++){
                    if(!visited[x][y] && (x+1) < n && !visited[x+1][y]){
                        visited[x][y] = true;
                        visited[x+1][y] = true;
                        dfs(cnt+1, sum+box[x][y]+box[x+1][y]);
                        visited[x][y] = false;
                        visited[x+1][y] = false;
                    }

                    if(!visited[x][y] && (y+1) < n && !visited[x][y+1]){
                        visited[x][y] = true;
                        visited[x][y+1] = true;
                        dfs(cnt+1, sum+box[x][y]+box[x][y+1]);
                        visited[x][y] = false;
                        visited[x][y+1] = false;
                    }
                }
            }
        }
    }
}