글 읽기 - [C++] DFS가 아닌 방법으로 구현했는데 반례 부탁드립니다.

minsh 3년 전 0

다 풀고 나니까 DFS로 구현해야 되는 문제인걸 알았는데...

DFS가 아닌 제 방법으로 구현했을 때 왠만한 반례는 다 되는데 안되네요....

고수님들 부탁드립니다.

#include <iostream>
#include <vector>

using namespace std;

int main() {

    int total_case;
    vector<vector<int>> arr;
    vector<int> tempArr;

    cin >> total_case;

    for (int i = 0; i < total_case; i++) {
        int xPos, yPos, veg, worm = 0;

        arr.clear();
        tempArr.clear();

        cin >> xPos >> yPos >> veg;

        for (int j = 0; j < yPos; j++) {
            for (int k = 0; k < xPos; k++) {
                tempArr.push_back(0);
            }
            arr.push_back(tempArr);
        }

        for (int j = 0;j < veg;j++) {
            int ix, iy;
            cin >> ix >> iy;
            arr[iy][ix] = 1;
        }

        for (int j = 0; j < yPos; j++) {
            for (int k = 0; k < xPos; k++) {

                int c = 0, n = 0, s = 0, e = 0, w = 0;

                if (j - 1 >= 0)
                    if (arr[j - 1][k]) n = arr[j - 1][k];
                if (k - 1 >= 0)
                    if (arr[j][k - 1]) w = arr[j][k - 1];
                if (j + 1 < yPos)
                    if (arr[j + 1][k]) s = arr[j + 1][k];
                if (k + 1 < xPos)
                    if (arr[j][k + 1]) e = arr[j][k + 1];
                if (arr[j][k]) c = arr[j][k];

                if (c) {
                    if (c == 2 || n == 2 || s == 2 || e == 2 || w == 2);
                    else worm++;

                    if (j - 1 >= 0)
                        if (arr[j - 1][k]) arr[j - 1][k] = 2;
                    if (k - 1 >= 0)
                        if (arr[j][k - 1]) arr[j][k - 1] = 2;
                    if (j + 1 < yPos)
                        if (arr[j + 1][k]) arr[j + 1][k] = 2;
                    if (k + 1 < xPos)
                        if (arr[j][k + 1]) arr[j][k + 1] = 2;
                    if (arr[j][k]) arr[j][k] = 2;

                }


            }
        }

        cout << worm << "\n";
    }




}

seico75 3년 전 0

22 23 줄 사이에 temoArr clear해야하지.않읅가요?

0100010

0111110

0000000

이런데에서는 문제 없을까요?

minsh 3년 전 0

아 22 23줄 사이에는 전체 맵을 0 으로 초기화하는 작업이라 상관 없을 것 같습니다 ... ㅠ

seico75 3년 전 0

집에 와서 다시 글을 씁니다.

앞에 썼던 글에서 들었던 예시에 대한 데이터를 드립니다.

모양은 위에 그린 그림입니다.

그리고, 22-23 줄은 답에 영향을 주지는 않겠지만 의도하신 바는 아닐 겁니다.

차라리 아래 같이 하는게 더 좋을 수 있겠네요.

for (int k = 0; k < xPos; k++) {
  tempArr.push_back(0);
}
for (int j = 0; j < yPos; j++) {
  arr.push_back(tempArr);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C++] DFS가 아닌 방법으로 구현했는데 반례 부탁드립니다.

minsh 3년 전 0

seico75 3년 전 0

minsh 3년 전 0

seico75 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말