[1일 1알고] G4 9207 페그 솔리테어

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

 

문제와 조건을 이해하면 간단하게 해결할 수 있는 문제입니다.

 

다만 저는 문제 이해에 시간이 오래걸렸네요

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

이 말에서 핀을 적절히 움직이라는 것이 전체 보드 내에서 핀을 자유롭게 배치하라는 말인 줄 알았는데, 초기 핀은 고정이고 말그대로 "적절히" 움직이라는 것이었습니다 ㅎㅎ...

 

보드의 크기가 세로 r = 5, 가로 c = 9로 고정이기 때문에 dfs, 백트래킹을 통해 조건에 맞게 탐색하면 답은 간단히 나옵니다.

---

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

int R = 5, C = 9;
char board[5][9];
int pin_cnt = 0;
int result = 0;

int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, -1, 0, 1 };

void dfs(int mov);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        result = 0;
        pin_cnt = 0;

        for (int r = 0; r < R; ++r)
        {
            for (int c = 0; c < C; ++c)
            {
                cin >> board[r][c];
                if (board[r][c] == 'o')
                    ++pin_cnt;
            }
        }

        dfs(0);
        cout << pin_cnt - result << ' ' << result << '\n';
    }

    return 0;
}

void dfs(int mov)
{
    result = max(result, mov);
    if (mov == pin_cnt - 1)
        return;

    for (int r = 0; r < R; ++r)
    {
        for (int c = 0; c < C; ++c)
        {
            if (board[r][c] != 'o') continue;
            for (int i = 0; i < 4; ++i)
            {
                int nr = r + dr[i] * 2;
                int nc = c + dc[i] * 2;

                if (nr >= 0 && nr < R && nc >= 0 && nc < C &&
                    board[r][c] == 'o' &&
                    board[r + dr[i]][c + dc[i]] == 'o' &&
                    board[nr][nc] == '.')
                {
                    board[r][c] = '.';
                    board[r + dr[i]][c + dc[i]] = '.';
                    board[nr][nc] = 'o';

                    dfs(mov + 1);

                    board[nr][nc] = '.';
                    board[r + dr[i]][c + dc[i]] = 'o';
                    board[r][c] = 'o';
                }
            }
        }
    }
}

 

매번 전체 보드를 전체 탐색하는게 약간 못마땅하긴한데 별다른 방법이 떠오르진 않네요