BOJ 15787 S2 기차가 어둠을 헤치고 은하수를
- 비트마스킹
- silver2
🔍 문제 설명
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번째 줄까지 각 줄에 명령이 주어진다.
✔ 출력
은하수를 건널 수 있는 기차의 수를 출력하시오.
💡 풀이
처음에는 ArrayList로 풀었다가 시간,공간차이가 많이나서
비트마스킹으로 다시 풀었습니다.
각 기차를 표현하는 map array와 기차를 건널때 상태를 기록하는 visit 배열을 사용했습니다.
기차의 상태를 0이 20개인 bit로 나타낼 수 있으므로 각 명령을 비트마스킹으로 구현했습니다.
- 기차에 사람을 태운다 ⇒ x번째 비트를 1로 바꾸어준다
map[i] |= (1<<x) ; x를 1로바꾸어준뒤 or연산하여 1이 되게 한다. - 기차에 사람을 내린다 => x번째 비트를 0으로 바꾸어준다 => and연산
map[i] &= ~(1<<x) ; x를 1로 바꾼뒤 not처리하고 x번째 비트만 0이 되게하여 and연산한다. - 모두 한칸씩 뒤로 간다 ⇒ 왼쪽 shift하여 한칸씩 이동 후 마지막 0으로 바꾸기
- 모두 한칸씩 앞으로 간다 ⇒ 모두 오른쪽 shift하여 하나씩 이동 후 첫번째 0으로 바꾸기
💡 소스코드
public class Main_BJ_15787_S2_기차가_bit {
/*
N개의 기차. (1번~N번)
기차에는 20개의 일렬로 된 좌석이 있음. 한좌석에 사람 한명 탐
1~N번 기차에 대해 M개의 명령이 주어짐
명령의 종류
1 i x : i번째 기차에 x번째 좌석에 사람을 태워라. 사람 이미 있으면 continue
2 i x : i번째 기차에 x번째 좌석 사람 하차 . 사람 없으면 continue
3 i : i번째 기차에 앉은 승객들이 모두 한칸씩 뒤로감. 만약 20번째 사람있으면 하차
4 i : i번째 기차에 앉은 승객들이 모두 한칸씩 앞으로감. 1번 사람있으면 하차
M 명령 후 1번기차부터 순서대로 은하수를 건넌다
기차는 순서대로 지나가며 기차가 지나갈때의 승객의 상태를 기록
이미 목록에 존재하는 기록이면 해당 기차는 건널 수 없음
은하수를 건널 수 있는 기차의 수는?
*/
static int N,M, ans;
static int map[];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); //기차의 수
M = Integer.parseInt(st.nextToken()); //명령의 수
map = new int[N+1]; //1~N개의 기차. 각 기차에는 20개의 좌석
for (int m = 0; m < M; m++) {
st = new StringTokenizer(br.readLine());
int cmd = Integer.parseInt(st.nextToken());
if(cmd==1) {
int i = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
//i번째 기차에 x번째 좌석에 사람을 태워라. 사람 이미 있으면 continue => or
map[i] = map[i] | (1<<x);
}else if(cmd==2) {
int i = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
//i번째 기차에 x번째 좌석 사람 하차 => and
map[i] = map[i] & ~(1<<x);
}else if(cmd==3) {
int i = Integer.parseInt(st.nextToken());
//모두 한칸씩 뒤로감.
map[i] = map[i] << 1;
//만약 20번째 사람있으면 하차
map[i] = map[i] & ((1<<21)-1);
}else if(cmd==4) {
int i = Integer.parseInt(st.nextToken());
//모두 한칸씩 앞으로
map[i] = map[i] >> 1;
map[i] = map[i] & ~1;
}
}
//M 명령 후 1번기차부터 순서대로 은하수를 건넌다
boolean visited[] = new boolean[1 << 21];
for (int i = 1; i <= N; i++) {
if(visited[map[i]]) continue;
else {
ans++;
visited[map[i]]=true;
}
}
System.out.println(ans);
}
}💯 채점 결과
39868 312
