우리가 구해야 할 답은 총 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;
}
정확히 이문제는 핵심이 나를 기준으로 나보다 크기가 작고 같은 거리에 있는 물고기 들은 위에에서 왼쪽부터 오른쪽 까지 검사하고 내려와서 왼쪽부터 오른쪽 까지 검사하면서 이 순으로 탐색을 하는 거였다. 단 위에를 듣고 BFS 이동방향을 1,0 ->0,-1 ->0,1 ->-1,0 이렇게 만 하면 안풀린다
핵심은 이부분이다 내가 물고기를 먹을 수있는 지역으로 갔을 때 현재 큐에 들어와 있는 것중 나보다 거리가 작거나 같고 행의 값이 위에 있거나 혹은 행이 같다면 열값이 더 먼저인 애를 찾아서 거기를 가야한다 이에 의해 필자는 행을 검사에서 위에있으면 해당 행으로 탐색지점을 바꿔줬고 같다면 열값이 더 작은 쪽으로 옮겨줬다
#include <iostream>
#include <queue>
using namespace std;
int n;
int arr[20][20] = { 0, };
bool isVisited[20][20];
int fishSize = 2;
int eatFish = 0;
int cnt = 0;
queue<pair<int,pair<int, int>>> bfsQ;
bool CanEat(int x, int y) {
if (arr[x][y]>0&&arr[x][y] < fishSize) {
return true;
}
return false;
}
bool canGo(int x, int y) {
if (x >= 0 && x < n && y >= 0 && y < n && !isVisited[x][y] && (CanEat(x, y) || arr[x][y] == 0 || arr[x][y]==fishSize))
return true;
else
return false;
}
void Bfs(int x, int y) {
bfsQ.push({ cnt,{x,y} });
arr[x][y] = 0;
int startX, startY, cost;
int otherX, otherY, otherCost;
while (!bfsQ.empty()) {
startX = bfsQ.front().second.first;
startY = bfsQ.front().second.second;
cost = bfsQ.front().first;
bfsQ.pop();
if (CanEat(startX, startY)) {
cnt += cost;
while (!bfsQ.empty()) {
otherX = bfsQ.front().second.first;
otherY = bfsQ.front().second.second;
otherCost = bfsQ.front().first;
if (CanEat(otherX, otherY) && otherCost<=cost) {
if (otherX < startX) {
startX = otherX;
startY = otherY;
otherCost = cost;
}
else if (otherX == startX && startY>otherY ) {
startX = otherX;
startY = otherY;
otherCost = cost;
}
}
bfsQ.pop();
}
bfsQ.push({ 0, {startX, startY}});
eatFish += 1;
if (eatFish == fishSize) {
fishSize += 1;
eatFish = 0;
}
arr[startX][startY] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
isVisited[i][j] = false;
}
}
isVisited[startX][startY] = true;
cost = 0;
}
if (canGo(startX-1,startY)) {
bfsQ.push({ cost + 1,{startX -1,startY}});
isVisited[startX - 1][startY] = 1;
}
if (canGo(startX, startY-1)) {
bfsQ.push({ cost + 1,{startX ,startY - 1} });
isVisited[startX][startY-1] = 1;
}
if (canGo(startX , startY+1)) {
bfsQ.push({ cost + 1,{startX ,startY + 1} });
isVisited[startX][startY + 1] = 1;
}
if (canGo(startX+1 , startY)) {
bfsQ.push({ cost + 1,{startX + 1,startY} });
isVisited[startX + 1][startY] = 1;
}
}
}
int main() {
cin >> n;
int startIdxCol, startIdxRow;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
if (arr[i][j] == 9) {
startIdxCol = i;
startIdxRow = j;
}
}
}
Bfs(startIdxCol, startIdxRow);
cout << cnt;
}
이 문제의 경우 흐름대로 생각하면 그게 정답이다 단 주의 할점은 단지 하나의 priority queue로 만한다면 음수부분의 처리가 이상하게 될것이다 이에 나는 음수와 0을 저장하는 priority queue와 양수만을 저장해주는 priority queue로 작성하였으며 음수 와 0을 묶은 이유는 음수와 음수의 곱은 양수이고 만약 음수와 0만 큐에 남았을 때는 2개를 곱하여 0을 반환함으로 작은 값을 반환할거라고 생각했다
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
priority_queue<int> plusNum;
priority_queue<int,vector<int>, greater<int>> negativeNum;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int temp1;
cin >> temp1;
if (temp1 > 0) {
plusNum.push(temp1);
}
else {
negativeNum.push(temp1);
}
}
int sum = 0;
while (!plusNum.empty())
{
int num1, num2;
num1 = plusNum.top();
plusNum.pop();
if (plusNum.empty()) {
sum += num1;
break;
}
num2 = plusNum.top();
plusNum.pop();
if (num1 != 1 && num2 != 1) {
sum += num1 * num2;
}
else {
sum += num1 + num2;
}
}
while (!negativeNum.empty())
{
int num1, num2;
num1 = negativeNum.top();
negativeNum.pop();
if (negativeNum.empty()) {
sum += num1;
break;
}
num2 = negativeNum.top();
negativeNum.pop();
sum += num1 * num2;
}
cout << sum;
}
