Softeer [21년 재직자 대회 예선] 이미지 프로세싱 c++

문제 URL : https://softeer.ai/practice/6265

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

문제접근법 : 해당좌표에서 좌우상하 같은 색깔이 있다면 그색깔을 원하는색깔로 바꿔 주면되는 문제입니다.

 

dfs or bfs 아무거나 상관없이 다 적용가능합니다. 이연산은 최대 q번 해야하는데

그렇다면 방문자 처리를 매번 해당배열 사이즈만큼 만들어도 답은 나오지만 좀더 빠르게하기위해

방문자 배열을 한번만 만들고 dfs 를 q번 해야하므로 1번부터 q번까지의 방문자 숫자를 준다면 굳이 여러번 배열을 만들필요가 없습니다. 

소스코드 : 

//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
vector<vector<int>>board,check;
vector<tuple<int,int,int>> tv;
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};
void input(){
    cin>>n>>m;
    check=board = vector<vector<int>>(n,vector<int>(m));
    for(int i =0;i<n;i++){
        for(int j =0;j<m;j++){
            cin>>board[i][j];
        }
    }
    cin>>q;
    int y,x,color;
    for(int i=0;i<q;i++){
        cin>>y>>x>>color;
        tv.push_back({y-1,x-1,color});
    }

}
bool isrange(int y,int x){
    return 0<=y&&y<n&&0<=x&&x<m;
}
void dfs(int y,int x,int color,int num){
    if(check[y][x]==num)return;
    check[y][x]=num;
    for(int i =0;i<4;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        if(isrange(ny,nx)&&board[ny][nx]==board[y][x]){
            dfs(ny,nx,color,num);
        }   
    }
    board[y][x]=color;
}
void solve(){
    int num=1;
    for(auto[y,x,color]:tv){
        dfs(y,x,color,num++);
    }
    for(int i =0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<board[i][j]<<" ";
        }
        cout<<"\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    input();
    solve();

}

 

궁금한점 혹은 모르는점 또는 어떤 질문이든 댓글은 언제나 환영입니다.