[백준] 9079 동전 게임 java

   시간 제한                   메모리 제한                      제출                  정답               맞힌 사람                    정답 비율

 

1 초

128 MB

379

258

200

68.966%

문제

상우는 재미있는 게임을 생각해냈다. 동전 9개를 아래 그림과 같이 3행 3열로 놓는다. H는 앞면, T는 뒷면을 의미한다.

H T T
H T T
T H H

게임의 목적은 이 동전의 모양을 모두 같은 면(H나 T)이 보이도록 하는 것이다. 단, 하나의 동전만을 뒤집을 수는 없고, 한 행의 모든 동전, 한 열의 모든 동전 또는 하나의 대각선 상의 모든 동전을 한 번에 뒤집어야 한다. 그런 식으로 세 개의 동전을 뒤집는 것을 '한 번의 연산'으로 센다. 상우는 이것을 최소 횟수의 연산으로 실행하고 싶어한다. 오랜 시간 생각한 끝에 위의 경우는 두 번의 연산으로 가능하다는 것을 알아냈고, 또, 이것이 최소인 것도 알아내었다.

H T T   T T T   T T T
H T T→ T T T →T T T
T H H   H H H   T T T

또한, 모두 같은 면으로 만드는 것이 불가능한 모양이 있다는 것도 알아내었다. 다음이 그 예이다.

T H H
H H H
H H H

상우를 도울 수 있는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 세 줄로 이루어지며, 한 줄에 세 개의 동전모양이 주어지는데, 각각의 동전 표시 사이에는 하나의 공백이 주어진다.

출력

각 테스트 케이스에 대해서, 모두 같은 면이 보이도록 만들기 위한 최소 연산 횟수를 출력하고, 불가능한 경우에는 -1을 출력한다.

풀이

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

class Info {
    StringBuilder state;
    int cnt;
    Info(StringBuilder sb, int cnt) {
        this.state = sb;
        this.cnt = cnt;
    }
}

public class Main {
    static final int N = 3;
    static BufferedReader br;
    static StringTokenizer st;
    static int T;
    static Set<String> set;
    static StringBuilder ret;

    public static void main(String[] args) throws IOException {
        init();
        solve();
        System.out.print(ret.toString());
    }

    static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        ret = new StringBuilder();
        T = Integer.parseInt(br.readLine());
    }

    static void solve() throws IOException{
        while(T-- > 0) {
            StringBuilder sb = new StringBuilder();
            set = new HashSet<>();
            for(int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j = 0; j < N; j++) {
                    sb.append(st.nextToken());
                }
            }
            int res = bfs(sb);
            if(res == -1) {
                ret.append("-1"+"\n");
            } else {
                ret.append(res+"\n");
            }
        }
    }

    static int bfs(StringBuilder start) {
        Queue<Info> q = new LinkedList<>();
        q.add(new Info(start, 0));
        while(!q.isEmpty()) {
            Info cur = q.poll();
            if(cur.state.toString().equals("HHHHHHHHH") || cur.state.toString().equals("TTTTTTTTT")) {
                return cur.cnt;
            }

            for(int i = 0; i < 8; i++) {
                if(i < 3) {
                    turnWidth(cur.state, i);
                } else if(i < 6) {
                    turnHeight(cur.state, i);
                } else {
                    turnDiaglnal(cur.state, i);
                }
                if(!set.contains(cur.state.toString())) {
                    q.add(new Info(new StringBuilder(cur.state.toString()), cur.cnt+1));
                    set.add(cur.state.toString());
                }

                if(i < 3) {
                    turnWidth(cur.state, i);
                } else if(i < 6) {
                    turnHeight(cur.state, i);
                } else {
                    turnDiaglnal(cur.state, i);
                }
            }
        }
        return -1;
    }

    static void swap(StringBuilder sb, int idx) {
        if(sb.charAt(idx) == 'H') {
            sb.setCharAt(idx, 'T');
        } else {
            sb.setCharAt(idx, 'H');
        }
    }

    static void turnWidth(StringBuilder s, int idx) {
        if(idx == 0) {
            swap(s,0);
           swap(s,1);
           swap(s,2);
           return;
        }
        if(idx == 1) {
            swap(s,3);
            swap(s,4);
            swap(s,5);
            return;
        }
        if(idx == 2) {
            swap(s,6);
            swap(s,7);
            swap(s,8);
            return;
        }
    }

    static void turnHeight(StringBuilder s, int idx) {
        if(idx == 3) {
            swap(s,0);
            swap(s,3);
            swap(s,6);
            return;
        }
        if(idx == 4) {
            swap(s,1);
            swap(s,4);
            swap(s,7);
            return;
        }
        if(idx == 5) {
            swap(s,2);
            swap(s,5);
            swap(s,8);
            return;
        }
    }

    static void turnDiaglnal(StringBuilder s, int idx) {
        if(idx == 6) {
            swap(s,0);
            swap(s,4);
            swap(s,8);
        } else {
            swap(s, 2);
            swap(s, 4);
            swap(s, 6);
        }
    }
}

완전탐색 bfs 문제였다.

 

입력값과 시간복잡도가 느슨해서 실버인 문제지만 문제풀이 난이도는 체감 상 골드5~4 쯤 되는 것 같다. 그래서 처음엔 백트래킹으로 해보려다가 계속 꼬여서 다른 분의 풀이 아이디어를 보고 풀었다. bfs가 다양하게 쓰일 수 있다는걸 알 수 있는 좋은 문제다.

 

현재 상태에서 갈 수 있는 모든 방향을 구해나가야 최소 연산 횟수를 알 수 있다. 컴퓨터는 어떤 방법이 최적인지 알지 못하기 때문이다. 문제에서는 3개의 동전이 뒤집는 것을 한번의 연산이라고 했으니 경우의 수는 가로 3개, 세로 3개, 대각선 2개 총 8개이다. 

 

8방향으로 각각 변환된 상태에서 이미 방문한 적 있는 상태는 큐에 넣지 않으므로 중복을 방지해줬다. 그리고 큐에 넣은 다음에는 다음 방향으로 또 변환해줘야 하기 때문에 다시 원 상태로 돌려준다.

 

핵심은 bfs를 통해 최단거리를 구한다는 점과 2차원 배열 형태의 정보를 어떤 자료구조를 이용해 저장할 것인지 (나는 문자열을 사용했지만 비트마스크를 이용할 수도 있다.), 중복 처리(배열 or SET) 등등이 있다.