✅ 한 것들

• 백준

⚔️ 백준

9376 탈옥

#include"9376.h"
using namespace std;
typedef vector<vector<char>> vvc;
typedef vector<vector<bool>> vvb;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

int h, w;
vector<pii> prisoner;
vvc prison;
vvb visited;
vvi AMinDoor;

vector<int> dx = { 1,-1,0,0 };
vector<int> dy = { 0,0,1,-1 };

int dfs(pii ij, int openedBDoor, int minADoorArea)
{
	if (ij.first < 0 || h < ij.first || ij.second < 0 || w < ij.second)
		return openedBDoor + minADoorArea;
	visited[ij.first][ij.second] = true;
	minADoorArea = min(AMinDoor[ij.first][ij.second], minADoorArea);
	if(prison[ij.first][ij.second] == '#') openedBDoor++;

	int res;
	for (int i = 0; i < 4; i++)
	{
		int newi = ij.first + dx[i];
		int newj = ij.second + dy[i];

		if (newi < 0 || h < newi || newj < 0 || w < newj) continue;
		if (prison[newi][newj] == '*') continue;
		if (visited[newi][newj]) continue;

		res = dfs({ newi,newj }, openedBDoor, minADoorArea);
	}

	if (prison[ij.first][ij.second] == '#') openedBDoor--;
	visited[ij.first][ij.second] = false;
	return res;
}

int GetMinDoor()
{
	stack<pii> dfsS;
	visited = vvb(h, vector<bool>(w, false));

	pii B = prisoner[1];
	visited[B.first][B.second] = true;
	return dfs(B, 0, 10001);
}

void BFS_SetAMinDoor()
{
	visited = vvb(h, vector<bool>(w,false));

	// 문을 만나면 큐에 넣지 않고 문 큐에 넣음 
	// bfs 한 사이클 끝나면 문 큐를 넣어서 다시 진행
	// bfs 큐가 있을 때까지 while문

	queue<pii> bfsQ;
	pii A = prisoner[0];
	bfsQ.push(A);
	visited[A.first][A.second] = true;
	queue<pii> doorQ;
	int minDoor = 0;

	while (!bfsQ.empty())
	{
		while (!bfsQ.empty())
		{
			pii ij = bfsQ.front(); bfsQ.pop();
			AMinDoor[ij.first][ij.second] = minDoor;
			
			for (int i = 0; i < 4; i++)
			{
				int newi = ij.first + dx[i];
				int newj = ij.second + dy[i];
				if (newi < 0 || h <= newi || newj < 0 || w <= newj) continue;
				if (visited[newi][newj]) continue;
				if (prison[newi][newj] == '*') continue;
				if (prison[newi][newj] == '#')
				{
					doorQ.push({ newi,newj });
					continue;
				}
				visited[newi][newj] = true;
				bfsQ.push({ newi,newj });
			}
		}

		bfsQ = doorQ;
		doorQ = queue<pii>();
		minDoor++;
	}	
}

void Init()
{
	cin >> h >> w;
	prison = vvc(h,vector<char>(w));
	AMinDoor = vvi(h, vector<int>(w,100001));
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
		{
			cin >> prison[i][j];
			if (prison[i][j] == '$')
				prisoner.push_back({ i,j });
		}
}

int CountMinDoor()
{
	Init();

	// bfs로 죄수 A에서부터 각 영역 가는데 필요한 최소 문 개수 구해놓기
	// dfs로 죄수 B에서부터 탈출하면서
	// 1. 연 문 개수를 기록
	// 2. 지금까지 갔던 죄수 A 최소 문 개수 중 최소값 기록
	// 3. 끝나면 연 문 개수 + 죄수 A 문 개수가 최소값인지 확인
	BFS_SetAMinDoor();
	return GetMinDoor();
}

void B9376::Solution()
{
	int T;
	cin >> T;
	while (T--)
	{
		cout << CountMinDoor();
	}
}

내일 마저