백준, BOJ, 1012번 C++ [CPP]

뭐 이것도 BFS의 기본문제라고 볼 수 있겠다

다만 이건 입력을 특이하게 받는 케이스? 라고 보면 된다.

https://www.acmicpc.net/problem/1012

 

---

#맞는 풀이

하지만 정제되지 않음

손에 익지 않아서 20분정도 걸림

주석포함

 

솔직히 다른 사람은 어떻게 그렇게 정제된 풀이가 바로 생각나는거지??...

아직 갈 길이 멀다.

 

#include<iostream>
#include<algorithm>
#include<queue>

#define X first
#define Y second


using namespace std;

int tc;

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

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

    cin >> tc;

    //tc만큼 반복
    while (tc--) {
        int map[50][50] = {0, };
        int vis[50][50] = {0, };
        queue<pair<int, int>> Q;

        int col, row, tg; // 행, 렬, 목표
        cin >> col >> row >> tg;

        int worm = 0; // 지렁이

        //tg 만큼 배추 맵에 입력
        while (tg--) {
            int x, y;
            cin >> x >> y;
            map[x][y] = 1;
        }

        //탐색 결과 출력

        //vis의 값이 1이 아니면서 배추가 있는 곳 Q에 푸시
        //시작노드 개수 = 에벌레 마리수
        for (int i = 0; i < col; i++) {
            for (int j = 0; j < row; j++) {

                if (vis[i][j] == 1 || map[i][j] == 0) {
                    continue;
                }

                Q.push({ i,j });
                vis[i][j] = 1;
                worm++;
                while (!Q.empty()) {
                    auto cur = Q.front();
                    Q.pop();

                    for (int dir = 0; dir < 4; dir++) {
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
                        if (nx < 0 || nx >= col || ny < 0 || ny >= row) {
                            continue;
                        }
                        if (vis[nx][ny] == 1 || map[nx][ny] == 0) {
                            continue;
                        }
                        vis[nx][ny] = 1;
                        Q.push({ nx,ny });
                    }
                }
            }
        }
        cout << worm << "\n";
    }
}

 

여기서 중요한 건

BFS로 탐색하는 것도 중요하지만

테스트케이스마다 초기화 해주어야 할 것을 꼭 초기화시켜주는 것이 필요하다.

에벌레 마리 수, 2차원 배열들, 사용할 큐 등이

그 중요한 것들이다.

**테스트케이스가 많은 경우

꼭 배열하고 큐는 잊지말고 초기화시켜주자

거의 이거 때문에 틀린다.