[G5] 백준 30702번 국기 색칠하기 C++ 너비 우선 탐색, 플러드 필

리뷰

 

https://www.acmicpc.net/problem/30702

국기 A의 인접한 색을 모두 새로운색으로 칠해 국기 B와 동일하게 만들 수 있는지 여부를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n, m : 국기의 세로/가로 크기를 저장할 변수
• A, B : 국기 A, B의 색 정보를 저장할 2차원 배열
• v : 국기 A의 방문 여부를 저장할 2차원 배열
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 현재 위치 정보를 정의할 구조체

 

함수

1. Input

void Input()
{
	cin >> n >> m;
	for ( int i = 0; i < n; ++i )
	{
		for ( int j = 0; j < m; ++j )
		{
			cin >> A[ i ][ j ];
		}
	}

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

 

모든 입력을 처리해 정의한 자료구조를 초기화 하기 위한 함수

 

2. FloodFill

void FloodFill( int sx, int sy, uint8_t prev, uint8_t next )
{
	queue<Pos> q;
	q.push( { sx, sy } );
	v[ sx ][ sy ] = true;
	A[ sx ][ sy ] = next;

	while ( !q.empty() )
	{
		auto [cx, cy] = q.front(); q.pop();

		for ( int i = 0; i < 4; ++i )
		{
			int nx = cx + dx[ i ], ny = cy + dy[ i ];

			if ( 0 <= nx && nx < n && 0 <= ny && ny < m && !v[ nx ][ ny ] && A[ nx ][ ny ] == prev )
			{
				v[ nx ][ ny ] = true;
				A[ nx ][ ny ] = next;
				q.push( { nx, ny } );
			}
		}
	}
}

 

국기 A의 시작 위치와 동일한 색을 국기 B의 시작 위치의 색으로 변경하기 위한 함수

 

 

문제풀이

1. Input함수를 호출해 값을 입력 받아 n, m, A, B를 초기화한다.
2. 변수 flag를 true로 저장하여 초기 상태를 만들 수 있는 상태로 정의한다.
3. n*m크기의 맵을 순회하며 현재 위치가 이미 방문한 상태인지를 체크한다.
4. 이미 방문한 상태임에도 A, B의 값이 다르다면 flag를 false로 변경 후 break처리한다.
5. 만약 이미 방문했지만 A, B의 값이 같다면 continue처리하여 다음 위치에 대한 탐색을 수행한다.
6. 방문하지 않은 위치라면 FloodFill함수에 i, j, A[i][j], B[i][j]를 매개변수로 전달해 호출한다.
7. FloodFill함수 내부에선 변수 sx, sy, prev, next에 인자를 파싱한다.
8. 맵의 범위 안에 있으면서 현재 값이 prev인 인접한 위치를 모두 next로 변경해준다.
9. 최종적으로 flag의 값이 true라면 "YES"를, 아니라면 "NO"를 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. A와 B의 국기 색이 다를 경우에만 동일한 색으로 칠해주면 된다.
2. 색칠 이후에도 색이 다른 경우를 발견하면 더 이상 탐색할 필요 없이 조기 종료 처리해주면 된다.

 

정답 코드

#include <iostream>
#include <queue>
using namespace std;

const int N = 50;
int n, m;
uint8_t A[ N ][ N ];
uint8_t B[ N ][ N ];
bool v[ N ][ N ];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
struct Pos
{
	int x, y;
};

void Input()
{
	cin >> n >> m;
	for ( int i = 0; i < n; ++i )
	{
		for ( int j = 0; j < m; ++j )
		{
			cin >> A[ i ][ j ];
		}
	}

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

void FloodFill( int sx, int sy, uint8_t prev, uint8_t next )
{
	queue<Pos> q;
	q.push( { sx, sy } );
	v[ sx ][ sy ] = true;
	A[ sx ][ sy ] = next;

	while ( !q.empty() )
	{
		auto [cx, cy] = q.front(); q.pop();

		for ( int i = 0; i < 4; ++i )
		{
			int nx = cx + dx[ i ], ny = cy + dy[ i ];

			if ( 0 <= nx && nx < n && 0 <= ny && ny < m && !v[ nx ][ ny ] && A[ nx ][ ny ] == prev )
			{
				v[ nx ][ ny ] = true;
				A[ nx ][ ny ] = next;
				q.push( { nx, ny } );
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio( 0 );
	cin.tie( 0 );

	Input();
	bool flag = true;
	for ( int i = 0; i < n; ++i )
	{
		if ( !flag )
			break;

		for ( int j = 0; j < m; ++j )
		{
			if ( v[ i ][ j ] )
			{
				if ( A[ i ][ j ] != B[ i ][ j ] )
				{
					flag = false;
					break;
				}
				continue;
			}
			
			FloodFill( i, j, A[ i ][ j ], B[ i ][ j ] );
		}
	}

	cout << ( flag ? "YES" : "NO" );
}