[Softeer] 함께하는 효도

다 푼줄 알았는데,, DFS나 BFS를 모르고 풀기에는 무리가 있나보다.... 내코드는 오답임

---

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

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

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

 

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

• [2024-07-24] 문제 지문 중 일부를 변경하였으며, 해당 부분에 강조/밑줄을 추가하였습니다. ('이동 경로가 겹치는 것은 불가능합니다.')

제약조건

[조건 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

4 2 20 26 185 80 100 20 25 80 20 20 88 99 15 32 44 50 1 2 2 3

출력예제1

633

 

---

내 코드

 

반례

 

3 2
1 2 3
4 5 6
7 8 9
1 1
2 2

 

2번째 친구가 5->6->9에서 갇힘. 5->6->3->2로 가야하는데,,, 내소스는 안간다.

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

public class Main {
    public static int n;
    public static int m;
    public static int[][] land;
    public static int[][] visited;
    public static int[] dy = {0, 0, 1, -1};
    public static int[] dx = {1, -1, 0, 0};

    public static boolean isIn(int a, int b){
        return a >= 0 && a < n && b >= 0 && b < n;
    }

    public static boolean isVisited(int a, int b){
        return visited[a][b] != 0;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); //땅 크기
        m = sc.nextInt(); //친구 수
        land = new int[n][n];
        visited = new int[n][n];

        //열매 수 셋팅
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                land[i][j] = sc.nextInt();
            }
        }

        int sum = 0;
        for(int i = 0; i < m; i++){
            /*  1. 가려고 하는 방향(동,서,남,북)이 범위안에 있는지
                2. start거나 visited가 아닌곳
                3. 중에 가장 큰곳
            */
            int a = sc.nextInt()-1; //시작 열값
            int b = sc.nextInt()-1; //시작 행값

            visited[a][b] += 1;
            //첫 위치
            sum += land[a][b];
            for(int j = 0; j < 3; j++){
                //동서남북 탐방
                int temp = Integer.MIN_VALUE;
                int move = -1;
                for(int k = 0; k <= 3; k++){
                    if(isIn(a + dy[k], b + dx[k]) && !isVisited(a + dy[k], b + dx[k])){
                        if(land[a + dy[k]][b + dx[k]] > temp){
                            temp = land[a + dy[k]][b + dx[k]];
                            move = k;
                        }
                    }
                }                
                sum += temp;
                a += dy[move];
                b += dx[move];
                visited[a][b] += 1;
            }
        }
        System.out.println(sum);
    }
}