ub가 떴다. (주의), tie문법, 장애물 치우기(bfs + dfs)

up 발생

• 밑의 코드에서 ub가 발생했다 ub는 undefined behhavior?이라서 -> 입력 값마다 출력하는 값들이 다 다를 수도 있다

• bool 값을 반환하는 함수에서 먼저 if로 true값을 반환했는데 else를 걸지 않으면 컴퓨터는 "어 이럴때는 true지? 근데 언제 false야? 나는 알 수 없어" 이렇게 반응해서 ub가 발생한다.

  bool Cango(int x, int y) {
    if (InRange(x, y) && visited[x][y] == -1) return true;
    else return false;
  }

tie, tuple 문법

• cpp 에서 tie는 3중 pair는 너무 복잡해서 사용하기에 눈이 너무 아파서 tie를 사용했는데 꼭 tie를 잘 활용해야겠다는 생각이 들었다 왜냐? tuple에서 tuple<int ,int , int> 일때 자동으로 정렬 기능까지 포함하기 때문이다 첫번째로 비교가 안된다면 두번째를 보고 자동으로 비교 연산까지 수행한다 갓 tuple.. !!!

장애물 치우기

문제

문제는 n * n에서 k개의 입력이 있고 m개의 장애물을 치울 수 있다... 이동 할 수 있는 최대위치를 출력하면된다

설명

• 여기서 k개의 입력 (시작위치) -> multisource bfs

• 여러개의 장애물 중에서 m개를 치울 수 있다 backtracking, 여기서 시작은 당연히 (0, 0) -> 가지치기문은 총 갯수 중에서 몇개를 선택했을 때 가지 시작!!

• 여기서 치울 장애물을 선택했다가, 치운 장애물을 다시 복원하는 과정에서 tmpMap을 쓸가 생각했는데 필요없다 이 과정도 backtracking 복원 과정과 동일하게 해주면된다

for (int i = 0; i < selectStonePos.size(); i++)
    {
        int xx = 0, yy = 0;
        tie(xx, yy) = selectStonePos[i];
        grid[xx][yy] = 0;
    }
    //bfs를 돌린다 
    memset(visited, 0, sizeof(visited));
    bfs();
    // 다시 제거했던 돌들을 다시 올려준다 
    for (int i = 0; i < selectStonePos.size(); i++)
    {
        int xx = 0, yy = 0;
        tie(xx, yy) = selectStonePos[i];
        grid[xx][yy] = 1;
    }

소스

#include <bits/stdc++.h>

using namespace std;

int n, m, k, ans;
int grid[200][200];
vector<pair<int, int>> startPos;
vector<pair<int, int>> stonePos;
vector<pair<int, int>> selectStonePos;
bool visited[200][200];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };

bool InRange(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= n;
}

bool Cango(int x, int y) {
    if (InRange(x, y) && !visited[x][y] && grid[x][y] == 0) return true;
    else return false;
}
void bfs() {
    queue<pair<int, int>> q;
    for (int i = 0; i < startPos.size(); i++)
    {
        int xx = 0, yy = 0;
        tie(xx, yy) = startPos[i];
        q.push({ xx, yy });
        visited[xx][yy] = 1;
    }

    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (Cango(nx, ny)) {
                q.push({ nx, ny });
                visited[nx][ny] = 1;
            }
        }
    }


}
int Calc() {
    //먼저 grid에 selectStonePos만큼 돌을 제거해준다
    int sum = 0;
    for (int i = 0; i < selectStonePos.size(); i++)
    {
        int xx = 0, yy = 0;
        tie(xx, yy) = selectStonePos[i];
        grid[xx][yy] = 0;
    }
    //bfs를 돌린다 
    memset(visited, 0, sizeof(visited));
    bfs();
    // 다시 제거했던 돌들을 다시 올려준다 
    for (int i = 0; i < selectStonePos.size(); i++)
    {
        int xx = 0, yy = 0;
        tie(xx, yy) = selectStonePos[i];
        grid[xx][yy] = 1;
    }
    // 최대칸수 헤아리기 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (visited[i][j]) sum++;
        }
    }
    return sum;
}
void back(int idx, int cnt) {

    if (idx == (int)stonePos.size()) {
        if (cnt == m) {
            ans = max(ans, Calc());
        }
        return;
    }


    selectStonePos.push_back(stonePos[idx]);
    back(idx + 1, cnt + 1);
    selectStonePos.pop_back();

    back(idx + 1, cnt);
}
int main() {
    cin >> n >> k >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 1) {
                stonePos.push_back({ i, j });
            }
        }
    }

    for (int i = 0; i < k; i++)
    {
        int r = 0, c = 0; cin >> r >> c;
        startPos.push_back({ r, c });
    }
    back(0, 0);

    cout << ans;
    return 0;
}