[백트래킹/자바] 코드트리 IL. 1차원 윷놀이 @얉은복사, 깊은복사

https://www.codetree.ai/missions/2/problems/yutnori-1d?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 해석

• 이 문제는 윳놀이 말의 선택 조합을 어떻게 가져가면 더 많은 점수를 낼 수 있는지에 대한 문제이다.
• 백트래킹으로 완탐을 돌렸을 때 시간복잡도는 O(k^n + n) 정도 될 것인데, k가 4 이하이고, n이 12 이하이므로 약 16백만 정도의 연산량이 최대이니 백트래킹을 활용해도 좋을 것이란 판단이 났다.

 

문제 풀이

package 코드트리.완전탐색.백트래킹;

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

public class 일차원_윷놀이 {
    /*
    * 고르는 조합의 풀은 k까지
    * 재귀의 깊이는 n
    * 턴에 주어지는 숫자는 queue에 넣고 (FIFO) -> 틀린 부분
    * 재귀 라운드마다 골라지는 말에 더함 (말은 dictionary)
    * 재귀를 다 돌면 map을 순회하면서 점수 계산
    * 얻는 점수는 PQ에 담고, 이후 -pq.poll()로 최대값 찾기
    * */
    private static int n, m, k;
    private static List<Integer> q = new ArrayList<>();
    private static Queue<Integer> pq = new PriorityQueue<>();
    private static List<Integer> li = new ArrayList<>();
    private static Map<Integer, Integer> map = new HashMap<>();

    private static void go(Queue<Integer> q) {
        if (li.size() == n) {
            for (int i = 0; i < k; i++) {
                map.put(i, 1); // init
            }
            for (int i = 0; i < n; i++) {
                int step = q.poll();
                Integer key = li.get(i);
                map.put(key, map.get(key) + step);
            }
            int ans = 0;
            for (int i = 0; i < k; i++) {
                int t = map.get(i);
                if (t >= m) {
                    ans++;
                }
            }
            pq.add(-ans);
            return;
        }
        for (int i = 0; i < k; i++) {
            li.add(i);
            go(q);
            li.remove(li.size() - 1);
        }
    }

    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());
        k = Integer.parseInt(st.nextToken());


        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int temp = Integer.parseInt(st.nextToken());
            q.add(temp);
        }
        go(q);
        System.out.println(-pq.poll());
    }
}

처음에 입력받은 움직임에 대한 값을 FIFO로 꺼낸다 인식해서 Queue에 담아서 이용하려고 했다. scope rule을 고려하면, 파라미터로 queue를 받는다면 원래 입력받은 queue의 값에 영향을 끼치지 않을 것이라 생각했다.

 

이는 자바의 동작 원리를 이해하지 못한 방식이었다.

 

자바는 파라미터로 데이터를 넘길 때, int 와 같은 기본 자료형 변수들은 깊은 복사를 통해 값만 복사해서 넘기지만, list나 queue와 같은 참조형 변수에 대해서는 얉은 복사로 값을 넘긴다. 즉, 참조변수의 주소값을 넘기는 것이다. 그렇게 되면 당연히도 그 파라미터를 수정한다 할때, 원래 그 파라미터의 아규먼트로 받은 데이터에도 수정이 가해진다. 이러한 이유로 NPE를 맞이하고, 혹시나 하는 마음에 디버깅을 하다가 다시금 깨달음을 얻고 list에 저장한 뒤 인덱스로 조회하는 로직으로 수정하였다.

 

과거에 깊은 복사 얉은 복사와 같은 컨텐츠에 대하여 학습을 했었는데도, 돌아서면 까먹게 되는 것 같다...

package 코드트리.완전탐색.백트래킹;

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

public class 일차원_윷놀이 {
    private static int n, m, k;
    private static List<Integer> q = new ArrayList<>();
    private static Queue<Integer> pq = new PriorityQueue<>();
    private static List<Integer> li = new ArrayList<>();
    private static Map<Integer, Integer> map = new HashMap<>();

    private static void go() {
        if (li.size() == n) {
            for (int i = 0; i < k; i++) {
                map.put(i, 1); // init
            }
            for (int i = 0; i < n; i++) {
                int step = q.get(i);
                Integer key = li.get(i);
                map.put(key, map.get(key) + step);
            }
            int ans = 0;
            for (int i = 0; i < k; i++) {
                int t = map.get(i);
                if (t >= m) {
                    ans++;
                }
            }
            pq.add(-ans);
            return;
        }
        for (int i = 0; i < k; i++) {
            li.add(i);
            go();
            li.remove(li.size() - 1);
        }
    }

    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());
        k = Integer.parseInt(st.nextToken());


        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int temp = Integer.parseInt(st.nextToken());
            q.add(temp);
        }
        go();
        System.out.println(-pq.poll());
    }
}