9207번: 페그 솔리테어 - Java

9207번: 페그 솔리테어

사진: Unsplash의Immo Wegmann

 

 

문제

페그 솔리테어는 구멍이 뚫려있는 이차원 게임판에서 하는 게임이다. 각 구멍에는 핀을 하나 꽂을 수 있다.

핀은 수평, 수직 방향으로 인접한 핀을 뛰어넘어서 그 핀의 다음 칸으로 이동하는 것만 허용된다. 인접한 핀의 다음 칸은 비어있어야 하고 그 인접한 핀은 제거된다.

현재 게임판에 꽂혀있는 핀의 상태가 주어진다. 이때, 핀을 적절히 움직여서 게임판에 남아있는 핀의 개수를 최소로 하려고 한다. 또, 그렇게 남기기 위해 필요한 최소 이동횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 1 ≤ N ≤ 100이 주어진다. 각 테스트 케이스는 게임판의 초기 상태이다.

게임판은 모두 같은 모양을 가진다. (예제 참고) '.'는 빈 칸, 'o'는 핀이 꽂혀있는 칸, '#'는 구멍이 없는 칸이다. 핀의 개수는 최대 8이며, 각 테스트 케이스는 빈 줄로 구분되어져 있다.

출력

각 테스트 케이스에 대해서, 핀을 움직여서 남길 수 있는 핀의 최소 개수와 그 개수를 만들기 위해 필요한 최소 이동 횟수를 출력한다.

---

 

나의 풀이

백트래킹과 DFS를 사용해서 완전탐색으로 풀어야하는 구현 문제입니다.

 

문제에서 요구하는 부분의 알고리즘은 어렵지는 않습니다. 다만 반복문을 많이 사용해야 하고 조건문이 많이 들어가기 때문에 길을 읽어버릴 수 있습니다. 

 

미리 기능 목록과 조건을 잘 정리한다면 해결할 수 있습니다.

import java.io.*;

public class Main {

    static int[] dx = new int[]{0, 1, 0, -1};
    static int[] dy = new int[]{1, 0, -1, 0};

    static int n;

    static int minPin = 8;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        int k = 0;
        while (true) {
            char[][] board = new char[5][9];
            for (int i = 0; i < 5; i++) {
                board[i] = br.readLine().toCharArray();
            }

            int cnt = 0;
            for (char[] boardLine : board) {
                for (char x : boardLine) {
                    if (x == 'o') {
                        cnt++;
                    }
                }
            }
            minPin = cnt;
            dfs(board, minPin);
            System.out.println(minPin + " " + (cnt - minPin));
            k++;
            if (k == n) {
                break;
            }
            br.readLine();
        }
    }

    static void dfs(char[][] board, int pin) {
        if (pin < minPin) {
            minPin = pin;
        }

        for (int x = 0; x < 5; x++) {
            for (int y = 0; y < 9; y++) {
                if (board[x][y] == 'o') {
                    for (int i = 0; i < 4; i++) {
                        int nextX = x + dx[i];
                        int nextY = y + dy[i];
                        int newX = nextX + dx[i];
                        int newY = nextY + dy[i];

                        if (checkTarget(board, nextX, nextY, 'o') &&
                                checkTarget(board, newX, newY, '.')) {
                            board[x][y] = '.';
                            board[nextX][nextY] = '.';
                            board[newX][newY] = 'o';
                            dfs(board, pin - 1);
                            board[x][y] = 'o';
                            board[nextX][nextY] = 'o';
                            board[newX][newY] = '.';
                        }
                    }
                }
            }
        }
    }

    static boolean checkTarget(char[][] board, int x, int y, char target) {
        if (x < 0 || x >= 5 || y < 0 || y >= 9) {
            return false;
        }

        return board[x][y] == target;
    }
}