Seren dev's blog
article thumbnail

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

 

9079번: 동전 게임

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

www.acmicpc.net

1. 풀이

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

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

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

<code />
H T T H T T T H H

-> HTTHTTTHH

 

1.1. BFS 로직

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

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

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

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

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

 

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

2. 코드

<java />
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; } }
728x90
profile

Seren dev's blog

@Seren dev

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!