글 읽기 - BFS가 제대로 탐색하지 않는 영역에 대한 질문

melon940925 4년 전 0

치킨배달을 풀면서 테스트케이스와 몇몇 반례들은 다 맞지만

결국 제가 만든 BFS가 어떤 영역을 탐색하지 않는다는 것을 알게되었습니다.

왜 오른쪽 밑 영역을 탐색하지 않는 것인지 알려주실 고수 분 계신가요?..

아래는 해당 예제들입니다.

제가만든 BFS는 1이있는 장소를 모두 탐색해야 종료가 되는데,

1이 있는 장소를 찾아가지 않기 때문에 종료가 되지 않고 있습니다.

무엇이 문제일까요?

6 8
0 0 0 2 1 0
1 2 2 0 1 0
2 0 1 0 0 0
0 2 0 2 2 0
2 0 1 0 1 2
2 2 2 0 2 0
Correct: 7

6 7
0 1 0 0 2 1
2 2 2 0 2 0
0 1 2 1 0 0
0 0 2 0 0 2
2 2 0 2 2 1
2 1 0 1 0 1
Correct: 9

6 10
2 2 1 2 1 0
2 1 0 0 1 1
2 0 2 1 0 1
2 0 2 2 1 0
2 0 0 2 1 0
1 0 1 2 2 1
Correct: 17

#include<iostream>
using namespace std;

int N, M;
int front, rear, Qcnt;
int D; int Min = 987654321;
int Distance;
int House;
int check[13];
int Chicken;
int map[51][51];
int tempmap[51][51];

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

class Loc {
public:
    int y;
    int x;
};


Loc queue[2500];
Loc chicken[13];

void push(int y, int x) {
    queue[rear].y = y;
    queue[rear].x = x;
    rear++; Qcnt++;
    rear %= (N * N);
}

void pushCHICKEN(int y, int x) {
    chicken[rear].y = y;
    chicken[rear].x = x;
    rear++; Qcnt++;
    rear %= (2500);
}

void pop() {
    front++;
    Qcnt--;
    front %= (2500);
}

void BFS();
void DFS(int cnt, int arr_idx);

int main() {
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {

            cin >> map[i][j];
            if (map[i][j] == 2) {
                Chicken++; pushCHICKEN(i, j);
            }
            if (map[i][j] == 1)House++;
        }
    }

    for (int i = 0; i < Chicken; i++) check[i] = 0;
    //for (int i = 0; i < M; i++) {
    //   cout << chicken[i].y << chicken[i].x << endl;
    //}
    Qcnt = rear = front = 0;

    DFS(0, 0);

    cout << Min << endl;

    return 0;
}

void BFS() {
    int q, ny, nx, X, Y;
    D = 0; int house = House;

    Distance = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            tempmap[i][j] = map[i][j];
        }
    }
    while (house > 0) {
        D++;
        q = Qcnt;

        //cout << "q: " << q << endl;
        for (int j = 0; j < q; j++) {
            X = queue[front].x; Y = queue[front].y;
            pop();

            for (int i = 0; i < 4; i++) {
                ny = Y + dy[i]; nx = X + dx[i];
                if (ny<N&&ny>=0&&nx<N&&nx>=0) {
                        if (tempmap[ny][nx] == 1) {
                            house--; Distance += D;
                            tempmap[ny][nx] = 9;
                            push(ny, nx);
                            if (house == 0)
                            {
                               Qcnt = rear = front = 0;
                               return;
                            }
                        }
                        else if(tempmap[ny][nx]!=9)
                        {
                            tempmap[ny][nx] = 9;
                            push(ny, nx);
                        }  
                }
            }
        }

        //cout << endl;
        //for (int x = 0; x < 10; x++) {
        //   for (int y = 0; y < 10; y++) {
        //      cout << tempmap[x][y] << ' ';
        //   }
        //   cout << "   D:" << D << ", Distance: " << Distance<<"house: "<<house << endl;
        //}


        //if (house == 0)
        //{
        //       //cout << endl;
        //       //for (int x = 0; x < N; x++) {
        //       //   for (int y = 0; y < N; y++) {
        //       //      cout << tempmap[x][y] << ' ';
        //       //   }
        //       //   cout << "   D:" << D << ", Distance: " << Distance << "house: " << house << endl;
        //       //}
        //    
        //    Qcnt = rear = front = 0;
        //    return;
        //}
    }
}



void DFS(int cnt, int arr_idx) {
    //if (Distance > Min)return;
    if (cnt > M)return;

    if (cnt >= 1) {
        //cout << endl;
        //for (int i = 0; i < Chicken; i++) {
        //   cout << check[i] << ' ';
        //}
        for (int i = 0; i < Chicken; i++)
        {
            if (check[i])push(chicken[i].y, chicken[i].x);
        }
        BFS();
        //cout << "Distance:" << Distance << endl;
        //if (!Distance) {
        //   for (int j = 0; j < M; j++) {
        //      cout << check[j] << ' ';
        //   }
        //   cout << endl;
        //}
        if (Distance < Min && Distance != 0)Min = Distance;

    }


    for (int i = arr_idx; i < Chicken; i++) {
        check[i] = 1;
        DFS(cnt + 1, i + 1);
        check[i] = 0;
    }

}

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

문제

문제

출처

ICPC

BFS가 제대로 탐색하지 않는 영역에 대한 질문

melon940925 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말