글 읽기 - 두 개의 큐를 이용해서는 풀 수 없는건가요??

rlatkdduq99 2년 전 0

큐를 두개로 관리합니다. (q, q1)

q1 : 방에 불이 켜져있어 스위치를 키고 이동할 수 있는 경우.

q : 방에 불이 켜져있지 않지만 후에 불이 켜질 가능성이 있어 재탐색을 해야하는 경우.

두 큐가 모두 비어있으면 while문을 탈 출하고, q1에서 불을 킬떄마다 킬 수 있는 방의 개수(sum)을 ++합니다.

q에서는 방에 불이 켜져있는지 확인하고 켜져있다면 q1으로 push, 꺼져있다면 다시 반복문을 돕니다.

반례를 찾을 수가 없어 질문드립니다ㅠㅠ

#include <stdio.h>
#include <stdlib.h>  
#include <cstring>
#include <bits/stdc++.h>
#include <math.h>
#include <tuple>
using namespace std;
#define X first
#define Y second        


int lights[102][102];
int vis[102][102];

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

vector<pair<int, int>> arr[102][102];

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    int n,m;
    int x,y,a,b;
    cin>>n>>m;

    for(int i=0;i<m;i++){
        cin>>x>>y>>a>>b;
        arr[x][y].push_back({a,b});
    }

    queue<pair<int,int>> q, q1;
    
    q.push({1,1});
    lights[1][1] = 1;
    int sum = 1;

    while(!q.empty()){

        auto cur1 = q.front(); q.pop();

        if(lights[cur1.X][cur1.Y] == 1 && vis[cur1.X][cur1.Y] == 0){

            q1.push({cur1.X, cur1.Y});
            vis[cur1.X][cur1.Y] = 1;

            while(!q1.empty()){
                auto cur = q1.front(); q1.pop();
                
                for(auto pcur : arr[cur.X][cur.Y]){
                    if(lights[pcur.X][pcur.Y] == 1) continue;
                    else{
                        lights[pcur.X][pcur.Y] = 1;
                        sum++;
                    }
                }
                
                for(int dir=0; dir<4;dir++){ // 이동시키기
                    int x = cur.X+dx[dir];
                    int y = cur.Y+dy[dir];
                    if(x<1||x>n||y<1||y>n) continue;
                    if(vis[x][y]!=0) continue;
                    
                    if(lights[x][y] == 0){ q.push({x,y}); }
                    else{
                        vis[x][y] = 1;
                        q1.push({x,y});
                    }
                }
            }
        }        
    }

    cout<<sum<<"\n";
 
    return 0;
}

bjh3502 2년 전 0

http://www.usaco.org/index.php...

오픈된 테케 7번에서 반례가 나오는것 같습니다...

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

문제

문제

출처

ICPC

두 개의 큐를 이용해서는 풀 수 없는건가요??

rlatkdduq99 2년 전 0

bjh3502 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말