[softeer] 함께하는 효도

30 Apr 2023 in Algorithm on Algorithm

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

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

public class Main {
    static int lineLen, personLen, totalCnt, result;
    static int[][] box;
    static boolean[][] visited;
    static List<int[]> personList = new ArrayList<>();
    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);

        lineLen = sc.nextInt();
        personLen = sc.nextInt();
        totalCnt = personLen*3;

        box = new int[lineLen][lineLen];
        visited = new boolean[lineLen][lineLen];

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

        for(int i = 0 ; i < personLen ; i++){
            int tempx = sc.nextInt()-1;
            int tempy = sc.nextInt()-1;
            personList.add(new int[]{tempx, tempy});
            visited[tempx][tempy] = true;
            result += box[tempx][tempy];
        }

        dfs(0, result, personList.get(0)[0], personList.get(0)[1]);

        System.out.println(result);
    }

    static void dfs(int cnt, int sum, int x, int y){
        if(cnt == totalCnt){
            result = Math.max(sum,result);
        }else{

            if(cnt%3 == 0){
                int idx = cnt / 3;
                x = personList.get(idx)[0];
                y = personList.get(idx)[1];
            }

            for(int i = 0 ; i < 4 ; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx >= 0 && ny >= 0 && nx < lineLen && ny < lineLen){
                    if(visited[nx][ny]){
                        dfs(cnt+1, sum, nx, ny);
                    }else{
                        visited[nx][ny] = true;
                        dfs(cnt+1, sum + box[nx][ny], nx, ny);
                        visited[nx][ny] = false;
                    }
                }
            }
        }
    }
}