[소프티어] 함께하는 효도 LV.3

문제

https://softeer.ai/practice/7727

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

 

 

자세한 내용은 원문 코드를 참조할 것.

 

풀이

 

처음에는 dp[Idx][R][C]를 통해, 각 친구(idx)별 경로를 추적하여 dp를 사용하고자 했으나,

백트래킹으로 각 위치별 수집량을 점유한 뒤, 이를 다음 친구로 적용하는 로직으로 풀이를 변경하였다.

 

풀이는 다음과 같다.

 

1. 0번째 인덱스(첫번째 친구)를 먼저 탐색한다.

2. if 기저조건 : time = 3초일 경우 해당 값을 저장한 채로, idx를 증가한 뒤 재귀 함수를 시행한다(다음 친구 호출)

3. 최종 조회 시 최대값을 비교한다.

4. 백트래킹을 통해 가지치기를 수행한다.

 

자세한 내용은 코드를 참조할 것

 

코드

 

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

public class Main {
    static final int[] DR = new int[] {0, 1, 0, -1};
    static final int[] DC = new int[] {1, 0, -1, 0};
    static int N, M;
    static int[][] map;
    static boolean[][][] visit;
    static List<int[]> friends = new ArrayList<>();
    static int maxResult = 0;

    public static void main(String[] args) throws Exception {
        input();
        int r = friends.get(0)[0];
        int c = friends.get(0)[1];
        dfs(0, 0, 0, r, c);
        System.out.println(maxResult);
    }

    //
    public static void dfs(int time, int idx, int res, int r, int c) {
        if(checkVisit(r, c)) res += map[r][c]; //'전체 Visit'에서 아무도 방문하지 않은 경우 더하기
        visit[idx][r][c] = true; //방문 처리

        if (time == 3) { // 기저조건: 3초 전부 수집
            if (idx + 1 == M) { // 마지막 친구일 경우 결과 갱신
                maxResult = Math.max(maxResult, res);
            } else {
                // 다음 친구로 넘어가는 로직
                int nextIdx = idx + 1; // 인덱스 증가
                int nextR = friends.get(nextIdx)[0]; // 다음 친구 좌표
                int nextC = friends.get(nextIdx)[1]; //
                dfs(0, nextIdx, res, nextR, nextC); // 현재 res값을 가지고 다음 친구로 이동
            }
            visit[idx][r][c] = false; // 방문 처리 해제 (백트래킹)
            return;
        }

        for(int i = 0; i < 4; i++) {
            int nr = r + DR[i];
            int nc = c + DC[i];
            if(cantGo(nr, nc) || visit[idx][nr][nc]) continue; //방문했거나 갈 수 없음
            dfs(time + 1, idx, res, nr, nc);
        }

        visit[idx][r][c] = false; //방문 처리 해제(가지치기)
    }

    public static boolean checkVisit(int r, int c) {
        for(int i = 0; i < M; i++) {
            if(visit[i][r][c]) return false; //이미 누군가 방문했음
        }
        return true; //아무도 방문하지 않음
    }

    public static boolean cantGo(int r, int c) {
        if(r < 0 || c < 0 || r >= N || c >= N) return true;
        return false;
    }

    public static void input() 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());
        map = new int[N][N];
        visit = new boolean[M][N][N];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            friends.add(new int[] {r, c, map[r][c], 0}); //r, c, 시작값, 시간(bfs에서 사용)
        }
    }
}