[백준] 9207. 페그 솔리테어(골드5)

백준(골드5) - 9207. 페그 솔리테어(골드5)

---

---

풀이

알고리즘 스터디에서 풀었던 문제이다.
백트레킹 + dfs를 적용하면 쉽게 풀 수 있는 문제였다!
문제 푸는 법보다는 해석이 오래걸린것 같다..ㅎ

우선 map에서 핀을 만나면 현재 위치에서 여러가지 방향으로 옮기는 가능성을 봐야하므로 dfs를 실행한다!

for(int i=0; i<5; i++) {
	for(int j=0; j<9; j++) {
		if(map[i][j]=='o') dfs(i,j,pin,0);//현재위치와 pin,move
	}
}

4방탐색으로 갈 수 있는 위치의 좌표의 값을 가져온다.

			int nx = x + dx[d];
			int ny = y + dy[d];

그리고 4방탐색으로 얻은 위치의 좌표(nx,ny)가 map안에 있는지 isValid함수로 확인해준다.
핀을 옮길 위치인 nx2,ny2를 구해주고, nx2,ny2도 nx,ny와 마찬가지로 isValid함수로 범위를 체크해준다.
nx,ny와는 다르게 nx2,ny2는 빈칸이어야 하므로 빈칸인지 확인을 해준다.
현재 위치는 핀을 옮겼기 때문에 빈칸(.)이 되고, 인접한 칸도 핀이 옮기는 과정에서 삭제되므로 빈칸(.)이 된다. 다만 이동한 칸은 빈칸이 아니라 핀(o)을 표시해줘야한다.

if(isValid(nx,ny) && map[nx][ny] == 'o') {
	int nx2 = nx + dx[d];
	int ny2 = ny + dy[d];
	if(isValid(nx2,ny2) && map[nx2][ny2]=='.') {//빈칸일때만 가능
		map[x][y] = '.';//현재위치 빈칸
		map[nx][ny] = '.';//인접한 칸도 빈칸
		map[nx2][ny2] = 'o';//이동한칸 표시

이제 다른 가능성도 체크해줘야 하므로 핀을 찾아 dfs를 실행한다.

for(int i=0; i<5; i++) {
	for(int j=0; j<9; j++) {
		if(map[i][j]=='o') dfs(i,j,pin-1,m+1);
	}
}

dfs에서 돌아온 후에는 다른 실행들을 위해서 map을 복구시켜주는 작업을 해줘야한다.

map[x][y] = 'o';//현재위치 복구
map[nx][ny] = 'o';//인접한 칸 복구
map[nx2][ny2] = '.';//이동한칸 복구

dfs 전체 코드는 아래와 같다.

	private static void dfs(int x, int y, int pin, int m) {
		//기저조건
		if(pin<=pinResult) {
			pinResult = pin;
			moveResult = m;
		}
		
		//4방탐색
		for(int d=0; d<4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			
			if(isValid(nx,ny) && map[nx][ny] == 'o') {
				int nx2 = nx + dx[d];
				int ny2 = ny + dy[d];
				if(isValid(nx2,ny2) && map[nx2][ny2]=='.') {//빈칸일때만 가능
					map[x][y] = '.';//현재위치 빈칸
					map[nx][ny] = '.';//인접한 칸도 빈칸
					map[nx2][ny2] = 'o';//이동한칸 표시
					
					for(int i=0; i<5; i++) {
						for(int j=0; j<9; j++) {
							if(map[i][j]=='o') dfs(i,j,pin-1,m+1);
						}
					}
					
					//복구
					map[x][y] = 'o';//현재위치 복구
					map[nx][ny] = 'o';//인접한 칸 복구
					map[nx2][ny2] = '.';//이동한칸 복구
				}
			}
			
			
		}
		
	}

문제 전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
//.는 빈칸
//o는 핀이 꽂혀있는 칸
//#은 구멍이 없는 칸
//핀의 개수는 최대 8개

public class Main {
	static int N,pinResult,moveResult;
	static char[][] map;
	//상하좌우
	static int[] dx= {-1,1,0,0};
	static int[] dy= {0,0,-1,1};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		for(int t=0; t<N; t++) {
			map = new char[5][9];
			pinResult = moveResult = 0;
			int pin = 0;
			for(int i=0; i<5; i++) {
				String temp = br.readLine();
				for(int j=0; j<9; j++) {
					map[i][j] = temp.charAt(j);
					if(map[i][j]=='o') pin++;
				}
			}
			pinResult = pin;
			
			for(int i=0; i<5; i++) {
				for(int j=0; j<9; j++) {
					if(map[i][j]=='o') dfs(i,j,pin,0);//현재위치와 pin,move
				}
			}
			br.readLine();
			//print();

			System.out.println(pinResult+" "+moveResult);
		}


	}
	private static void dfs(int x, int y, int pin, int m) {
		//기저조건
		if(pin<=pinResult) {
			pinResult = pin;
			moveResult = m;
		}
		
		//4방탐색
		for(int d=0; d<4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			
			if(isValid(nx,ny) && map[nx][ny] == 'o') {
				int nx2 = nx + dx[d];
				int ny2 = ny + dy[d];
				if(isValid(nx2,ny2) && map[nx2][ny2]=='.') {//빈칸일때만 가능
					map[x][y] = '.';//현재위치 빈칸
					map[nx][ny] = '.';//인접한 칸도 빈칸
					map[nx2][ny2] = 'o';//이동한칸 표시
					
					for(int i=0; i<5; i++) {
						for(int j=0; j<9; j++) {
							if(map[i][j]=='o') dfs(i,j,pin-1,m+1);
						}
					}
					
					//복구
					map[x][y] = 'o';//현재위치 복구
					map[nx][ny] = 'o';//인접한 칸 복구
					map[nx2][ny2] = '.';//이동한칸 복구
				}
			}
			
			
		}
		
	}
	
	private static boolean isValid(int nx, int ny) {//map안에 있는지 확인
		return nx>=0 && nx<5 && ny>=0 && ny<9;
	}
	
	private static void print() {
		for(int i=0; i<5; i++) {
			for(int j=0; j<9; j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}

	}

}