[Softeer] 함께하는 효도 - JAVA

https://softeer.ai/practice/7727

 

HAST 모의고사를 경험했기에, 외부 IDE를 쓰지 않는 것에 익숙해졌다. 때문에 자바 Docs를 보지 않고 진행할 수 있었다.

 

그래프 탐색 문제이며, 나는 DFS로 구현하였다.

---

 

시간 복잡도

최대 3명의 친구가 각각 3번씩 움직인다. 이를 delta 배열(4)로 구현하면,

O(4^(3*3)) = O(262144)가 나온다. 충분히 브루트포스 할 수 있다.

 

친구들은 같은 칸에 방문할 수 있으며, 해당 경우엔 값을 한 번만 누적한다.

나는 방문체크 배열만 기록하고 마지막에 계산하는 방식을 선택했다.

(방문 횟수는 딱히 상관 없으므로 boolean 배열로 구현해도 된다.)

 

또한, BFS를 사용한다면, 형상 복귀가 까다롭다. 때문에 DFS를 사용했다.

 

각 친구가 처음에 위치한 칸은 무조건 값을 누적해야 하므로 방문 체크 배열에 이를 표시하고 시작한다.

모듈러 연산으로 현재 탐색할 친구를 구해준 후, 델타로 탐색하고 친구의 좌표 또한 이동시킨다. 이후 형상복귀 해준다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int[][] map, visited, friends;
    static int[] dr = {0, 0, -1, 1}, dc = {-1, 1, 0, 0};
    static int ans, N, M;

    public static void main(String[] args) throws IOException {
        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];
        visited = new int[N][N];

        for (int i = 0; i < N; i++) {
            map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        friends = new int[M][2];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            friends[i][0] = Integer.parseInt(st.nextToken()) - 1;
            friends[i][1] = Integer.parseInt(st.nextToken()) - 1;
            visited[friends[i][0]][friends[i][1]]++;
        }
        dfs(0);

        System.out.println(ans);
    }

    public static void dfs(int dep) {

        if (dep == M * 3) {
            int total = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (visited[i][j] != 0) total += map[i][j];
                }
            }

            ans = Math.max(total, ans);
            return;
        }

        int nf = dep % M;
        int nr = friends[nf][0];
        int nc = friends[nf][1];

        for (int i = 0; i < 4; i++) {
            int tr = nr + dr[i];
            int tc = nc + dc[i];

            if (tr >= 0 && tr < N && tc >= 0 && tc < N) {
                visited[tr][tc]++;
                friends[nf][0] += dr[i];
                friends[nf][1] += dc[i];
                dfs(dep + 1);
                visited[tr][tc]--;
                friends[nf][0] -= dr[i];
                friends[nf][1] -= dc[i];
            }
        }
    }
}