알고리즘 단련장/소프티어

[소프티어] 함께하는 효도 레벨3 자바 풀이

dcho 2024. 11. 2. 00:23
SMALL

https://softeer.ai/practice/7727

 

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

 

softeer.ai

 

 

DFS의 기초를 다지다가 마주친 DFS 응용 문제 너란 녀석 엄청 강하구나. 하지만 너를 정복하겠다.

 

해결 전략

이 문제를 해결하기 위해 DFS와 백트래킹을 사용하여 모든 가능한 경로를 탐색하여 최대 수확량을 구한다.

처음 입력받는 위치와 값은 초기값으로 저장을 해둔다.

현재 위치에서 상하좌우로 비교해 가며 최대 수확량을 구하고 다음 친구가 턴을 이어 받아 (전에 있던 최대 수확량 + 현재 최대 수확량)으로 최대값을 구한다. 이를 계속 반복하면서 진정으로 최대값을 구한다.

각각 케이스에 3초의 시간이 있는데 3초가 끝날때 다음 친구에게 턴을 이어주기 위해 fCnt 를 사용해 현재 탐색 중인 친구의 인덱스를 추적하게 해준다.

모든 케이스의 최대 수확량을 뽑기 위해서는 DFS가 끝난 후 visited[ny][nx] = false를 통해 해당 위치를 다시 방문할 수 있도록 복구한다.

이렇게 백트래킹으로 경로를 되돌리기 때문에, DFS는 모든 가능한 경로를 탐색하면서 최대 수확량을 찾을 수 있게 된다.

 

정답 코드

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        answer = 0;

        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        maps = new int[n + 1][n + 1];
        visited = new boolean[n + 1][n + 1];

        // 맵 입력
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                maps[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 시작 위치 설정
        friends = new int[m][2];
        for (int k = 0; k < m; k++) {
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            friends[k] = new int[]{y, x};
            visited[y][x] = true;
            answer += maps[y][x];
        }

        // DFS 진행 (시작 위치도 수확 이후)
        dfs(friends[0][0], friends[0][1], 0, 0, answer);

        bw.write(answer + "\n");

        bw.flush();
        bw.close();
    }

    public static void dfs(int y, int x, int fCnt, int time, int sum) {
        answer = Math.max(answer, sum);

        if (time == 3) {
            // 다음 친구 DFS 진행
            if (fCnt + 1 < m) {
                dfs(friends[fCnt + 1][0], friends[fCnt + 1][1], fCnt + 1, 0, sum);
            }
        } else {
            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (nx > 0 && nx <= n && ny > 0 && ny <= n && !visited[ny][nx]) {
                    visited[ny][nx] = true;
                    dfs(ny, nx, fCnt, time + 1, sum + maps[ny][nx]);
                    // 백트래킹 (원상 복구)
                    visited[ny][nx] = false;
                }
            }
        }

    }
}

 

 

 

진짜 이제부터가 제대로된 알고리즘 문제인거 같다. 그동안 했던것은 손풀기 머리풀기 수준이다. 

하면서 느끼는 것은 왜 코딩테스트를 보는지 이유를 알것만 같다. 문제 해결을 하다보니 어떻게 접근해야하는지에 대해 깊게 고민해보고 해결하면서 실무에서 정답이 없는 문제를 풀때 좋은 시야를 가져다 주는것 같다.

아자 화이팅! 

항상 힘들고 지칠때 정신 개조 도와주는 동희야 고맙다.