글 읽기 - BFS) 반례를 알고 싶습니다

dlekgns6743 2년 전 0

테스트케이스, 질문게시판 반례들 해봤는데 안 되네요 ㅠㅠ

#include<bits/stdc++.h>
using namespace std;
int N;
char tmpC='F';
char tmp;
int visited[101][101];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int case1 =0,case2=0;
queue<pair<int,int>> Q;
string pic[101];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>N;
    for(int i=0; i<N; i++){
        cin>>pic[i];
    }
    memset(visited,0,sizeof(visited));
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(pic[i][j] != tmpC && visited[i][j] == 0){
                case1++;
                tmpC = pic[i][j];
                Q.push({i,j});
                visited[i][j] = 1;
                while(!Q.empty()){
                    auto cur = Q.front(); Q.pop();
                    for(int i=0; i<4; i++){
                        int nx = cur.first + dx[i];
                        int ny = cur.second + dy[i];
                        if(nx<0 || ny<0 || nx>=N || ny>=N) continue;
                        if(visited[nx][ny] == 1 || tmpC != pic[nx][ny]) continue;
                        Q.push({nx,ny});
                        visited[nx][ny] = 1;
                    }
                }
            }
        }
    } //적록색약 아닌 사람
    memset(visited,0,sizeof(visited));
    Q = queue<pair<int,int>>();
    tmpC = 'F';
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            tmp = pic[i][j];
            if(tmp == 'R' || tmp == 'G') tmp = 'S';
            pic[i][j] = tmp;
        }
    }
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(pic[i][j] != tmpC && visited[i][j] == 0){
                case2++;
                tmpC = pic[i][j];
                Q.push({i,j});
                visited[i][j] = 1;
                while(!Q.empty()){
                    auto cur = Q.front(); Q.pop();
                    for(int i=0; i<4; i++){
                        int nx = cur.first + dx[i];
                        int ny = cur.second + dy[i];
                        if(nx<0 || ny<0 || nx>=N || ny>=N) continue;
                        if(visited[nx][ny] == 1 || tmpC != pic[nx][ny]) continue;
                        Q.push({nx,ny});
                        visited[nx][ny] = 1;
                    }
                }
            }
        }
    } // 적록색약인 사람
    cout<<case1<<" "<<case2;
    return 0;
}

malratz 2년 전 7

GR

4 1 이 정답입니다
3 1 이 출력되네요

dlekgns6743 2년 전 0

허를ㄹㄹ 엄청 빨리 찾아주셨네요 ㅠㅠㅠ 감사합니다!!!!!!!!!!!!!!!!!!!!!!!!!!!!! tmpC로 색깔을 구분하려 했는데 그 대신에 그냥 pic[nx][ny] != pic[cur.first][cur.second]으로 했더니 됐습니다.. 다시 한 번 감사드립니다 :)

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

문제

문제

출처

ICPC

BFS) 반례를 알고 싶습니다

dlekgns6743 2년 전 0

malratz 2년 전 7

dlekgns6743 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말