[BOJ] 아맞다우산

5 5
#####
#S..E
#...#
#..X#
#####

7

*물건을 찾으러 가는 순서에 따라서 최단 거리가 결정이 된다. 

*물건에 번호를 매겨서 비트마스킹으로 하려고 했으나, 매번 값이 달라짐 

*시작점, 물건, 도착점을 모두 하나의 백터배열에 저장하여 모두의 최단거리를 dp에 저장한다. (dp는 다이나믹이라기보다는 그냥 저장배열로 생각한다.)

*시작점, 도착점을 제외한 물건들을 순열로 순서를 만들어 탐색하면서 최단거리를 저장한다. (처음 시작은 시작지점, 마지막은 도착지점으로 해야한다)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
 
#define INF 987654321
using namespace std;
 
int n, m;
char map[51][51];
bool visited[51][51];
typedef pair<int, int> pp;
 
vector<pp> pos;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
 
int bfs(pp p1, pp p2)
{
    queue<pp> dist;
    dist.push(p1);
    memset(visited, 0, sizeof(visited));
    visited[p1.first][p1.second] = true;
    int res = INF, tmp = 0;
 
    while (!dist.empty())
    {
        int size = dist.size();
        while (size--)
        {
            int x = dist.front().first;
            int y = dist.front().second;
 
            dist.pop();
 
            if (x == p2.first && y == p2.second)
            {
                res = min(res, tmp);
                continue;
            }
 
            for (int i = 0; i < 4; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
 
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || visited[nx][ny] || map[nx][ny] == '#')
                    continue;
                
                visited[nx][ny] = true;
                dist.push(pp(nx, ny));
            }
        }
        ++tmp;
    }
    return res; 
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    pp dest;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 'S')
            {
                pos.insert(pos.begin(), pp(i, j));
            }
            else if (map[i][j] == 'X')
            {
                pos.push_back(pp(i, j));
            }
            else if (map[i][j] == 'E')
            {
                dest = pp(i, j);
            }
        }
    }
 
    pos.push_back(dest);
    //bfs를 최단 거리를 구하는 용도로 사용한다.
    int dp[51][51] = {{0}};
    for (int i = 0; i < pos.size(); i++)
    {
        for (int j = i; j < pos.size(); j++)
        {
            if (i == j)
                continue;
            dp[i][j] = dp[j][i] = bfs(pos[i], pos[j]);
        }
    }
 
    vector<int> nums;
    for (int i = 1; i < pos.size() - 1; i++)
    {
        nums.push_back(i); //시작점과 도착점 빼고 (이건 랜덤 순서가 될 수 없다.)
    }
 
    int ans = INF;
    int sum, start, end = pos.size() - 1;
    do
    {
        //start지점에서 출발해서 end까지 가는 거리에서 물건 간의 거리를 최소로 가져가도록 한다.
        sum = 0;
        start = 0;
        for (auto i : nums)
        {
            sum += dp[start][i];
            // cout << start << " -> " << i << " " << dp[start][i] << '\n';
            start = i;
        }
        sum += dp[start][end];
        ans = min(ans, sum);
    } while (next_permutation(nums.begin(), nums.end())); //물건을 가져갈 수 있는 모든 경우를 다 해본다.
 
    cout << ans << '\n';
    return 0;
}