BJ G5 9207 페그솔리테어

BJ G5 9207 페그솔리테어

 

 

문제링크

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

9207번: 페그 솔리테어

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=Jg1eq0U-N-M

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;

/**
 * @author itsmeyjc
 * @since 2020. 5. 10.
 * @see https://www.acmicpc.net/problem/9207
 * @mem 15816
 * @time 100
 * @caution #dfs
 */
public class BJ_G5_9207_페그솔리테어 {
    static StringBuilder output = new StringBuilder();

    static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    static char[][] map = new char[5][9];

    // 남겨진 최소 핀의 개수와 그때까지 이동한 회수
    static int minPin = 0, totalMoveCnt;

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

        int T = Integer.parseInt(input.readLine());
        for (int t = 0; t < T; t++) {

            minPin = Integer.MAX_VALUE;

            // 기본 핀의 개수
            int pinCnt = 0;

            for (int r = 0; r < map.length; r++) {
                map[r] = input.readLine().toCharArray();
                for (int c = 0; c < 9; c++) {
                    if (map[r][c] == 'o') {
                        pinCnt++;
                    }
                }
            }
            // 한줄 공백
            input.readLine();

            for (int r = 0; r < 5; r++) {
                for (int c = 0; c < 9; c++) {
                    if (map[r][c] == 'o') {
                        dfs(r, c, 0, pinCnt);
                    }
                }
            }

            output.append(minPin).append(" ").append(totalMoveCnt).append("\n");
        }
        System.out.println(output);
    }

    static void dfs(int row, int col, int moveCnt, int pin) {

        if (pin < minPin) {
            minPin = pin;
            totalMoveCnt = moveCnt;
        }

        // 일단 사방 탐색으로 가볼 수 있어야 한다.
        for (int d = 0; d < dirs.length; d++) {
            int nr = row + dirs[d][0];
            int nc = col + dirs[d][1];
            // 새로운 점이 범위 안에 있고 다른 핀이라면...
            if (isIn(nr, nc) && map[nr][nc] == 'o') {
                // 그런데 그 방향으로 다음 한 칸을 넘을 수 있는지 살펴봐야 한다.
                int nr2 = nr + dirs[d][0];
                int nc2 = nc + dirs[d][1];

                // 다행이 넘어갈 곳이 빈곳이라면 가보자.
                if (isIn(nr2, nc2) && map[nr2][nc2] == '.') {
                    // 변경 처리
                    map[row][col] = map[nr][nc] = '.';
                    map[nr2][nc2] = 'o';

                    // 또다른 핀을 찾아서....
                    for (int r = 0; r < 5; r++) {
                        for (int c = 0; c < 9; c++) {
                            if (map[r][c] == 'o') {
                                // 이제는 회수가 1 증가 되었고 핀도 하나 줄어든다.
                                dfs(r, c, moveCnt + 1, pin - 1);
                            }
                        }
                    }
                    // 원상 복구
                    map[row][col] = map[nr][nc] = 'o';
                    map[nr2][nc2] = '.';
                }
            }
        }
    }


    static boolean isIn(int row, int col) {
        return 0 <= row && row < 5 && 0 <= col && col < 9;
    }

    private static String src = "3\r\n" +
                                "###...###\r\n" +
                                "..oo.....\r\n" +
                                ".....oo..\r\n" +
                                ".........\r\n" +
                                "###...###\r\n" +
                                "\r\n" +
                                "###...###\r\n" +
                                "..oo.o...\r\n" +
                                "...o.oo..\r\n" +
                                "...oo....\r\n" +
                                "###...###\r\n" +
                                "\r\n" +
                                "###o..###\r\n" +
                                ".o.oo....\r\n" +
                                "o.o......\r\n" +
                                ".o.o.....\r\n" +
                                "###...###";
}