BOJ 9207

28 Jan 2020 • ProblemSolving

페그 솔리테어

문제출처

1.설계(20)

  • 문제 해석

    • 2차원 배열에서 각 구멍에 핀을 하나 꽂을 수 있습니다.
    • 핀은 수평,수직방향으로 인접한 핀을 뛰어넘어서 그 핀의 다음칸으로 이동가능합니다.
    • 이동할 칸은 비어있어야 하고, 인접한 핀은 제거됩니다.
    • 최소한의 핀이 남게 하기 위한 최소 이동횟수를 구하는 문제입니다.

  • 설계

    • 각 핀을 상하좌우 이동시키면서 남아있는 핀의 최솟값과 최소이동 횟수를 백트래킹으로 구현할 수 있습니다.
    • 상하좌우 중 핀이 있는지 검토한 후, 핀을 이동 및 제거합니다.
    • 모두 떨어져있는 핀들이 있는 경우를 체크하기 위하여 flag를 설정하여 모든 핀이 이동할 수 없으면 return 합니다.
    • 핀이 1개 이하로 남았으면 더이상 진행할 수 없으므로 return 합니다.
    • 편의성을 위해서 map을 int형으로 바꾸고, 각 핀에 번호를 부여하였습니다. 또한 좌표를 저장하기 위한 구조체를 선언하였습니다.

2.구현(60)

  • 코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>

#define INF 987654321
using namespace std;

int map[5][9];

struct node {
	int x;
	int y;
};
struct info {
	int x;
	int y;
	int idx;
};
int idx = 1;
node pin[9];

int N;
int max_pin = INF;
int ans = INF;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
bool is_range(int nx, int ny) {
	if (nx < 0 || ny < 0 || nx >= 5 || ny >= 9) return false;
	return true;
}
bool can_move(int x, int y, int dir) {
	int nx = x + dx[dir];
	int ny = y + dy[dir];
	
	if (!is_range(nx, ny) || map[nx][ny] <= 0) return false;
	
	nx += dx[dir];
	ny += dy[dir];
	if (!is_range(nx, ny) || map[nx][ny] != 0) return false;
	return true;
}


void dfs(int remain, int move) {
	if (max_pin < remain && ans < move) return;
	if (remain <= 1) {
		if (max_pin > remain) {
			max_pin = remain;
			ans = move;
		
		}
		else if (max_pin == remain) {
			if (ans > move) ans = move;
		}
		
		return;
	}
	bool flag = false;
	for (int i = 1; i < idx; i++) {
		// 지워진 핀이면 건너뜀
		if (pin[i].x == -1) continue;
		for (int k = 0; k < 4; k++) {
			if (can_move(pin[i].x, pin[i].y, k)) {
				info tmp[2];
				
				int nx = pin[i].x + dx[k];
				int ny = pin[i].y + dy[k];
				tmp[0] = { pin[map[nx][ny]].x,pin[map[nx][ny]].y,map[nx][ny] };
				
				pin[map[nx][ny]] = { -1,-1 };
				map[nx][ny] = 0;
				nx += dx[k];
				ny += dy[k];
				tmp[1] = { pin[i].x,pin[i].y, i};
				map[pin[i].x][pin[i].y] = 0;
				pin[i] = { nx,ny };
				map[nx][ny] = i;
				
				flag = true;
				dfs(remain-1,move+1);
				map[pin[i].x][pin[i].y] = 0;
				pin[i].x = tmp[1].x;
				pin[i].y = tmp[1].y;
				map[pin[i].x][pin[i].y] = i;
				map[tmp[0].x][tmp[0].y] = tmp[0].idx;
				pin[tmp[0].idx] = { tmp[0].x,tmp[0].y };

			}
		}
	}
	if (!flag) {
		if (max_pin > remain) {
			max_pin = remain;
			ans = move;

		}
		else if (max_pin == remain) {
			if (ans > move) ans = move;
		}
		return;
	}
}
int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		idx = 1;
		max_pin = INF;
		ans = INF;
		memset(map, 0, sizeof(map));
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 9; j++) {
				char tmp;
				scanf(" %1c", &tmp);

				if (tmp == 'o') {
					map[i][j] = idx;
					pin[idx++] = { i,j };
				}
				else if (tmp == '#') {
					map[i][j] = -1;
				}
			}
		}
		
		dfs(idx - 1, 0);
		cout << max_pin << " " << ans << "\n";
	}
	
	return 0;
}

  • 디버깅

    • 문제에서 언급한 부분중에 인접한 핀을 뛰어 넘어서 그 다음칸에 핀이 이동하는 부분이 있는데, 수평 또는 수직으로 인접한 핀이 연달아 있으면 계속 뛰어넘는 것으로 이해를 잘못하여서 이를 찾는데 오랜시간이 걸렸습니다.

    • 최소 핀의 개수와 움직인 횟수를 갱신할 때, 최소 핀의 개수가 갱신되면 움직인 횟수의 최소 여부와 상관없이 갱신을 해야한다는 부분이 헷갈렸습니다.

    • 또한, 최소 핀의 개수가 같은 경우 움직인 횟수의 최솟값을 따로 갱신을 해주어야 했습니다.

  • 제출결과

    0ms

3.마무리

  • 백트래킹 문제로, map의 범위와 최대 핀의 개수가 작아서 시간복잡도를 신경쓰지 않을 수 있었습니다.
    문제를 잘못이해하여 구현이 오래걸렸고, 최솟값 갱신 부분이 까다로워서 디버깅을 오래하게 되었습니다.
    구현연습하기에 아주 좋은 문제인 것 같습니다.
 BOJ

Related Posts