문제 - 나무 조경

문제접근

인접한 나무끼리 쌍을 묶어서 총 4개의 쌍을 찾아야되는 문제이다.
이때 총 4개의 쌍이 되지 않을 때에는 충족시키지 않아도된다.
즉 n=2일때에는 4개의 쌍을 만들 수 없으므로 2개의 쌍만 찾는다.

모든 경로를 탐색해야되므로 dfs를 사용한다. 이때에 상하좌우를 모두 고려하지 않고 아래와 오른쪽만 고려한다.
그 이유는 처음 0,0인덱스부터 시작을 하면 왼쪽과 위는 고려를 하지 않아도 모두 연결해서 확인할 수 있기 때문이다.

주요 코드

 static void dfs(int cnt, int sum,int maxDepth)
    {
        if(cnt == maxDepth)
        {
            ans = Math.max(ans,sum);
            return;
        }

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(visited[i][j]) continue;
                //현재 좌표와 아래 혹은 오른쪽의 나무를 쌍으로 묶음
                for(int d =0;d<2;d++){
                    int nx = i + dx[d];
                    int ny = j + dy[d];

                    if( 0<= nx && nx <n && 0<= ny && ny < n && !visited[nx][ny])
                    {
                        visited[i][j] = true;
                        visited[nx][ny] = true;
                        dfs(cnt+1,sum + maps[i][j] + maps[nx][ny],maxDepth);
                        visited[i][j] = false;
                        visited[nx][ny] = false;
                        
                    }
                }
            }
        }
    }

전체 소스코드

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

public class Main {

    static int ans =0,n=0;
    //아래 오른쪽만 설정
    static int dx[] = {0,1};
    static int dy[] = {1,0};
    static int maps[][];
    static boolean visited[][];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        maps = new int[n][n];
        visited = new boolean[n][n];
        
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                maps[i][j] = sc.nextInt();
            }
        }
        int maxDepth = 4;
        if(n==2) maxDepth =2;
        
        dfs(0,0,maxDepth);
        
        System.out.println(ans);
        
    }

    static void dfs(int cnt, int sum,int maxDepth)
    {
        if(cnt == maxDepth)
        {
            ans = Math.max(ans,sum);
            return;
        }

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(visited[i][j]) continue;
                //현재 좌표와 아래 혹은 오른쪽의 나무를 쌍으로 묶음
                for(int d =0;d<2;d++){
                    int nx = i + dx[d];
                    int ny = j + dy[d];

                    if( 0<= nx && nx <n && 0<= ny && ny < n && !visited[nx][ny])
                    {
                        visited[i][j] = true;
                        visited[nx][ny] = true;
                        dfs(cnt+1,sum + maps[i][j] + maps[nx][ny],maxDepth);
                        visited[i][j] = false;
                        visited[nx][ny] = false;
                        
                    }
                }
            }
        }
    }
}