[소프티어] 나무 조경 🌳 (Java)

문제 링크

Softeer - 현대자동차그룹 SW인재확보플랫폼

구조화

최대 4쌍? -> 조합

그런데 다른 문제들처럼 몇개 뽑는지가 아니라 최대 4개 뽑는다고 해서 재귀할때마다 최댓값 갱신해줌

걸린 시간(23:46)

소스 코드

// 4개의 쌍 -> 픽스
import java.io.*;
import java.util.*;

public class Main {
    static int n, ans = 0;
    static int[][] map,
    way = {{-1,0},{1,0},{0,-1},{0,1}};
    static boolean[][] visit;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        visit = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        loop(0, 0);
        System.out.println(ans);
        
    }

    static void loop(int cnt, int sum) {
        ans = Math.max(ans, sum);
        
        if (cnt>=4) {
            return;    
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visit[i][j]) {
                    
                    for (int w = 0; w < 4; w++) {
                        int nx = i + way[w][0];
                        int ny = j + way[w][1];

                        if (nx<0 || nx>=n || ny<0 || ny>=n || visit[nx][ny]) continue;
                        
                        visit[i][j] = true;
                        visit[nx][ny] = true;
                        loop(cnt+1, sum + map[i][j] + map[nx][ny]);
                        visit[i][j] = false;
                        visit[nx][ny] = false;
                    }
                }
            }
        }
    }
}