글 읽기 - 2234 두 코드의 차이가 뭘까요....하나는정답..하나는오답

neity16 3년 전 0

저는 우선 1,2번을 위한 BFS를 따로 수행하였고

3번을 해결하기 위해 3차원 배열을 이용한 BFS로 문제를 해결했습니다.

그런데 100번줄 코드의 위치에 따라 오답 / 정답 처리가 나뉘네요..

어떤 코드냐면 새로운 방에 들어갔을 때 새로운 영역의 넓이의 값의 합으로 갱신하고 다음 queue에 넣지않으면 성공 / 다음 queue에 넣으면 실패가 됩니다

사실 논리적으로 봤을 때 새로운 방에 들어가도 어차피 벽을 부순 다음이기 때문에 알아서 종료되어 영향이 없을 것이라고 생각합니다.

(status가 1이면 continue하게 설정했기 때문)

저부분에 대해 논리적 차이를 혹시 아시는 분이 계실까요..?

( + 추가로 게시판에 있는 TC는 모두 통과했습니다 두 코드 모두)

#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#include <stack>
#define ull unsigned long long
using namespace std;
// 0325 ~ 0515
int N,M;
int ans_cnt, ans_wide, ans_wide_remove;
int board[52][52];
bool vis[52][52];
bool vis2[2][52][52];
int record[52][52];
map<int,int> record_num;
int dx[4] = {-1, 0, 1, 0}; // 서,북,동,남
int dy[4] = {0, -1, 0, 1};
vector<pair<int,int>> room_area;
bool breakWall(int num, int n){ // n은 0,1,2,3 (1,2,4,8)
    int result = num & (1 << n);
    if(result == (1 << n)) return false;
    return true;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M; // N=가로, M=세로
    for(int i=0;i<M;i++)
        for(int j=0;j<N;j++)
            cin >> board[i][j];
    // 1,2번 수행
    for(int i=0;i<M;i++)
    {
        for(int j=0;j<N;j++)
        {
            if(vis[i][j]) continue;
            ans_cnt++; // 이 성에 있는 방의 개수
            room_area.push_back({i,j});
            int cnt = 1;
            queue<pair<int,int>> q;
            q.push({i,j});
            vis[i][j] = true;
            record[i][j] = ans_cnt;
            while(!q.empty())
            {
                auto cur = q.front(); q.pop();
                for(int dir=0;dir<4;dir++)
                {
                    int ny = cur.first + dy[dir];
                    int nx = cur.second + dx[dir];
                    int num = board[cur.first][cur.second];
                    if(nx<0 or ny<0 or nx>=N or ny>=M) continue;
                    if(vis[ny][nx] or !breakWall(num,dir)) continue;
                    q.push({ny,nx});
                    vis[ny][nx] = true;
                    record[ny][nx] = ans_cnt;
                    cnt++;
                }
            }
            record_num[ans_cnt] = cnt;
            ans_wide = max(ans_wide, cnt);
        }
    }
    // 3번 수행
    for(int i=0;i<room_area.size();i++)
    {
        /* vis2 초기화 */
        for(int z=0;z<1;z++)
            for(int j=0;j<M;j++)
                fill(vis2[z][j], vis2[z][j]+N, false);
        /* BFS 수행 */
        auto cur_pos = room_area[i];
        int cur_room_num = record[cur_pos.first][cur_pos.second];
        queue<pair<pair<int,int>,int>> dq; // {{y,x},status}
        dq.push({cur_pos,0});
        vis2[0][cur_pos.first][cur_pos.second] = true;
        int sum = record_num[cur_room_num];
        while(!dq.empty())
        {
            auto cur = dq.front(); dq.pop();
            for(int dir=0;dir<4;dir++)
            {
                int ny = cur.first.first + dy[dir];
                int nx = cur.first.second + dx[dir];
                int num = board[cur.first.first][cur.first.second];
                int status = cur.second;
                if(nx<0 or ny<0 or nx>=N or ny>=M) continue;
                if(!breakWall(num, dir)){
                    if(status == 1) continue;
                    status++;
                }
                if(vis2[status][ny][nx]) continue; 
                vis2[status][ny][nx] = true;
                // dq.push({{ny,nx},status});  여기에 있으면 57%에서 실패처리
                if(cur_room_num != record[ny][nx]){
                    sum = max(sum, record_num[cur_room_num] + record_num[record[ny][nx]]);
                    continue;
                }
                dq.push({{ny,nx},status});  // 새로운 방 왔을 때 바로 종료하고 큐에 안넣으면 성공처리
            }
        }
        ans_wide_remove = max(ans_wide_remove, sum);
    }
    cout << ans_cnt << '\n' << ans_wide << '\n' << ans_wide_remove << '\n';
    return 0;
}

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

문제

문제

출처

ICPC

2234 두 코드의 차이가 뭘까요....하나는정답..하나는오답

neity16 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말