백준 - 1189, 16234, 14620

백준 1189 컴백홈 (유형 - BFS 백트래킹)

 

BFS 방식 순차탐색을 하되 백트래킹으로 원복하여 가짓수 CNT를 계산하는 방식의 문제

//Input : R * C , R,C | 거리 K | 맵정보
//Output : 거리가 k인 가짓수 cnt
#include <iostream>
#include <queue>
#include <string>

using namespace std;

int cnt, n, m, k;
int visited[9][9];
char a[9][9];
string s;
const int dy[4] = { -1, 0, 1, 0 };
const int dx[4] = { 0, 1, 0, -1 };

int Go(int y, int x)
{
	//우측상단일때
	if (y == 0 && x == m - 1)
	{
		if (visited[y][x] == k)
			return 1;
		return 0;
	}
	int ret = 0;
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= n || nx < 0 || nx >= m)
			continue;
		if (visited[ny][nx])
			continue;
		if (a[ny][nx] == 'T')
			continue;

		visited[ny][nx] = visited[y][x] + 1;
		ret += Go(ny, nx);
		visited[ny][nx] = 0;
	}
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m >> k;
	for (int i = 0; i < n; i++)
	{
		cin >> s;
		for (int j = 0; j < m; j++)
			a[i][j] = s[j];
	}
	visited[n - 1][0] = 1;
	cout << Go(n - 1, 0) << "\n";
	return 0;
}

 

---

백준 16234 인구이동

 

DFS + 백트래킹으로 풀었습니다

인구차이를 계산할떄 50 , 30 일떄나 30 , 50 일때나 어차피 서로 빼서 계산하면

20 OR - 20이기 떄문에 ABS 절대값을 사용하여 계산

//Input
//n * n 의 n | 국경선을 공유하는 두 나라의 인구차이 l이상 r 이하 l, r| 
//각 나라의 인구수 
//Output : 인구이동 몇일동안?
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int visited[54][54];
int a[54][54];
int n, l, r, sum, cnt;
const int dy[4] = { -1, 0, 1, 0 };
const int dx[4] = { 0, 1, 0, -1 };
vector<pair<int, int>> v;

void DFS(int y, int x, vector<pair<int, int>>& v)
{
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= n || nx < 0 || nx >= n)
			continue;
		if (visited[ny][nx])
			continue;
		// l 과 r 사이라면
		if (abs(a[ny][nx] - a[y][x]) >= l && abs(a[ny][nx] - a[y][x]) <= r)
		{
			visited[ny][nx] = 1;
			v.push_back({ ny, nx });
			sum += a[ny][nx];
			DFS(ny, nx, v);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> l >> r;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			cin >> a[i][j];
	}
	while (true)
	{
		bool flag = 0;
		fill(&visited[0][0], &visited[0][0] + 54 * 54, 0);
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (!visited[i][j])
				{
					v.clear();
					visited[i][j] = 1;
					v.push_back({ i, j });
					sum = a[i][j];
					DFS(i, j, v);

					if (v.size() == 1)
						continue;
					for (pair<int, int> b : v)
					{
						a[b.first][b.second] = sum / v.size();
						flag = 1;
					}
				}
			}
		}
		if (!flag)
			break;
		cnt++;
	}
	cout << cnt << "\n";
	return 0;
	
}

 

---

백준 14620 꽃길

BFS 의 알고리즘에서 백트래킹을 섞은 완탐방식의 문제였습니다

//Input : n * n 의 n, 맵
//Output : 최소비용 cnt
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

bool visited[14][14];
int a[14][14];
int n, cnt;
int ret = 1e7;
const int dy[4] = { -1, 0, 1, 0 };
const int dx[4] = { 0, 1, 0, -1 };

//Check
bool Check(int y, int x)
{
	if (visited[y][x])
		return false;
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= n || nx < 0 || nx >= n)
			return false;
		if (visited[ny][nx])
			return false;
	}
	return true;
}
//SetFlower
int SetFlower(int y, int x)
{
	visited[y][x] = 1;
	int sum = a[y][x];
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		visited[ny][nx] = 1;
		sum += a[ny][nx];
	}
	return sum;
}
//EraseFlower (backtracking)
void EraseFlower(int y, int x)
{
	visited[y][x] = 0;
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		visited[ny][nx] = 0;
	}
}
//재귀로 심어진 꽃 갯수, 심어진 꽃 가격 합산식
void Flower(int cnt, int sum)
{
	if (cnt == 3)
	{
		ret = min(ret, sum);
		return;
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!Check(i, j))
				continue;
			int cost = SetFlower(i, j);
			Flower(cnt + 1, sum + cost);
			EraseFlower(i, j);
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			cin >> a[i][j];
	}
	Flower(0, 0);
	cout << ret << "\n";
	return 0;
}