[1035] 조각 움직이기

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

1035번: 조각 움직이기

<문제>

입력된 조각의 개수를 S라고 하면, 25^S로 완전탐색하면 된다.

각 조각이 어느위치로 움직일지가 결정되면, 모든 S개의 조각에 대해서 맨해튼 거리를 합한것이 score가 된다.

해당 score를, 모든 조각이 붙어있는 경우에 한해서 ans를 최소로 업데이트하면 된다.

조각이 붙어있는지를 판정하는건 실버정도의 문제, dfs든 bfs든 간단히 판정할 수 있다.

여러모로, 구현난이도가 높은데.. vector를 전역에 두고 그때그때 push()와 pop()을 하면 그나마 편하다.

 

<소스코드>

#include <bits/stdc++.h>

using namespace std;

using pi = pair<int, int>;

const int dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};

bool board[5][5];

int S, ans = 1234;

vector<pi> s, e;

bool isValid(void) {

    bool vst[5][5] = {0};

    queue<pi> q;

    q.push(e.front());

    memset(vst, 0, sizeof(vst));

    vst[e.front().first][e.front().second] = true;

    int i, j, cnt = 1;

    while (!q.empty()) {

        pi cur = q.front();

        q.pop();

        for (int i = 0; i < 4; i++) {

            int y = cur.first + dy[i];

            int x = cur.second + dx[i];

            if (y < 0 || x < 0 || y >= 5 || x >= 5) continue;

            if (board[y][x] == true && vst[y][x] == false) {

                vst[y][x] = true;

                cnt++;

                q.push({y, x});

            }

        }

    }

    return cnt == S;

}

int c(pi& A, pi& B) {

    return abs(A.first - B.first) + abs(A.second - B.second);

}

void f(int d, int cost) {

    if (cost >= ans) return;

    if (d == S) {

        if (isValid() == false) return;

        ans = min(cost, ans);

        return;

    }

    int i, j;

    for (i = 0; i < 5; i++) {

        for (j = 0; j < 5; j++) {

            if (board[i][j] == false) {

                board[i][j] = true;

                e.push_back({i, j});

                f(d + 1, cost + c(s[d], e[d]));

                e.pop_back();

                board[i][j] = false;

            }

        }

    }

}

int main(void) {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    int i, j;

    for (i = 0; i < 5; i++) {

        for (j = 0; j < 5; j++) {

            char x;

            cin >> x;

            if (x == '*') s.push_back({i, j});

        }

    }

    S = s.size();

    f(0, 0);

    cout << ans;

    return 0;

}