백준 9207번 페그 솔리테어 [JAVA]

문제

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

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

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

 

입력

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

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

 

출력

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

 

예제

풀이 방법

핀을 적절히 움직여서 게임판에 남아있는 핀의 개수를 최소로하는 동시에, 최소로 남기기 위해 필요한 최소 이동 횟수를 구하는 문제였습니다. 

 

게임판의 존재하는 핀의 개수를 카운트해주고, remainPin 변수에 핀의 개수를 넣어주었습니다. 게임판의 해당 위치가 핀이 꽂혀있는 칸이라면 dfs() 메서드를 통해 현재 위치의 다음 위치가 게임판의 범위를 넘지 않으면서 핀이 꽂혀있는 칸이고 그 다다음 칸이 빈칸이라면 해당 위치의 핀을 이동할 수 있으므로, 이동시켜주고 핀의 개수를 하나 줄이고, 움직인 수를 하나 늘린 뒤, 다음 게임판에서 핀이 꽂혀있는 위치를 찾은 뒤 위에 과정을 반복해주었습니다. 과정이 끝난 후, 마지막으로 남아있는 핀의 개수와, 이동 횟수를 출력해주었습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main_BJ_9207_페그솔리테어 {
    
    static char [][] map;
    static int xx=5,yy=9,remainPin, move;
    
    static int [] dx = {-1,0,1,0};
    static int [] dy = {0,1,0,-1};
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        
        for(int tc=0; tc<T;tc++) {
            map = new char[xx][yy];
            
            int pin=0;
            for(int i=0;i<xx;i++) {
                String str = br.readLine();
                for(int j=0;j<yy;j++) {
                    map[i][j] = str.charAt(j);
                    if(map[i][j]=='o') pin++;
                }
            }
            
            remainPin = pin;
            
            for(int i=0;i<xx;i++) {
                for(int j=0;j<yy;j++) {
                    if(map[i][j]=='o') dfs(i,j,pin,0);
                }
            }
            
            br.readLine();
            
            sb.append(remainPin+" "+move+"\n");
        }
        
        System.out.println(sb.toString());
 
    }
    
    public static void dfs(int x, int y , int remain, int moveCnt) {
        if(remain<=remainPin) {
            remainPin = remain;
            move = moveCnt;
        }
        
        for(int d=0;d<4;d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            
            if(range(nx,ny) && map[nx][ny]=='o') {
                int nnx = nx +dx[d];
                int nny = ny +dy[d];
                
                if(range(nnx,nny) && map[nnx][nny]=='.') {
                    map[x][y]=map[nx][ny]='.';
                    map[nnx][nny]='o';
                    
                    for(int i=0;i<xx;i++) {
                        for(int j=0;j<yy;j++) {
                            if(map[i][j]=='o') dfs(i,j,remain-1,moveCnt+1);
                        }
                    }
                    
                    map[x][y]=map[nx][ny]='o';
                    map[nnx][nny]='.';
                }
            }
            
        }
    }
    
    public static boolean range(int x, int y) {
        return x>=0 && x<xx && y>=0 && y<yy;
    }
 
}