2024 - 08- 19 C++ 코딩테스트 10주완성 D+32
완전탐색과 원상복귀
모든 경우의 수를 찾을 때에는 완전탐색을 이용합니다.
하지만 어떤 맵에서 어떤 것을 색칠하거나 뭘 세운다라고 했을 때 경우의 수들끼리 서로의 상태값이 영향을 미치지 않게 하려는 방법이 바로 원복입니다.
연습코드
#include <bits/stdc++.h>
using namespace std;
int visited[4];
vector<int> adj[4];
vector<int> v;
void print() {
for (int i : v) cout << char(i + 'A') << " ";
cout << '\n';
}
void go(int idx) {
if (v.size() == 3) {
print(); return;
}
for (int there : adj[idx]) {
if (visited[there]) continue;
visited[there] = 1;
v.push_back(there);
go(there);
visited[there] = 0;
v.pop_back();
}
}
int main() {
adj[0].push_back(1);
adj[1].push_back(2);
adj[1].push_back(3);
adj[1].push_back(0);
adj[2].push_back(1);
adj[3].push_back(1);
visited[0] = 1;
v.push_back(0);
go(0);
return 0;
}
Visited 배열을 이용하여서 특정한 노드에서 자식노드가 여러개 있을 경우,
이미 탐색한 자식노드를 제외하고 나머지를 탐색하도록 하는 알고리즘으로 구성하였습니다.
실습문제
홍철이는 3 * 3 맵에서 {0, 0} 지점에서 길을 잃어버렸다.
긍정왕 홍철이는 길을 잃어버린 김에 구걸을 하면서 돈을 모으면서 여행을 가려고 한다.
목적지는 {2, 2}이며 방문한 정점은 다시 방문할 수 없고 해당 맵에 구걸로 얻을 수 있는 돈들이 있다.
홍철이는 4방향(상하좌우)로 움직일 수 있다.
{2, 2}까지 간다고 했을 때 이 돈들을 모으는 모든 경우의 수를 출력하여라.
맵 :
{10, 20, 21},
{70, 90, 12},
{80, 110, 120}
실습코드
#include <bits/stdc++.h>
using namespace std;
int a[3][3] = { {10,20,21},{70,90,12},{80,110,120} };
int visited[3][3];
int dy[4] = { -1, 0 , 1,0 };
int dx[4] = { 0 , 1 , 0 , -1 };
vector<int> v;
void print()
{
for (int i : v) cout << i << " ";
cout << endl;
}
void go(int y, int x)
{
if (y == 2 && x == 2)
{
print();
return;
}
for (int i = 0; i < 4; i++)
{
int uy = y + dy[i];
int ux = x + dx[i];
if (uy >= 3 || uy < 0 || ux >= 3 || ux < 0) continue;
if (visited[uy][ux]) continue;
visited[uy][ux] = 1;
v.push_back(a[uy][ux]);
go(uy, ux);
visited[uy][ux] = 0;
v.pop_back();
}
}
int main()
{
visited[0][0] = 1;
v.push_back(a[0][0]);
go(0, 0);
return 0;
}
완전탐색을 해주는 함수인 go를 맨처음 지점인 (0,0) 부터 호출시켜주고 만약 끝지점위치인 (2,2)까지 올 경우
이때까지 탐색한 v 의 값을 순서대로 출력해주면 된다!
이때 중요한 것은 위치를 탐색하고 검사하는 ux,uy 변수가 지역변수여야된다.
왜냐하면 전역변수일 경우에는 특정한 위치에서 visited[uy][ux] = 0 을 해주어야하는데,
완전 탐색이 끝난 (2,2) 지점에서 uy,ux 값을 지정해주는 동작이 끝나기때문에
재귀함수 전부 visited[2][2] = 0 으로 동작을 해버린다!
백준 15686 문제 - 치킨배달
크기가 N×N인 도시가 있다.
도시는 1×1크기의 칸으로 나누어져 있다.
도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다.
도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다.
(r과 c는 1부터 시작한다.)
이 도시에 사는 사람들은 치킨을 매우 좋아한다.
따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다.
즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다.
도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.
임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.
예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2
0은 빈 칸, 1은 집, 2는 치킨집이다.
(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.
(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.
이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다.
프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다.
오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실을 알아내었다.
도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다.
어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.
둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.
도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다.
집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.
출력
첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.
실습코드
#include <bits/stdc++.h>
using namespace std;
int n, m, a[54][54], result = 987654321;
vector<vector<int>>chickenList;
vector<pair<int, int>> _home, chicken;
void combi(int start, vector<int> v) {
if (v.size() == m) {
chickenList.push_back(v);
return;
}
for (int i = start + 1; i < chicken.size(); i++) {
v.push_back(i);
combi(i, v);
v.pop_back();
}
return;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
if (a[i][j] == 1)_home.push_back({ i, j });
if (a[i][j] == 2)chicken.push_back({ i, j });
}
}
vector<int> v;
combi(-1, v);
for (vector<int> cList : chickenList) {
int ret = 0;
for (pair<int, int> home : _home) {
int _min = 987654321;
for (int ch : cList) {
int _dist = abs(home.first - chicken[ch].first) + abs(home.second - chicken[ch].second);
_min = min(_min, _dist);
}
ret += _min;
}
result = min(result, ret);
}
cout << result << "\n";
return 0;
}
배열의 행과 열을 입력받고,
원소의 값을 입력받을 때,그 값이 1이면 Home, 2이면 chicken 안에 해당 좌표를 push_back 시켜준다.
임의의 벡터 v를 선언하고, combi 함수안를 호출하고 매개인수로 넣는다.
치킨집의 사이즈만큼 v안에 push_back을 해주는데,
만약 v의 사이즈가 m이 될 경우 이중벡터인 chickenList 안에 v를 넣어준다.
그리고 ChickenList의 크기만큼 각각의 집마다 최소 치킨거리를 구한다음,
결과에 더해준다.
그리고 결과의 최솟값을 구한다음 출력시켜준다.
처음하는 조합과 이중 Vector를 이용한 문제풀이라 너무 헷갈렸는데,
조금은 이해된것 같다..! 사실 아직도 헷갈리지만 코드 하나씩 분석하며 풀어가니
어떤 메커니즘인지는 파악할 수 있는 거 같다.
조금 더 분석해보아야겠다.