백준 17244 : 아맞다우산 c++

www.acmicpc.net/problem/17244

17244번: 아맞다우산

후기

1. 완벽하다고 생각해도 틀리면 극단적인 예시를 생각하자!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

2. 물건 하나도 없는 경우 생각안해서 런타임으로 진짜 1시간은 코드 째려본듯 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

 

풀이

1. 순열로 물건 집을 순서 정한다

2. 시작점 -> 물건들 -> 문 이렇게 거리 각각 구해서 더함

3. 거리 구하는건 언제나 하는 BFS

 -> 조금 특이하게 벽으로 둘러쌓여있어서 E랑 # 이 두가지만 아닌거 판단하면된당

 

#include<iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

int answer = 987654321;
char map[51][51];
int visited[51][51];

int d_r[4] = { 0,0,1,-1 };
int d_c[4] = { 1,-1,0,0 };
int n, m;
pair<int, int> now, door;
vector < pair<int, int> >product;
int order[10];// 여기 순서대로 product 의 순서 들어가있음

int bfs(pair<int, int> start, pair<int, int> end)
{
	memset(visited, 0, sizeof(visited));
	int result = 0;
	queue<pair<int, int> > q;
	q.push(start);
	visited[start.first][start.second] = 1;

	while (true)
	{
		int s = q.size();
		for (int k = 0; k < s; k++)
		{
			int r = q.front().first;
			int c = q.front().second;

			q.pop();
			for (int i = 0; i < 4; i++)
			{
				int new_r = r + d_r[i];
				int new_c = c + d_c[i];

				if (new_r == end.first && new_c == end.second)
					return result + 1;

				if (map[new_r][new_c] == '#')//벽
					continue;
				if (map[new_r][new_c] == 'E')
					continue;

				if (visited[new_r][new_c] == 0)
				{
					visited[new_r][new_c] = 1;
					q.push(make_pair(new_r, new_c));
				}
			}
		}
		result++;
	}

}

void make_order(int cnt)
{
	if (cnt == product.size())
	{
		int sum = 0;
		sum += bfs(now, product[order[0]]);
		for (int i = 0; i < product.size()-1; i++)
		{
			sum += bfs(product[order[i]], product[order[i + 1]]);
		}
		sum += bfs(product[order[product.size() - 1]], door);
		answer = min(answer, sum);

		return;
	}

	for (int i = 0; i < product.size(); i++)
	{
		if (order[i] == -1)
		{
			order[i] = cnt;
			make_order(cnt + 1);
			order[i] = -1;
		}
	}

}

int main()
{
	cin >> n >> m; // (m,n) 행 m  열 n
	for (int i = 0; i < m; i++ )
		for (int j = 0; j < n; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 'S')
			{
				now.first = i;
				now.second = j;
			}
			else if (map[i][j] == 'X')
			{
				product.push_back(make_pair(i, j));
			}
			else if (map[i][j] == 'E')
			{
				door.first = i;
				door.second = j;
			}
		}

	memset(order, -1, sizeof(order));

	if (product.size() == 0)
	{
		answer = bfs(now, door);
	}
	else
		make_order(0);

	cout << answer << endl;
	return 0;
}