구현 문제 (개미)

백준 3048번 구현문제를 Java로 풀어보았다.
예상치 못한 중요한 개념을 하나 배우게 됐다.

얕은 복사와 깊은 복사에 대해 제대로 배우게 됐다. 이전에 이미 책으로 배운 적은 있지만 실제로 이 개념과 관련한 상황에서 문제를 마주한 적이 없기 때문에 그저 존재만 알 뿐 어떻게 적용되는지에 대해서는 무지했다. 이 문제를 풀며 어떤 지점에서 이 개념에 대해 제대로 배우게 됐는지는 후술하겠다.

---

char 값 value, 방향 값 direction을 갖는 개미 클래스를 선언해줬다.

시간 값으로 받는 T만큼 반복문을 돌려주며 매번 전체 개미 행렬을 스캔해주어 서로 자리를 바꿔줘야할 개미를 찾아 자리를 바꿔주는 작업을 수행한다.

실제 로직을 구현하기 이전에 주의해야할 것은 첫 번째 개미 행렬은 역순으로 입력을 받아야 한다. 선두에 서는 개미가 가장 우측에 존재하기 때문이다.

자리 바꿔주기

자리를 바꿔주는 반복문을 수행하기 위해 현재 개미 행렬의 상태를 담을 Ant[] cur 과 가장 최근의 개미 행렬의 상태를 담을 Ant[] end 를 선언해준다.
cur의 상태에 따라 end를 update 해주면 된다.

자리를 바꿔줘야할 경우는 왼쪽 녀석은 오른쪽으로 가려하고, 오른쪽 녀석은 왼쪽으로 가려할 때 바꿔주면 된다. 이를 표현하기 위해 왼쪽 방향은 -1, 오른쪽 방향은 +1로 direction 변수에 담아주었다.

바로 여기가 얕은 복사와 깊은 복사에 대한 무지함이 드러나는 지점이다.

Ant[] end = start; // 가장 초기의 상태를 end 에 넣어주자
        for(int i=0; i<T; i++){
//            Ant[] cur = end; // 얕은 복사의 문제!!
            Ant[] cur = end.clone();
            for(int j=0; j<n1+n2-1; j++){
                if(cur[j].direction == 1 && cur[j+1].direction == -1){
                    Ant tmp = cur[j];
                    end[j] = cur[j+1];
                    end[j+1] = tmp;
                }
                else
                    continue;
            }
        }

주석 처리된 Ant[] cur = end; 를 보면 cur 배열을 end 배열로 얕은 복사를 해주었기 때문에 안쪽 반복문을 돌며 end의 상태만 바뀌는 것이 아니라 cur의 상태도 바뀌게 된다.

얕은 복사는 새로운 객체를 생성하는 것이 아니라, 동일한 주소를 가리킴으로써 사실상 한 몸이기 때문이다. 나으 무지함

이를 해결하기 위해 Object.clone(); 을 통해 새로운 객체를 생성한다.

---

객체 복사 문제를 마주치지 않고 해결하기

물론 위의 코드처럼 cur과 end를 따로 선언하지 않고 하나의 배열로 해결하면 얕은 복사와 깊은 복사의 문제를 겪지 않아도 된다.

위의 코드를 보면, 0번 index와 1번 index 를 비교하고, 1번 index와 2번 index 를 비교하고, ... n-1번 index와 n번 index까지 비교하는 방식이다.
하지만 1번과 2번을 서로 교체해주었으면 2번과 3번은 비교해줄 필요없이 바로 3번과 4번을 비교하는 단계로 넘어가면 된다.

이 로직을 구현한 코드는 다음과 같다.

Ant[] cur = start;
        for(int i=0; i<T; i++){
            for(int j=0; j<n1+n2-1; j++){
            	Ant a = cur[j];
                Ant b = cur[j+1];
                if(cur[j].direction == 1 && cur[j+1].direction == -1){
                    cur[j] = b;
                    cur[j+1] = a;
                    j++; // 그냥 한 칸 건너 뛰면 해결된다!
                }
                else
                    continue;
            }
        }

이렇게 할 경우 굳이 여러 배열을 선언해서 메모리를 낭비할 필요가 없다.

---

이렇게 두 가지 가능한 solution 을 살펴봤다. 어느 경우로 해도 맞긴 하기 때문에 문제를 만났을 때 먼저 생각나는 방식으로 해결하면 될 것 같긴 하다.

하지만 굳이 불필요한 배열들을 선언해서 메모리를 낭비하지 않는 쪽이 더 좋은 풀이 같다.

아래는 내가 제출한 코드다.

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

public class boj3048 {
    static class Ant {
        char value;
        int direction;

        public Ant(char value, int direction){
            this.value = value;
            this.direction = direction;
        }
    }

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        int n1 = Integer.parseInt(stk.nextToken()); int n2 = Integer.parseInt(stk.nextToken());
        Ant[] group1 = new Ant[n1+1]; Ant[] group2 = new Ant[n2+1];

        String input = bfr.readLine();
        for(int i=n1-1; i>=0; i--){
            group1[i] = new Ant(input.charAt(n1-i-1), 1);
        }

        input = bfr.readLine();
        for(int i=0; i<n2; i++){
            group2[i] = new Ant(input.charAt(i), -1);
        }

        Ant[] start = new Ant[n1+n2];
        for(int i=0; i<n1; i++) start[i] = group1[i];
        for(int i=n1; i<n1+n2; i++) start[i] = group2[i-n1];
        int T = Integer.parseInt(bfr.readLine());

        Ant[] end = start;
        for(int i=0; i<T; i++){
//            Ant[] cur = end; // 얕은 복사의 문제!!
            Ant[] cur = end.clone();
            for(int j=0; j<n1+n2-1; j++){
                if(cur[j].direction == 1 && cur[j+1].direction == -1){
                    Ant tmp = cur[j];
                    end[j] = cur[j+1];
                    end[j+1] = tmp;
                }
                else
                    continue;
            }
        }

        /** 이렇게 하면 굳이 배열 여러 개를 선언해서 메모리를 낭비할 필요가 없다 */
//        for(int i=0; i<T; i++){
//            for(int j=0; j<n1+n2-1; j++){
//                Ant a = start[j];
//                Ant b = start[j+1];
//                if(start[j].direction == 1 && start[j+1].direction == -1){
//                    start[j] = b;
//                    start[j+1] = a;
//                    j++;
//                }
//                else
//                    continue;
//            }
//        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n1+n2; i++)
            sb.append(end[i].value);

        bfw.write(sb.toString());
        bfw.close();
    }
}