[소프티어] 이미지 프로세싱 / C++ 해설

더 많은 문제풀이는 아래 Github 주소에서 확인하실 수 있습니다.

https://github.com/Dongha-k/softeer-code

GitHub - Dongha-k/softeer-code: softeer 문제 풀이입니다.

문제 출처: https://softeer.ai/practice/info.do?idx=1&eid=627 

Softeer

공식 해설: https://www.softeer.ai/community/view.do?idx=683&cd=edu&pageNo=1 

Softeer

 

#include <iostream>
#include <queue>
#define X first
#define Y second
using namespace std;
typedef pair<int, int> P;

int dr[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int pixel[128][128];

int n, m;
void bfs(int x, int y, int p){
	int myColor = pixel[x][y];
	queue<P> q;
	q.push({x, y});
	pixel[x][y] = p;

	while(!q.empty()){
		P cur = q.front();
		q.pop();
		for(int i = 0 ; i < 4 ; i ++){
			int nx = cur.X + dr[i][0];
			int ny = cur.Y + dr[i][1];
			if(nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
			if(pixel[nx][ny] != myColor) continue;
			pixel[nx][ny] = p;
			q.push({nx, ny});
		}
	}
}
int main(int argc, char** argv)
{
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int q;
	cin >> n >> m;

	for(int i = 0 ; i < n ; i ++){
		for(int j = 0 ; j < m ; j ++){
			cin >> pixel[i][j];
		}
	}
	
	cin >> q;

	for(int i = 0 ; i < q ; i ++){
		int x, y, p;
		cin >> x >> y >> p;
		x --;
		y --;
		if(pixel[x][y] == p) continue;
		bfs(x, y, p);
	}
	for(int i = 0 ; i < n ; i ++){
		for(int j = 0 ; j < m ; j ++){
			cout << pixel[i][j] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

좌표는 개인적으로 0부터가 편해서 x, y 좌표를 입력받을 시 1을 빼주었다. 일반적인 2d map에 색을 칠하는 bfs문제이다.

 

주의할 점

if(pixel[x][y] == p) continue;

주의할 점은 윗줄을 bfs 수행 이전에 처리해주는 것이다. 이 부분을 넘겨주지 않으면 같은 색을 같은 색으로 칠하려고 하니 구분이 되지 않는다. 원래색이랑 바꾸려는 색이랑은 따로 프로세싱해주지 않아도 결과가 같으니 넘겨준다.

 

Recursion을 이용한 dfs도 좋은 방법이겠지만, 메모리 함수 스택에 넘겨줘야할 것들이 너무 많기에 시간초과가 발생할 것 같았다. 그렇기에 queue 자료구조를 이용한 bfs를 사용하였다.