C++ / 30702 /국기 색칠하기 ( 깊이 우선 탐색 )

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

문제 요약

국기는 n행 m열의 격자판 ( 행열 )으로 구성되어 있습니다. 격자판의 각 칸을 이루는 색은 A부터 Z까지의 영어 알파벳 대문자로 표현합니다.

 

A[ i ][ j ] 를 국기 A의 i행 j열의 색이라고 합니다. 두 국기 A, B가 주어졌을 때, 모든 i, j에대해 A[ i ][ j ]와 B[ i ][ j ]가 같으면 둘은 같은 국기 입니다.

 

국기 A를 적절히 색칠하여 국기 B와 같게 만들려고 합니다. 국기를 색칠할 때는 다음과 같은 동작을 0회 이상 반복해야 합니다.

 

국기의 격자판 중 한  칸을 고르고, 이 칸과 같은 구역에 속한 모든 칸을 찾는다. 두 칸이 같은색이면서 상하좌우로 인접해 있을 경우 둘은 같은 구역에 속합니다.

 

이후, 해당 하는 국역의 칸들의 색을 원하는 다른 색으로 바꿉니다.

 

이 때, 영어 알파벳 대문자 외에도 임의의 다른 색을 새로 사용 할 수 있다.

 

국기 두 장의 정보가 주어졌을때, 국기 A를 적절히 색칠하여 국기 B와 똑같이 만들 수 있는지 판별해야합니다.

국기는 뒤집거나 돌릴 수 없습니다.

문제 풀이

1. 국기를 2차원 벡터 2개로 입력받습니다.

2. dfs 함수에서는 국기 A를 B로 바꿔주는 기능을 합니다. 

국기 A의 0,0부터 탐색하는데 dfs기 때문에 같은 영역일때만 탐색합니다. 여기서 영역은 같은 색깔을 의미하고,

같은 색깔일 경우 국기 B의 0,0 (국기 A의 탐색 시작 노드)의 색과 같은 색으로 덮어 씌웁니다.

국기 A               국기 B

AABBCC        DDEEFF

AABBCC        DDEEFF

AABBCC        DDEEFF

 

에서 처음 A인 영역을 국기 B의 같은 좌표( 영역 시작 좌표 A의 경우엔 0, 0 )인 색으로 덮어 씌웁니다.

국기 A              국기 B

DDBBCC       DDEEFF

DDBBCC       DDEEFF

DDBBCC       DDEEFF

 

색깔 A와 같은 영역은 다 변경 되었고 그 다음 방문하지 않은 영역들도 국기 B의 같은 좌표의 색깔로 덮어 씌웁니다.

국기 A              국기 B

DDEEFF        DDEEFF   

DDEEFF        DDEEFF

DDEEFF        DDEEFF

 

만약 같은 색으로 만들 수 없는 국기라면

국기 A     국기 B

AAAA     DEEF

BBBB     DEEF

CCCC     DEEF

 

국기 A     국기 B

DDDD     DEEF

DDDD     DEEF

DDDD     DEEF

 

국기 A의 영역 시작 좌표인 국기 B색으로 덮어지기 때문에 D로만 덮어 지게 됩니다.

국기 A의 영역 시작 좌표는 각각 0,0 1,0 2,0 국기 B의 해당 좌표의 색깔은 전부 D이기 때문입니다.

 

3. dfs를 통해 국기 A의 변경이 끝나면 n*m 2중 배열에서 국기 A와 국기 B의 색깔이 일치하는지 조건을 주고 같을 경우 개수를 셉니다.

4. 세어진 개수가 국기 사이즈와 같을 경우 "YES", 다를 경우 "NO"를 출력합니다.

주의할 점

처음에 풀때는 국기 2개를 입력받고 이를 영역별로 숫자로 바꾸고 다른 영역을 탐색 할 경우 숫자를 증가시켜 바꿔넣게 하였는데

 

국기 A       국기 B

001122      001122

001122      001122

001122      001122

 

이렇게 하여 둘이 같은 상태면 "YES"를 출력하게 하였는데 주어진 예제 2개에서는 정답을 뽑을 수 있으나 예외가 있었습니다.

질문 게시판에 있었던 테스트 케이스

2 4
AAAA
BBBB
AAAA
AAAA

를 입력하면

 

국기 A      국기 B

 0000        0000

 1111         0000

 

가 되어

"NO"를 출력하는 예외가 생겼습니다.

따라서 영역의 배치만  같은지 확인하면 틀릴 수 있기 때문에 주의해야합니다.

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

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

bool visit[51][51];
vector<vector<char>>v1;
vector<vector<char>>v2;

int n, m, cnt= 0;
string s;


void dfs(int x, int y, char c1, char c2)
{
	visit[x][y] = true;
	v1[x][y] = c2;
	for (int i = 0; i < 4; i++)
	{
		int nx = dx[i] + x;
		int ny = dy[i] + y;

		if (nx < 0 || nx >= n || ny < 0 || ny >= m)
		{
			continue;
		}
		if (!visit[nx][ny])
		{
			// 같은 영역 색 바꿈
			if (v1[nx][ny] == c1)
			{
				v1[nx][ny] = c2;
				dfs(nx, ny, c1, c2);
			}
		}


	}
}

int main()
{
	cin >> n >> m;
	v1.resize(n, vector<char>(m));
	v2.resize(n, vector<char>(m));

	// 국기 a 입력
	for (int i = 0; i < n; i++)
	{
		cin >> s;
		for (int j = 0; j < m; j++)
		{
			v1[i][j] = s[j];
		}

	}	

	// 국기 b 입력
	for (int i = 0; i < n; i++)
	{
		cin >> s;
		for (int j = 0; j < m; j++)
		{
			v2[i][j] = s[j];
		}
	}

	// 국기 a 기준으로 색 변경
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (!visit[i][j])
			{
				dfs(i, j, v1[i][j], v2[i][j]);
			}
		}
	}

	// 같은지 비교
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (v1[i][j] == v2[i][j])
			{
				cnt++;
			}
		}
	}

	if (cnt == n * m)
	{
		cout << "YES";
	}
	else
	{
		cout << "NO";
	}
	return 0;
}

반응형

예제 1

3 6
AABBCC
AABBCC
AABBCC
DDEEFF
DDEEFF
DDEEFF

결과 1

예제 2

3 4
AAAA
BBBB
CCCC
DEEF
DEEF
DEEF

결과 2

예제3

2 4
AAAA
BBBB
AAAA
AAAA

결과3