우리가 구해야 할 답은 총 3개다 1 번과 2번은 그냥 우리가 아는 bfs 로 영역의 최대 크기와 영역의 갯수를 구해주면된다 3번은 내가 있는 방을 기준으로 4방의 방에서 벽을 뚫는다고 가정하고 풀었다 그후 모든 방에서 상하좌우방을 뚫었을 때 진행할수 있으면 진행 하도록 코드를 작성 하였다
#include <iostream>
#include<bitset>
#include <queue>
#include <cstring>
using namespace std;
int arr[50][50];
bool isVisited[50][50];
int n, m;
int maxCnt = 1;
int xi[4] = { 0,1,0,-1 };
int yi[4] = { 1,0,-1,0 };
queue<pair<int, int>> bfsq;
bool canGo(int x, int y , int z) {
if (x >= 0 && x < m && y >= 0 && y < n && !isVisited[x][y]) {
if (arr[x][y] & (1 << z)) {
return false;
}
else
return true;
}
return false;
}
bool canGo(int x, int y) {
if (x >= 0 && x < m && y >= 0 && y < n ) {
return true;
}
return false;
}
void bfs(int startX, int startY) {
bfsq.push({ startX,startY });
isVisited[startX][startY] = true;
int cnt = 1;
while (!bfsq.empty()) {
int col = bfsq.front().first;
int row = bfsq.front().second;
bfsq.pop();
for (int i = 0; i < 4; i++) {
if (canGo(col + xi[i], row + yi[i],i)) {
bfsq.push({ col + xi[i] , row + yi[i] });
isVisited[col + xi[i]][row + yi[i]] = 1;
cnt += 1;
if (maxCnt < cnt)
maxCnt = cnt;
}
}
}
}
int main() {
int roomCnt=0;
cin >> n >> m;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (isVisited[i][j])
continue;
roomCnt += 1;
bfs(i, j);
}
}
cout << roomCnt << endl;
cout << maxCnt << endl;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++){
for (int k = 0; k < 4; k++) {
if (canGo(i + xi[k], j + yi[k]) && (arr[i + xi[k]][j + yi[k]] &(1<<k))) {
memset(isVisited, 0, sizeof(isVisited));
arr[i + xi[k]][j + yi[k]] ^= (1 << k);
bfs(i, j);
arr[i + xi[k]][j + yi[k]] |= (1 << k);
}
}
}
}
cout << maxCnt;
}
이 문제는 내가 완전 감을 잘못 잡고 풀고 있었다. 이 문제를 증가수열 비슷하게 풀려고 했었다 하지만 이렇게 풀면 로직이 꼬였는데 테스트케이스 몇개는 잘나왔으나 몇개는 매우 잘 나오지 않았다.
이 문제의 로직은 현재 나를 기준으로 내왼쪽에서의 최대높이와 내오른 쪽의 최대높이를 비교해서 낮은 높이를 선택 해주는 문제 였다 단 오른쪽 과 왼쪽의 최대높이가 나보다는 클때만 빗물이 받아지니 해당 상황일때만 계산하도록 코드를 작성한다 그림으로 나타내면 대충 아래와 같다
해당 로직에 대한 코드는 아래 와 같다
#include <iostream>
#include<algorithm>
using namespace std;
int h, w;
int arr[500];
int main() {
cin >> h >> w;
int result = 0;
for (int i = 0; i < w; i++) {
cin >> arr[i];
}
for (int i = 1; i < w - 1; i++) {
int lmax = 0;
int rmax = 0;
for (int j = 0; j < i; j++) {
if (lmax < arr[j] && arr[j]>arr[i])
lmax = arr[j];
}
for (int j = i + 1; j < w; j++) {
if (rmax < arr[j] && arr[j]>arr[i])
rmax = arr[j];
}
if (lmax != 0 && rmax != 0)
result += min(lmax, rmax) - arr[i];
}
cout << result;
}
이 문제는 다익스트라 알고리즘을 사용해서 풀 수 있다 현재 이블로그에 있는 다익스트라 알고리즘에 관한 문제는 비슷한 양상을 보인다
void djikstraSolution(int start) {
int startNode = start;
int toCost = 0;
djikstra_pq.push({ startNode,toCost });
while (!djikstra_pq.empty()) {
int toVertex = djikstra_pq.top().first;
int toCost = djikstra_pq.top().second;
djikstra_pq.pop();
int distanceToNextVertex = distanceV[toVertex];
if (distanceToNextVertex < toCost) {
continue;
}
for (int i = 0; i < edgeList[toVertex].size(); i++) {
// 다음 인덱스로 가는 cost
int cost = edgeList[toVertex][i].second + toCost;
// 나를 통해 갈 다음 IDX
int nextIdx = edgeList[toVertex][i].first;
if (cost < distanceV[nextIdx]) {
distanceV[nextIdx] = cost;
djikstra_pq.push({ nextIdx,cost });
}
}
}
}
이 부분이 핵심 부분인데
1. 일단 start 즉 시작점으로 부터의 거리를 구할 것이기에 Start -> Start의 toCost를 0 start->start의 다음인덱스 start를 우선순위 큐에 넣는다 (우선순위 큐는 값이 작은게 root 에 있다)
2.그리고 우선순위 큐가 빌때 까지 현재 우선순위 큐에 들어가 있는 버텍스와 경로들을 뽑아서 해당 경로들에 영향을 받는 다른 vertex들의 cost값을 업데이트 해줘야 한다
3.일단 node1 -> node2 로 갈때의 현재 우선순위 큐에들어가 있는 가장 작은 애를 가져온다 그후 내가 node1을 통해서 가는 node2 까지의 거리와 이전부터 업데이트 해놓은 1부터 node2까지의 거리를 비교해서 작은 값일 때 node2를 통해서 가는 거리들의 값을 업데이트 해준다 그후 다음 업데이트를 할수도 있으니 해당 값들을 우선순위 큐에 넣어주고 반복한다
전체 코드는 아래와 같다
#include <iostream>
#include<queue>
using namespace std;
int n, m;
#define INF 1e9+7
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> djikstra_pq;
vector<pair<int, int>> edgeList[5001];
vector<int> distanceV(5001);
void djikstraSolution(int start) {
int startNode = start;
int toCost = 0;
djikstra_pq.push({ startNode,toCost });
while (!djikstra_pq.empty()) {
int toVertex = djikstra_pq.top().first;
int toCost = djikstra_pq.top().second;
djikstra_pq.pop();
int distanceToNextVertex = distanceV[toVertex];
if (distanceToNextVertex < toCost) {
continue;
}
for (int i = 0; i < edgeList[toVertex].size(); i++) {
// 다음 인덱스로 가는 cost
int cost = edgeList[toVertex][i].second + toCost;
// 나를 통해 갈 다음 IDX
int nextIdx = edgeList[toVertex][i].first;
if (cost < distanceV[nextIdx]) {
distanceV[nextIdx] = cost;
djikstra_pq.push({ nextIdx,cost });
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int temp1, temp2, temp3;
cin >> temp1 >> temp2 >> temp3;
edgeList[temp1].push_back({ temp2,temp3 });
edgeList[temp2].push_back({ temp1,temp3 });
}
int start, end;
cin >> start >> end;
distanceV.assign(n + 1, INF);
djikstraSolution(start);
cout << distanceV[end];
}
이번에 모회사 코테를 보는 데 내가 못풀었던 문제에서 중복순열을 2번사용하여 경우의 수를 구하는 브루트포스 방식의 문제가 출제 되었던 거 같다. 내가 생각한게 정답이 아닐 수 도 있지만 적어도 내가 생각한데로 풀기 위해서는 중복순열과 순열을 구현했어야 했다. 하지만 오랫동안 기본적인 알고리즘 조차 손을 놓았어서. 역시 급하게 준비한 코테답게 불합격 메일을 기다리고 있다. 확실히 불합격이 되더라도 코테를 직접 보면서 어떤 식으로 공부해야할지 감이 잡히기 시작했다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//중복 순열
int caseNum;
int arr[100000];
bool vectorIndexUsed[100000];
void DuplicatePermutation(int level, vector<int> caseVector) {
if (level == caseNum) {
for (int i = 0; i < caseNum; i++) {
cout << arr[i];
}
cout << endl;
return;
}
for (int i = 0; i < caseVector.size(); i++) {
arr[level] = caseVector[i];
DuplicatePermutation(level + 1, caseVector);
}
}
void Permutation(int level, vector<int> caseVector) {
if (level == caseNum) {
for (int i = 0; i < caseNum; i++) {
cout << arr[i];
}
cout << endl;
return;
}
for (int i = 0; i < caseVector.size(); i++) {
if (!vectorIndexUsed[i]) {
vectorIndexUsed[i] = true;
arr[level] = caseVector[i];
Permutation(level + 1, caseVector);
vectorIndexUsed[i] = false;
}
}
}
void Combination(int level, vector<int> caseVector, int beforeIndex) {
if (level == caseNum) {
for (int i = 0; i < caseNum; i++) {
cout << arr[i];
}
cout << endl;
return;
}
for (int i = beforeIndex; i < caseVector.size(); i++) {
arr[level] = caseVector[i];
Combination(level + 1, caseVector, beforeIndex + 1);
}
}
int main() {
cin >> caseNum;
vector<int> dupPermuTest = { 1,4,5,2 };
DuplicatePermutation(0, dupPermuTest);
cout << "====================================="<<endl;
Permutation(0, dupPermuTest);
cout << "====================================="<<endl;
sort(dupPermuTest.begin(), dupPermuTest.end());
Combination(0, dupPermuTest, 0);
}
일단 기억나는 것은 주어진 벡터에서 몇명을 뽑아야하는 것이었다 이에 나는 중복순열,순열,조합순으로 현재 구현했다.
void DuplicatePermutation(int level, vector<int> caseVector) {
if (level == caseNum) {
for (int i = 0; i < caseNum; i++) {
cout << arr[i];
}
cout << endl;
return;
}
for (int i = 0; i < caseVector.size(); i++) {
arr[level] = caseVector[i];
DuplicatePermutation(level + 1, caseVector);
}
}
중복 순열의 경우 똑같은 걸 여러번 사용해도 되니 굳이 사용했는지 안했는 지 체크할 필요가 없다
void Permutation(int level, vector<int> caseVector) {
if (level == caseNum) {
for (int i = 0; i < caseNum; i++) {
cout << arr[i];
}
cout << endl;
return;
}
for (int i = 0; i < caseVector.size(); i++) {
if (!vectorIndexUsed[i]) {
vectorIndexUsed[i] = true;
arr[level] = caseVector[i];
Permutation(level + 1, caseVector);
vectorIndexUsed[i] = false;
}
}
}
순열의 경우 vector에서 순서가 다르면 다른것으로 인정하고 중복은 허하지 않는다
void Permutation(int level, vector<int> caseVector) {
if (level == caseNum) {
for (int i = 0; i < caseNum; i++) {
cout << arr[i];
}
cout << endl;
return;
}
for (int i = 0; i < caseVector.size(); i++) {
if (!vectorIndexUsed[i]) {
vectorIndexUsed[i] = true;
arr[level] = caseVector[i];
Permutation(level + 1, caseVector);
vectorIndexUsed[i] = false;
}
}
}
조합은 중복을 허하지도 않고 순서가 달라도 같은 수를 뽑았으면 허용치 않는다.
void duplicateCombination(int level, vector<int> caseVector, int beforeIndex) {
if (level == caseNum) {
for (int i = 0; i < caseNum; i++) {
cout << arr[i];
}
cout << endl;
return;
}
for (int i = beforeIndex; i < caseVector.size(); i++) {
arr[level] = caseVector[i];
duplicateCombination(level + 1, caseVector, i);
}
}
중복 조합은 같은 수를 뽑을 수 있고 순서가 존재한다 이에 같은수는 뽑을 수 있지만 순서가 다르고 동일한 요소로 이루어져있는 것은 이전에 뽑은것과 같음으로 허용치 않는다
