[소프티어] 함께하는 효도 (자바풀이)

문제

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

Candidate | Softeer Assessment UI

 

문제풀이

문제 조건은 무엇인가?

3초동안 각 친구들이 수확한 과일의 최대 수확량을 구해야 한다 이 때 친구들의 경로는 겹치면 안된다.

 

접근 방법은?

DFS를 통해서 전체 경우의 수를 구해준다

-> 한 친구의 3초동안의 수확이 끝나면 다음 친구의 수확량을 구해준다.

(workerList에 각 친구의 시작위치를 저장해 놓고 idx를 파라미터로 넘겨서 다음 친구의 수확을 시작)

 

코드

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

public class Main {
    static int[][] board;
    static int n, m;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static boolean[][] visited;
    static ArrayList<int[]> workerList;
    static int answer = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        visited = new boolean[n][n];
        board = new int[n][n];
        workerList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = in.nextInt();
            }
        }

        for (int i = 0; i < m; i++) {
            int x = in.nextInt() - 1;
            int y = in.nextInt() - 1;
            workerList.add(new int[]{x, y});
        }
        dfs(0, workerList.get(0)[0], workerList.get(0)[1], 0, board[workerList.get(0)[0]][workerList.get(0)[1]]);
        System.out.println(answer);
    }

    public static void dfs(int time, int x, int y, int workIdx, int sum) {
        visited[x][y] = true;
        if (time == 3) {
            if (workIdx + 1 < m) {
                int startX = workerList.get(workIdx + 1)[0];
                int startY = workerList.get(workIdx + 1)[1];
                dfs(0, startX, startY, workIdx + 1, sum + board[startX][startY]);
            } else {
                answer = Math.max(sum, answer);
            }
        } else {
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    dfs(time + 1, nx, ny, workIdx, sum + board[nx][ny]);
                    visited[nx][ny] = false;
                }
            }
        }
    }
}