[소프티어] LV3 : 함께하는 효도 (java)

🧪 LV3 함께하는 효도

---

난이도 : 🌟 LV3
유형 : BackTracking

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

 

📝 문제

---

남우는 m명의 친구를 불러 나무에서 열매를 수확하는 일을 맡겼습니다. 나무들은 n * n 크기의 격자 모양의 땅 위의 모든 칸에 심어져 있고, 각 나무마다 가능한 열매 수확량이 주어져 있습니다.

 

친구들은 n * n 크기의 격자 내의 서로 다른 위치에서 출발하여 1초에 1칸씩 상하좌우 인접한 칸 중 한 곳으로 움직일 수 있으며, 최종적으로 모든 열매 수확량의 합을 최대로 만들고자 합니다. 이때 각 칸에서 열매를 수확하는데 걸리는 시간은 0초이며, 한 나무에 여러 친구가 방문하게 되더라도 열매는 딱 한 번만 수확이 가능합니다. 또, 친구들끼리 이동하는 도중 만나게 되는 것 역시 가능합니다.

 

m명의 친구들이 3초 동안 최대로 얻을 수 있는 열매 수확량의 총 합을 구하는 프로그램을 작성해보세요.

 

본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.

 

제약조건

 

[조건 1] 2 ≤ n ≤ 20

[조건 2] 1 ≤ m ≤ 3

[조건 3] 1 ≤ 가능한 열매 수확량 ≤ 1,000

 

 

입력

 

첫 번째 줄에 n과 m이 공백을 사이에 두고 주어집니다.

 

두 번째 줄부터는 n개의 줄에 걸쳐 각 행에 해당하는 n개의 가능한 열매 수확량 정보가 공백을 사이에 두고 주어집니다.

 

n + 2번째 줄부터는 m개의 줄에 걸쳐 각 친구의 위치 정보 ( Xi , Yi )가 공백을 사이에 두고 주어집니다. 이는 친구가 ( Xi 행, Yi 열)에 위치해 있음을 뜻하며, 처음 위치가 겹쳐져 주어지는 경우는 없다고 가정해도 좋습니다.

 

출력

 

첫 번째 줄에 얻을 수 있는 최대 열매 수확량의 합을 출력하세요. 단, 처음 시작하는 칸의 경우 0초 때 열매 수확이 가능함에 유의합니다.

 

🚧  주의할 점

---

1. 처음엔 visited로 체크도 했었는데 만약 시작지점 좌우로 둘 다 큰 수가 있고 다른 수들이 그 둘에 비해 현저히 작은 경우 3개를 다 밟지 않고 오른쪽을 갔다 다시 돌아와서 왼쪽을 지나 2개만 밟는 경우도 체크할 필요가 있어 visited가 필요하지 않다고 생각했다.
2. 입력값으로 받는 x, y의 좌표에서 1을 빼야 인덱스 번호에 맞게 들어간다.

🧐 핵심 로직

---

1) x좌표와 y좌표 그리고 열매량 정보를 가지고 있는 Node 클래스를 만들어준다.

 

2) harvest 2차원 배열에 입력값들을 채우고 친구수에 따른 출발 위치를 Node 객체들의 리스트에 추가해준다.

    ◈ 이때, 열매량은 이미 Node 객체에 포함시켰으니 그 자리의 열매량을 0으로 만든다.

 

3) backTracking 함수를 부르고 cnt가 3초를 다 돌았고, idx가 친구 수보다 적을 때 다음 친구에 대한 backTracking을 실행한다.

    ◈ 들어가는 값은 다음 친구의 노드와 현재까지의 열매량을 넣어준다.

 

4) 들어간 친구 역시 3초가 지났고 idx가 m과 같아졌다면 결과값에 현재까지의 최대 열매량을 넣고 재귀를 반복하며 최대의 열매 수확량이 res에 저장되고 이를 출력한다.

 

💻 최종 코드 (최대 99 ms)

---

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

public class Main {

    static class Node {

        int x, y, fruit;

        Node(int x, int y, int fruit) {
            this.x = x;
            this.y = y;
            this.fruit = fruit;
        }
    }

    static int n, m, res;
    static List<Node> nodes;
    static int[][] harvest;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        res = Integer.MIN_VALUE;
        nodes = new ArrayList<>();
        harvest = new int[n][n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                harvest[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            
            Node startNode = new Node(x - 1, y - 1, harvest[x - 1][y - 1]);
            nodes.add(startNode);
            harvest[x - 1][y - 1] = 0;
        }
        
        backTracking(nodes.get(0), 1, 0, 0);

        System.out.println(res);

        br.close();
    }

    private static void backTracking(Node curNode, int idx, int cnt, int maxFruit) {

        if (cnt == 3) {
            if (idx < m) {
                backTracking(nodes.get(idx), idx + 1, 0, maxFruit + curNode.fruit);
                return;
            }

            res = Math.max(res, maxFruit + curNode.fruit);
            return;
        };

        for (int i = 0; i < 4; i++) {
            int nx = curNode.x + dx[i];
            int ny = curNode.y + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;

            Node nextNode = new Node(nx, ny, curNode.fruit + harvest[nx][ny]);
            int tmp = harvest[nx][ny];
            harvest[nx][ny] = 0;
            backTracking(nextNode, idx, cnt + 1, maxFruit);
            harvest[nx][ny] = tmp;
        }
    }
}