[BOJ] 백준 15787 - 기차가 어둠을 헤치고 은하수를 풀이

1. 문제

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

15787번: 기차가 어둠을 헤치고 은하수를

 

2. 풀이

백준 실버 2에 해당하는 문제이다.

하나의 열차가 20칸이고 입력으로 열차의 갯수가 주어지므로 열차들을 담을 List를 선언하고 초기화한다.(착석 OR 비착석이므로 boolean 배열로 선언해줬다.)
그 후 명령을 받으면서 각 일을 수행하면된다.

(1) 명령 1
  - 명령 1은 주어진 기차의 넘버와 좌석의 넘버에 맞는 곳에 true를 넣었다. 이미 true라면 패스.

(2) 명령 2
  - 명령 2는 주어진 기차의 넘버와 좌석의 넘버에 맞는 곳에 false를 넣었다. 이미 false라면 패스.

(3) 명령 3
  - 명령 3은 주어진 기차 넘버에 맞는 기차를 선택하여 좌석을 오른쪽으로 한 칸씩 밀어주었다. ( 코드의 case 3)

(4) 명령 4
  - 명령 3은 주어진 기차 넘버에 맞는 기차를 선택하여 좌석을 왼쪽으로 한 칸씩 밀어주었다. ( 코드의 case 4)

명령이 끝나면 이제 기차가 통과할 수 있는지 판단해야 한다.
먼저 기차가 통과한 기록을 저장할 History List를 선언하고 1번 기차를 넣어준다. (1번 기차는 전에 통과한 기차의 기록이 없기 때문이다.)
그 후 2번 기차부터 History List를 하나씩 탐색하면서 같은 좌석 배치를 갖는 배열이 있는지 판단한다.
같은 좌석 배치를 갖는 배열이 있다면 통과하고 없다면 result에 +1을 해준 후 History List에 기록하면 된다.

마지막으로 result을 출력하면 정답!!

(생각보다 소요 시간이 오래 걸렸다... 시간을 확 개선하신 분이 있다면 댓글로 알려주시면 감사하겠습니다. ^^7)

 

3. 소스 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int result = 1;

        List<boolean[]> trains = new ArrayList<>();
        List<boolean[]> trainsHistory = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            boolean[] inputArr = new boolean[20];

            for (int j = 0; j < 20; j++) {
                inputArr[j] = false;
            }

            trains.add(inputArr);
        }

        for (int p = 0; p < M; p++) {
            st = new StringTokenizer(br.readLine());

            int order = Integer.parseInt(st.nextToken());
            int trainNum = Integer.parseInt(st.nextToken());
            int sitNum = 0;

            if (order == 1 || order == 2) {
                sitNum = Integer.parseInt(st.nextToken());
            }

            boolean[] arr = trains.get(trainNum - 1);
            switch (order) {
                case 1:
                    if (!arr[sitNum - 1]) {
                        arr[sitNum - 1] = true;
                    }
                    break;

                case 2:
                    if (arr[sitNum - 1]) {
                        arr[sitNum - 1] = false;
                    }
                    break;

                case 3:
                    for(int i = 19; i >= 1; i--) {
                        arr[i] = arr[i - 1];
                    }
                    arr[0] = false;
                    break;

                case 4:
                    for(int i = 0; i < 19 ; i++) {
                        arr[i] = arr[i + 1];
                    }
                    arr[19] = false;
                    break;
            }
        }

        trainsHistory.add(trains.get(0));
        for (int k = 1; k < trains.size(); k++) {
            boolean[] train = trains.get(k);
            boolean flag = false;

            for (int i = 0; i < trainsHistory.size(); i++) {
                boolean[] history = trainsHistory.get(i);

                if (Arrays.equals(history, train)) {
                    flag = true;
                    break;
                }
            }

            if (!flag) {
                result += 1;
                trainsHistory.add(train);
            }
        }

        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }
}