[백준] 9079번 : 동전 게임 - 자바[Java]

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

9079번: 동전 게임

풀이

모두 같은 면이 보이도록 하는 최소 연산 횟수를 구해야 하기 때문에 BFS를 사용하였다.

또한 이미 탐색했던 상태가 나올 수 있으므로, Map<String, Integer> map을 선언하여 (동전상태, 해당 동전상태가 나오기 위한 최소 연산 횟수)를 저장한다.

동전 상태는 다음과 같이 문자열로 저장된다.

H T T
H T T
T H H

-> HTTHTTTHH

 

BFS 로직

1. 초기 동전상태를 큐와 Map에 추가한다.

2. while문을 사용하여 큐가 빈 상태가 될 때까지 다음을 반복한다.

2-1) 큐에서 현재 동전상태를 꺼낸다.

2-2) 모든 동전이 같은 면이면 현재 동전상태가 되기 위한 최소연산횟수를 반환한다.

2-3) 8가지 연산을 수행한다. 각 연산을 수행하고 난 후의 동전 상태가 map에 없거나, map에 저장된 연산 횟수보다 적은 연산 횟수로 도달한다면, map을 업데이트하고 큐에 추가한다.

 

3. while문이 종료되면, -1을 반환한다.

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test_case = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int t = 0; t < test_case; t++) {
            String coins = "";

            for (int i = 0; i < 3; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 3; j++) {
                    char coin = st.nextToken().charAt(0);
                    coins += coin;
                }
            }

            int minCnt = bfs(coins);
            sb.append(minCnt).append("\n");
        }

        System.out.println(sb);
    }

    static int bfs(String initialCoins) {
        Map<String, Integer> map = new HashMap<>();
        Queue<String> q = new ArrayDeque<>();

        q.add(initialCoins);
        map.put(initialCoins, 0);

        while (!q.isEmpty()) {
            String curCoins = q.poll();
            int cnt = map.get(curCoins);
            //System.out.println(curCoins + " " + map.get(curCoins));

            // 모든 동전이 같은 면이면
            if (isCompleted(curCoins)) {
                return cnt;
            }

            // 8가지 연산 수행 -> 연산을 수행한 동전 상태가 map의 key에 없거나, map에 저장된 연산 횟수보다 적은 연산 횟수로 도달한다면 -> map 업데이트, 큐에 추가
            // 1. 1번째 행 뒤집기
            StringBuilder nextCoins = new StringBuilder(curCoins);
            for (int i = 0; i < 3; i++) {
                char coin = nextCoins.charAt(i);
                nextCoins.deleteCharAt(i);
                if (coin == 'H') {
                    nextCoins.insert(i, 'T');
                } else {
                    nextCoins.insert(i, 'H');
                }
            }

            if (!map.containsKey(nextCoins.toString()) || map.get(nextCoins.toString()) > cnt+1) {
                map.put(nextCoins.toString(), cnt+1);
                q.add(nextCoins.toString());
            }

            // 2. 2번째 열 뒤집기
            nextCoins = new StringBuilder(curCoins);
            for (int i = 3; i < 6; i++) {
                char coin = nextCoins.charAt(i);
                nextCoins.deleteCharAt(i);
                if (coin == 'H') {
                    nextCoins.insert(i, 'T');
                } else {
                    nextCoins.insert(i, 'H');
                }
            }

            if (!map.containsKey(nextCoins.toString()) || map.get(nextCoins.toString()) > cnt+1) {
                map.put(nextCoins.toString(), cnt+1);
                q.add(nextCoins.toString());
            }

            // 3. 3번째 행 뒤집기
            nextCoins = new StringBuilder(curCoins);
            for (int i = 6; i < 9; i++) {
                char coin = nextCoins.charAt(i);
                nextCoins.deleteCharAt(i);
                if (coin == 'H') {
                    nextCoins.insert(i, 'T');
                } else {
                    nextCoins.insert(i, 'H');
                }
            }

            if (!map.containsKey(nextCoins.toString()) || map.get(nextCoins.toString()) > cnt+1) {
                map.put(nextCoins.toString(), cnt+1);
                q.add(nextCoins.toString());
            }

            // 4. 1번째 열 뒤집기
            nextCoins = new StringBuilder(curCoins);
            for (int i = 0; i < 9; i += 3) {
                char coin = nextCoins.charAt(i);
                nextCoins.deleteCharAt(i);
                if (coin == 'H') {
                    nextCoins.insert(i, 'T');
                } else {
                    nextCoins.insert(i, 'H');
                }
            }

            if (!map.containsKey(nextCoins.toString()) || map.get(nextCoins.toString()) > cnt+1) {
                map.put(nextCoins.toString(), cnt+1);
                q.add(nextCoins.toString());
            }

            // 5. 2번째 열 뒤집기
            nextCoins = new StringBuilder(curCoins);
            for (int i = 1; i < 9; i += 3) {
                char coin = nextCoins.charAt(i);
                nextCoins.deleteCharAt(i);
                if (coin == 'H') {
                    nextCoins.insert(i, 'T');
                } else {
                    nextCoins.insert(i, 'H');
                }
            }

            if (!map.containsKey(nextCoins.toString()) || map.get(nextCoins.toString()) > cnt+1) {
                map.put(nextCoins.toString(), cnt+1);
                q.add(nextCoins.toString());
            }

            // 6. 3번째 열 뒤집기
            nextCoins = new StringBuilder(curCoins);
            for (int i = 2; i < 9; i += 3) {
                char coin = nextCoins.charAt(i);
                nextCoins.deleteCharAt(i);
                if (coin == 'H') {
                    nextCoins.insert(i, 'T');
                } else {
                    nextCoins.insert(i, 'H');
                }
            }

            if (!map.containsKey(nextCoins.toString()) || map.get(nextCoins.toString()) > cnt+1) {
                map.put(nextCoins.toString(), cnt+1);
                q.add(nextCoins.toString());
            }

            // 7. 우하향 대각선 뒤집기
            nextCoins = new StringBuilder(curCoins);
            for (int i = 0; i < 9; i += 4) {
                char coin = nextCoins.charAt(i);
                nextCoins.deleteCharAt(i);
                if (coin == 'H') {
                    nextCoins.insert(i, 'T');
                } else {
                    nextCoins.insert(i, 'H');
                }
            }

            if (!map.containsKey(nextCoins.toString()) || map.get(nextCoins.toString()) > cnt+1) {
                map.put(nextCoins.toString(), cnt+1);
                q.add(nextCoins.toString());
            }

            // 8. 좌하향 대각선 뒤집기
            nextCoins = new StringBuilder(curCoins);
            for (int i = 2; i <= 6; i += 2) {
                char coin = nextCoins.charAt(i);
                nextCoins.deleteCharAt(i);
                if (coin == 'H') {
                    nextCoins.insert(i, 'T');
                } else {
                    nextCoins.insert(i, 'H');
                }
            }

            if (!map.containsKey(nextCoins.toString()) || map.get(nextCoins.toString()) > cnt+1) {
                map.put(nextCoins.toString(), cnt+1);
                q.add(nextCoins.toString());
            }
        }

        return -1;
    }

    static boolean isCompleted(String str) {
        char coin = str.charAt(0);
        for (int i = 1; i < str.length(); i++) {
            if (coin != str.charAt(i)) {
                return false;
            }
        }

        return true;
    }
}