글 읽기 - 안녕하세요 BFS로 코드를 구성했는데 계속 틀렸다고 나옵니다.

ldkl123 4년 전 0

안녕하세요 BFS로 코드를 구성해봤습니다.

아이디어는 들어온 왼쪽 아래 값은 +1 씩 줌으로써 좌표가 아닌 사각형 칸을 중심으로 탐색하는 것입니다.

우선 print_out 함수들은 맵 출력이므로 무시하셔도 됩니다.

map은 입력을 받아 사각형 칸에는 1, 나머지는 0을 만드는 맵 배열입니다.

2. visit는 탐색할 때 방문한 곳을 체크하는 배열입니다.

3. make_map 함수는 주어진 사각형의 양 끝 좌표를 가지고 사각형 내부를 1로 채우는 함수입니다.

4. BFS는 맵 값이 0인 부분을 기준으로 탐색하여 칸의 개수를 리턴하는 함수입니다.

초반에는 좌표를 구조체를 가지고 했으나, pair로 바꾸었습니다. Warning이 떠서...

예제는 물론이고 질문 게시판의 반례를 모두 적용해보았고 나름대로 테스트들을 가지고 돌렸는데 잘나왔습니다.

하지만 계속 틀렸다고 나와서... 어디에서 잘못 되었는지 잘모르겠습니다.

도움 주시면 감사드리겠습니다.

#include <iostream>
#include <vector>
#include <utility>
#include <cstdio>
#include <math.h>
#include <cstdlib>
#include <queue>
#include <algorithm>
using namespace std;

bool map[101][101]={0,};
bool visit[101][101] = {0,};
void print_out1(int n, int m);
void print_out2(int n, int m);
void make_map(pair<int, int> d1,  pair<int, int> d2);
int BFS(int i, int j, int N, int M);
int x_move[4] = {-1, 0, 0, 1};
int y_move[4] = {0, -1, 1, 0};
int main(){
    int N=0, M=0, K=0;
    vector<int> res;
    scanf("%d %d %d", &M, &N, &K);
    cin.ignore();
    for(int i=0; i<K; i++){   //입력받아서 사각형의 좌표를 map배열에 1 저장
        vector<int> v;
        for(int j=0; j<4; j++){
            int temp=0;
            cin>>temp;
            v.push_back(temp);
        } 
        pair<int, int> d1 = make_pair(v[0]+1, v[1]+1); 
        pair<int, int> d2 = make_pair(v[2], v[3]); 
        map[d1.second][d1.first]= 1;
        map[d2.second][d2.first] = 1;    
        make_map(d1, d2);  // 사각형 내부를 1로 채우는 함수
    }
    for(int i=1; i<=N; i++){     //실질적으로 0부분을 찾아서 칸의 개수를 구하는 루프문
        for(int j=1; j<=M; j++){
            if(map[j][i] == 0 && visit[j][i] == false){
                int ans = 0;
                ans = BFS(i, j, N, M);
                res.push_back(ans);
            }
        }
    }
    //print_out1(M,N);     // 맵 출력하는 부분
    //cout << endl;
    //print_out2(M,N);
    sort(res.begin(), res.end());  // 오름차순 정렬
    cout << res.size() << endl;
    for(int i=0; i<res.size(); i++){
        cout << res[i] << " ";
    }
    cout << endl;

}
 void print_out1(int n, int m){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cout << map[i][j] << " ";
        }
        cout << endl;
    }
}   
void print_out2(int n, int m){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cout << visit[i][j] << " ";
        }
        cout << endl;
    }
}
void make_map(pair<int, int> d1, pair<int, int> d2){
    queue<pair<int, int> > q;
    q.push(d1);
    q.push(d2);
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            int _x = x+x_move[i]; 
            int _y = y+y_move[i]; 
            if(_x < d1.first || _x > d2.first || _y < d1.second || _y > d2.second){
                continue;
            }   // 사각형 좌표를 벗어나면 제외
            if(map[_y][_x] == 0){
                map[_y][_x] = 1;
                pair<int, int> d = make_pair(_x, _y); 
                q.push(d); 
            }
        }   
    } 
}
int BFS(int i, int j, int N, int M){
    queue<pair<int, int> >q;
    int ans=1;
    pair<int, int> d = make_pair(i, j);
    q.push(d);
    visit[j][i] = true;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            int _x = x+x_move[i];
            int _y = y+y_move[i];
            if(_x < 1 || _x > N || _y < 1 || _y > M){
                continue;   // 그리드 크기를 벗어나면 제외
            }
            if(map[_y][_x] == 0 && visit[_y][_x] == false){
                visit[_y][_x] = true;
                pair<int, int> d = make_pair(_x, _y); 
                q.push(d);
                ans++;
            }
        }
    }
    return ans;
}

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

문제

문제

출처

ICPC

안녕하세요 BFS로 코드를 구성했는데 계속 틀렸다고 나옵니다.

ldkl123 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말