[Java/BruteForce] 소프티어. 함께하는효도

🤔 Intuition

이 문제는 동시 탐색 결과를 구하는 코드를 구현할 수 있는가를 묻는 문제였다.

컴퓨터는 한번에 하나의 연산만을 수행하는 것이 기본이기 때문에, 이전 결과를 잘 저장해둬서 다음에 영향을 주게끔 구현해야 한다.

 

동시에 탐색하는 효과를 주기 위해 history라는 좌표 리스트를 운영하여, 이전 탐색에서 최선을 얻었던 값의 자취를 다음 탐색에 반영해주었다.

 

하지만 여기서 내가 놓쳤던 부분이 있다.

코드 상에서는 각 출발지가 모두 다르므로, 탐색이 시작되는 위치의 순서가 달라졌을 때 최선의 값이 달라질 수 있음을 고려해야 했다. 이를 고려해야 비로소 동시 탐색 결과를 알 수 있는 모든 케이스를 탐색할 수 있게 된다. 따라서 이는 순열을 접목하여 표현해 주었다.

🔎 Algorithm & Complexity

* @algorithm brute-force (permutation + dfs)
* @time O(M! * N^2) 순열 O(M!) * DFS O(N^2) -> 87 ms
* @memory O(N^2) 3차원 배열을 사용했지만 상수값으로 설정하므로 O(N^2) -> 11.46 MB

👨🏻‍💻 Logic

1. 순열을 통해 탐색 위치의 순서를 구한다.
2. 탐색 순서 경우의 수 각각에 대하여 독립사건으로 결과를 구하기 위해 map을 복사하여 탐색한다. (temp 이용)
3. dfs를 이용하여 각 출발지에서 3칸까지 델타탐색할 때 얻을 수 있는 최대 sum 값을 구하고, 저장한다.
4. 각 순열 경우의 수 기준으로 M개의 sum 값의 합을 res에 저장해두고, 이 중에서 최대값을 갱신하며 정답을 구함

public class SFT_함께하는효도 {
    private static int N, M, ans;
    private static int[][][] map;
    private static int[] ansArr;
    private static List<int[]> history;
    private static int[] dy = {1, -1, 0, 0};
    private static int[] dx = {0, 0, 1, -1};
    private static final int VAL = 0;
    private static final int SUM = 1;
    private static final int CNT = 2;
    private static int[][] mPosArr;
    private static int[] selected;
    private static int[][][] temp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N][3];
        mPosArr = new int[M][2];
        selected = new int[M];

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

        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken()) - 1;
            int x = Integer.parseInt(st.nextToken()) - 1;
            mPosArr[m][0] = y;
            mPosArr[m][1] = x;
        }

        perm(0, 0);



        br.close();
        bw.write(sb.append(ans).toString());
        bw.flush();
        bw.close();
    }

    private static void perm(int cnt, int visited) {
        if (cnt == M) {
            ansArr = new int[M];
            temp = new int[N][N][3];
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    temp[j][k] = map[j][k].clone();
                }
            }
            for (int i : selected) {
                int y = mPosArr[i][0];
                int x = mPosArr[i][1];
                temp[y][x][SUM] = temp[y][x][VAL];
                temp[y][x][CNT] = i * 10 + 1; // 10의 자리수로 각 인원을 구별
                List<int[]> footPrint = new ArrayList<>();
                footPrint.add(new int[]{y, x});
                go(y, x, i, footPrint);
                for (int[] pos : history) {
                    temp[pos[0]][pos[1]][CNT] = i;
                }
            }
            int res = Arrays.stream(ansArr).sum();
            ans = Math.max(res, ans);

            return;
        }
        for (int i = 0; i < M; i++) {
            if ((visited & 1 << i) != 0) {
                continue;
            }
            selected[cnt] = i;
            perm(cnt+1,visited | 1 << i);
        }
    }

    private static void go(int y, int x, int m, List<int[]> footPrint) {
        if ((temp[y][x][CNT] % 10) == 4) { // 1부터 시작 -> 4가 되었을 때 종료
            int mdx = temp[y][x][CNT] / 10; // 각 친구별 인덱스 추출
            if (temp[y][x][SUM] > ansArr[mdx]) {
                ansArr[mdx] = temp[y][x][SUM];
                // 갱신되었을 때에는, 이 케이스의 발자취를 저장해서 다음에 영향을 줘야 함.
                // 근데 이렇게 영향을 줄 발자취는 전부 탐색한 뒤에 결정이 가능함
                // 따라서 재귀 안에서는 자취만 기록해두고, 나중에 나가서 입력해야 함.
                history = new ArrayList<>();
                for (int[] ints : footPrint) {
                    history.add(ints);
                }
            }
            return;
        }
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (inRange(ny, nx)) {
                if (temp[ny][nx][CNT] > 0) {
                    continue;
                }
                temp[ny][nx][SUM] = temp[ny][nx][VAL] + temp[y][x][SUM];
                temp[ny][nx][CNT] = temp[y][x][CNT] + 1;
                if ((temp[ny][nx][CNT] % 10) <= 4) { // 1부터 시작 -> 4가 되었을 때 종료
                    footPrint.add(new int[]{ny, nx});
                    go(ny, nx, m, footPrint);
                    footPrint.remove(footPrint.size() - 1);
                    temp[ny][nx][SUM] = 0;
                    temp[ny][nx][CNT] = 0;
                }
            }
        }
    }

    private static boolean inRange(int y, int x) {
        return y >= 0 && y < N && x >= 0 && x < N;
    }
}