[BOJ] 15787: 기차가 어둠을 헤치고 (JAVA)

문제

https://www.acmicpc.net/problem/15787

 

여담

처음에는 순수 구현으로 풀었다. 그치만 비트마스킹으로도 풀 수 있다길래 비트마스킹에 대해 간단하게 공부한 뒤 다시 풀었다. 이때까지 비트마스킹이 어려울 것 같아서 계속 미루고 있었는데, 이 문제를 통해 비트마스킹에 대해 알아볼 수 있는 기회가 되었다!

 

그리고 비트마스킹을 사용하면 더 빠른 시간, 더 적은 메모리를 사용하는 효과가 있다고 들었는데, 실제로 확실히 차이가 나는 것을 확인할 수 있었다. 비트마스킹을 잘 익히면 유용하게 써먹을 수 있을 것 같다! 

위: 비트마스킹 / 아래: 구현

 

풀이

기차의 상태를 구한 뒤, HashSet을 이용해서 중복을 거른 후 저장된 수를 출력하면 된다.

 

기차의 상태를 구하는 방법은 구현과 비트마스킹, 총 2가지로 나눌 수 있다. 각 방법은 아래의 설명과 코드를 참고하면 된다.

 

구현

기차의 상태를 구하기 위해서, 단순하게 문제에 주어진 명령에 맞게 구현을 하면 된다. 

 

이때, 주의해야 할 명령은 3번이다. 3번 명령의 경우 한 칸씩 뒤로 가는 것이기 때문에 앞에서부터 값을 변경하면 제대로 값이 갱신되지 않는다. 따라서 추가로 배열을 하나 더 사용하거나 뒤에서부터 값을 변경해 주도록 해야 한다.

 

비트마스킹

기차의 상태를 구하기 위해서, 각 명령에 맞게 비트마스크 연산을 수행하면 된다.

 

기차는 0번부터 N - 1번, 좌석은 0번부터 19번까지로 매긴다. 여기서 좌석은 각 자리의 비트를 뜻한다. 따라서 19번 - 18번 - 17번 - ... - 2번 - 1번 - 0번과 같은 식으로 매겨져있는 것이다. 

 

그럼 각 명령마다 수행해야 하는 연산을 살펴보자.

• 1번 명령
  • i번째 기차의 x번째 좌석에 사람 태우기
  • 즉, x번째 위치에 원소를 추가하는 것 (0에서 1로 변경)
  • trains[i] = trains[i] | (1 << x) (trains[i] |= (1 << x))
• 2번 명령
  • i번째 기차의 x번째 좌석에서 하차하기
  • 즉, x번째 위치에서 원소를 삭제하는 것 (1에서 0으로 변경)
  • trains[i] = trains[i] & ~(1 << x) (trains[i] &= ~(1 << x))
• 3번 명령
  • i번째 기차에 앉아있는 승객들을 모두 한 칸씩 뒤로 밀기
  • 한 칸씩 뒤로 밀기: trains[i] = trains[i] << 1 (trains[i] <<= 1)
  • 20번 자리에 값이 있으면 안되므로 삭제하기: trains[i] &= ~(1 << 20) 
• 4번 명령
  • i번째 기차에 앉아있는 승객들을 모두 한 칸씩 앞으로 밀기
  • 한 칸씩 앞으로 밀기: trains[i] = trains[i] >> 1 (trains[i] >>= 1)

뒤로 미는 경우와 달리, 앞으로 미는 경우에는 0번을 Shift하면 자동으로 사라진다. 따라서 비트를 직접 삭제할 필요가 없다.

 

코드

구현

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

public class Main {
    static int N, M;
    static final int K = 20;
    static int[][] trains;
    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());
        trains = new int[N + 1][K + 1];
        for (int t = 0; t < M; t++) {
            st = new StringTokenizer(br.readLine());
            int cmd = Integer.parseInt(st.nextToken());
            int i = Integer.parseInt(st.nextToken());
            int x;
            switch (cmd) {
                case 1: // 기차에 태우기
                    x = Integer.parseInt(st.nextToken());
                    trains[i][x] = 1;
                    break;
                case 2: // 기차에서 내리기
                    x = Integer.parseInt(st.nextToken());
                    trains[i][x] = 0;
                    break;
                case 3: // 한 칸씩 뒤로 이동
                    for (int j = K; j >= 2; j--) {
                        trains[i][j] = trains[i][j - 1];
                    }
                    trains[i][1] = 0;
                    break;
                case 4: // 한 칸씩 앞으로 이동:
                    for (int j = 1; j < K; j++) {
                        trains[i][j] = trains[i][j + 1];
                    }
                    trains[i][K] = 0;
                    break;
            }
        }

        HashSet<String> hashSet = new HashSet<>();
        for (int i = 1; i <= N; i++) { // 문자열과 해시로 기차의 상태 확인하기
            StringBuilder sb = new StringBuilder();
            for (int j = 1; j <= K; j++) {
                sb.append(trains[i][j]);
            }
            hashSet.add(sb.toString());
        }
        System.out.println(hashSet.size());
    }
}

 

비트마스킹

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

public class Main {
    static int N, M;
    static int[] trains;
    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());
        trains = new int[N];
        for (int t = 0; t < M; t++) {
            st = new StringTokenizer(br.readLine());
            int cmd = Integer.parseInt(st.nextToken());
            int i = Integer.parseInt(st.nextToken()) - 1;
            int x;
            switch (cmd) {
                case 1: // 기차에 태우기
                    x = Integer.parseInt(st.nextToken()) - 1; // 0번 ~ 19번
                    trains[i] |= (1 << x); // x번째 자리의 값을 1로 변경
                    break;
                case 2: // 기차에서 내리기
                    x = Integer.parseInt(st.nextToken()) - 1;
                    trains[i] &= ~(1 << x); // x번째 자리의 값을 0으로 변경
                    break;
                case 3: // 한 칸씩 뒤(←)로 이동
                    trains[i] <<= 1; // 각 자리의 사람 모두 한 칸씩 뒤로
                    trains[i] &= ~(1 << 20); // 20번 자리의 사람이 있다면 하차(0으로 변경)
                    break;
                case 4: // 한 칸씩 앞(→)으로 이동
                    trains[i] >>= 1; // 각 자리의 사람 모두 한 칸씩 앞으로
                    break;
            }
        }
        HashSet<Integer> hashSet = new HashSet<>();
        for (int train : trains) {
            hashSet.add(train);
        }
        System.out.println(hashSet.size());
    }
}

---

참고

https://hungseong.tistory.com/119

https://g-db.tistory.com/entry/JAVA-%EB%B0%B1%EC%A4%80-15787