[Boj_15787] 기차가 어둠을 헤치고 은하수를

📎 문제 링크

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

 

▸ 문제

N개의 기차가 어둠을 헤치고 은하수를 건너려고 한다.

기차는 20개의 일렬로 된 좌석이 있고, 한 개의 좌석에는 한 명의 사람이 탈 수 있다. 

기차의 번호를 1번부터 N번으로 매길 때, 어떠한 기차에 대하여 M개의 명령이 주어진다.

명령의 종류는 4가지로 다음과 같다.

• 1 i x : i번째 기차에(1 ≤ i ≤ N) x번째 좌석에(1 ≤ x ≤ 20) 사람을 태워라. 이미 사람이 타있다면 , 아무런 행동을 하지 않는다.
• 2 i x : i번째 기차에 x번째 좌석에 앉은 사람은 하차한다. 만약 아무도 그자리에 앉아있지 않았다면, 아무런 행동을 하지 않는다.
• 3 i : i번째 기차에 앉아있는 승객들이 모두 한칸씩 뒤로간다. k번째 앉은 사람은 k+1번째로 이동하여 앉는다. 만약 20번째 자리에 사람이 앉아있었다면 그 사람은 이 명령 후에 하차한다.
• 4 i : i번째 기차에 앉아있는 승객들이 모두 한칸씩 앞으로간다. k번째 앉은 사람은 k-1 번째 자리로 이동하여 앉는다. 만약 1번째 자리에 사람이 앉아있었다면 그 사람은 이 명령 후에 하차한다.

M번의 명령 후에 1번째 기차부터 순서대로 한 기차씩 은하수를 건너는데 조건이 있다.

기차는 순서대로 지나가며 기차가 지나갈 때 승객이 앉은 상태를 목록에 기록하며 이미 목록에 존재하는 기록이라면 해당 기차는 은하수를 건널 수 없다.

예를 들면, 다음 그림을 예로 들었을 때, 1번째 기차와 같이 승객이 앉은 상태는 기록되지 않았기 때문에 은하수를 건널 수있다. 2번째 기차와 같은 상태도 기록되지 않았기 때문에 2번째 기차도 은하수를 건널 수 있다. 3번째 기차는 1번째 기차와 승객이 앉은 상태가 같으므로 은하수를 건널 수 없다.

처음에 주어지는 기차에는 아무도 사람이 타지 않는다.

은하수를 건널 수 있는 기차의 수를 출력하시오.

 

▸ 입력

입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. 

 

▸ 출력

은하수를 건널 수 있는 기차의 수를 출력하시오.

 

📍 문제 정보

• 🥈  문제 레벨 : 실버 2
• 🔔  문제 유형 : 구현, 비트마스킹
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

비트 마스킹을 활용하면 각 기차의 좌석 상태를 20비트 정수로 효율적으로 표현할 수 있다.

 

각 명령에 따른 연산을 비트 연산으로 처리할 수 있으며, 다음과 같이 구현할 수 있다.

🎯 명령별 비트 마스킹 연산

명령 1

• 1 i x : i번째 기차의 x번째 좌석에 사람을 태우기
• trains[i] |= (1 << x);
• 이때, 좌석의 번호는 1부터 시작하지만 비트 마스킹의 인덱스는 0부터 시작하므로 x를 입력받으면서 -1을 해준다.

명령 2

• 2 i x : i번째 기차에 x번째 좌석에 앉은 사람을 하차시키기
• trains[i] &= ~(1 << x);
• ~ 연산으로 해당 비트를 0으로 만든 후, AND 연산으로 제거한다.

명령 3

• 3 i : i번째 기차에 앉아있는 승객들을 모두 한 칸씩 뒤로 이동
• trains[i] = (trains[i] << 1) & ((1 << 20) - 1);
• << 연산을 사용해 왼쪽으로 밀고, 21번째 비트는 & 연산으로 제거한다.

명령 4

• 4 i : i번째 기차에 앉아있는 승객들을 모두 한 칸씩 앞으로 이동
• trains[i] = trains[i] >> 1;
• 오른쪽 쉬프트는 자동으로 가장 오른쪽 비트가 버려진다.

 

모든 기차의 상태는 20비트 정수로 표현되므로, 최종적으로 Set<Integer>을 사용해 중복되지 않는 좌석 상태만 저장할 수 있다.

 

👉 즉, 각 기차의 최종 상태를 set에 넣고, set의 크기를 출력하면 은 Integer 하수를 건널 수 있는 기차의 수가 된다.

 

위 풀이의 코드를 바탕으로 전체적인 코드를 작성해 보면 아래와 같다.

 

🎯 비트 마스킹 연산

연산	사용 예시
공집합	A = 0
꽉 찬 집합	A = (1 << 10) - 1
원소 추가	A |= (1 << K)
원소 삭제	A &= ~(1 << K)
원소 포함 여부 확인	if ((A & (1 << K)) != 0))
원소 토글 (비트 반전)	A ^= (1 << K)
합집합	A | B
교집합	A & B
차집합	A & (~B)
대칭 차집합	A ^ B
집합의 크기 구하기 (재귀)	bitCount(A)
집합의 크기 구하기 (Java 내장)	Integer.bitCount(A)
최소 원소 찾기	A & (-A)
최소 원소 지우기	A &= (A-1)
부분 집합 순회	for (int subset = A; subset; subset = (subset - 1) & A)

 

✔ 코드

메모리 : 42988KB
시간 : 308ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Set;
import java.util.HashSet;

public class Main {
    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());
        int n = Integer.parseInt(st.nextToken()); // 기차 개수
        int m = Integer.parseInt(st.nextToken()); // 명령의 개수

        // 각 기차의 내부 상태 저장
        trains = new int[n+1];
        for (int i = 0; i < m; i++) {
            excute(br.readLine());
        }

        Set<Integer> set = new HashSet<>();
        for (int i = 1; i <= n; i++) {
            set.add(trains[i]);
        }

        System.out.println(set.size());

        br.close();
    }

    private static void excute(String command) {
        StringTokenizer st = new StringTokenizer(command);

        int t = Integer.parseInt(st.nextToken()); // 명령 번호
        int i = Integer.parseInt(st.nextToken()); // 기차 번호
        int x; // 좌석 번호

        switch (t) {
            case 1 :
                x = Integer.parseInt(st.nextToken())-1;
                trains[i] |= (1 << x);
                break;
            case 2 :
                x = Integer.parseInt(st.nextToken())-1;
                trains[i] &= ~(1 << x);
                break;
            case 3 :
                trains[i] = (trains[i] << 1) & ((1 << 20) - 1);
                break;
            case 4 :
                trains[i] = trains[i] >> 1;
                break;
        }
    }
}

 

요즘 문제를 선택할 때 비트 마스킹 문제 위주로 선택해 풀려고 하는데, 이 문제를 풀면서 비트 마스킹 연산에 대해 조금 더 확실히 이해할 수 있었던 것 같아 포스팅을 해야지 생각했다. 아직까진 문제만 보고 비트 마스킹을 어떻게 활용하면 좋을지 떠올리는 게 쉽지 않지만.. 더 열심히 풀다 보면 감이 오겠지.. ⭐