[백준]20209: 스트레이트 스위치 게임(java)

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

20209번: 스트레이트 스위치 게임

문제

어느 나라에는, 여러 큐브와 연결된 스위치를 적절한 횟수만큼 눌러 모든 큐브 위에 적힌 숫자를 동일하게 만드는 게임이 있다.

그중 스트레이트 스위치라는 게임이 있다.

스트레이트 스위치 게임은 다음의 규칙을 따른다.

• 선분 위에 여러 개의 큐브가 일렬로 놓여 있고, 이 큐브 중 특정 큐브들과 연결된 스위치들이 여러 개 존재한다.
• i 번 스위치를 한 번 누르면 해당 스위치와 연결된 모든 큐브 위의 숫자가 각각 i 만큼 증가한다.
• 큐브 위의 숫자는 0, 1, 2, 3, 4만 존재할 수 있으며 스위치를 눌러 큐브 위의 숫자 K가 4를 초과하면 K를 5로 나눈 나머지로 즉시 초기화된다.
• 스위치를 한 번 누를 때, 반드시 단 한 개의 스위치만 누를 수 있다.
• 같은 번호의 큐브가 한 스위치에 여러 번 연결되어있는 경우는 없다.
• 각 스위치를 누를 수 있는 횟수의 제한은 없다.
• 큐브 위에 쓰여 있는 모든 숫자가 동일해지는 순간, 게임은 종료된다.

이 스트레이트 스위치 게임의 국가 대표 선수인 당신은 세계 대회에서 우수한 성적을 거두기 위해 전략을 세워야 한다.

큐브의 개수와 현재 큐브 위에 쓰여 있는 숫자들, 그리고 스위치-큐브 간의 연결 정보가 주어질 때

이 큐브들 위에 쓰여 있는 숫자를 모두 동일하게 만들기 위해 눌러야 하는 스위치의 최소 횟수를 구해보자.

입력

첫 번째 줄에는 큐브의 개수 N과 스위치의 개수 K가 주어진다. (1 ≤ N, K ≤ 8)

두 번째 줄에는 현재 N개의 큐브 위에 쓰여 있는 숫자 a1 a2 a3 ... aN 가 한 줄에 주어진다. (0 ≤ ai ≤ 4)

세 번째 줄 부터 K+3번째 줄에는, 1번 스위치부터 K번 스위치까지 각 스위치에 연결된 큐브의 개수(Bm)와, 연결된 큐브의 번호들(bj)이 각 줄 마다 주어진다. (1 ≤ Bm ≤ 8, 1 ≤ bj ≤ N)

출력

첫 번째 줄에 큐브들 위에 쓰여 있는 숫자를 모두 동일하게 만들기 위해 눌러야 하는 스위치의 최소 횟수를 출력한다.

(단, 주어진 스위치들을 아무리 누르더라도 모든 큐브의 숫자를 동일하게 만들 수 없는 경우에는 -1을 출력한다.)

예제 입력 1 

4 2
0 1 0 1
2 1 3
3 1 2 3

예제 출력 1 

1

1번 버튼을 누르면 1, 3번째 큐브의 숫자가 1 증가한다. 따라서 모든 큐브의 숫자가 1로 같게 된다.

한 번 미만으로 버튼을 눌러 모든 숫자를 같게 만들 수는 없다. 따라서 정답은 1이다.

예제 입력 2 

2 2
1 2
2 1 2
2 1 2

예제 출력 2 

-1

모든 스위치를, 몇 번을 누르더라도 큐브 위의 숫자를 모두 같게 할 수 없다. 따라서 -1을 출력해야한다.

---

풀이

bfs를 통해 각 단계별로 switch를 종류별로 눌러준다.

이 때 평소 좌표로 이미 방문한 곳을 백트래킹 해주었다면 여기서는 String형태로 이미 만들었던 큐브 모양은 더 이상 만들지 않도록 해준다. (HashSet 자료구조를 String형태로 사용하였다.)

큐브는 0, 1, 2, 3, 4 를 순환해야함을 주의한다.

가장 빠르게 같은 숫자를 만들었으면 더 이상 순환하지 않아도 된다.

 

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class BJ_G3_20209_스트레이트스위치게임 {
    static int N, K;
    static ArrayList<Integer>[] switchList;
    static HashSet<String> visited = new HashSet<>();

    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());
        K = Integer.parseInt(st.nextToken());
        String str = "";
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            str += Integer.parseInt(st.nextToken());
        }
        switchList = new ArrayList[K];
        for(int i=0; i<K; i++) {
            switchList[i] = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            int size = Integer.parseInt(st.nextToken());
            for(int j=0; j<size; j++) {
                switchList[i].add(Integer.parseInt(st.nextToken()) - 1);
            }
        }

        System.out.println(bfs(str));
    }

    private static int bfs(String start) {
        Queue<String> q = new LinkedList<>();
        q.add(start);
        visited.add(start);
        int depth = 0;
        while(!q.isEmpty()) {
            int size = q.size();

            for(int s = 0; s<size; s++) {
                String now = q.poll();
                if(isFinished(now)) {
                    return depth;
                }
                for(int i=0; i<switchList.length; i++) {
                    StringBuilder tmp = new StringBuilder(now);
                    for(int j=0; j<switchList[i].size(); j++) {
                        char nowChar = tmp.charAt(switchList[i].get(j));
                        int num = ((nowChar-'0') + i+1)%5;
                        tmp.setCharAt(switchList[i].get(j), (char)(num+'0'));
                    }
                    if(visited.contains(tmp.toString())) continue;
                    visited.add(tmp.toString());
                    q.add(tmp.toString());
                }
            }
            depth++;
        }
        return -1;
    }
    private static boolean isFinished(String str) {
        for(int i=1; i<str.length(); i++) {
            if(str.charAt(0) != str.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}