1388) 바닥 장식

 출처 

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

1388번: 바닥 장식

 내 풀이 

#include<iostream>
#include<queue>

using namespace std;

int N = 0, M = 0;	//처음 입력 받을 값
int wood = 0;	//정답이 될 나무

char floors[51][51];
bool visited[51][51];

void BFS(int i, int j, bool type);

int main()
{
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		string input = "";
		cin >> input;
		for (int j = 0; j < M; j++)
		{
			floors[i][j] = input[j];
		}
	}


	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			//좌우 탐색
			if (floors[i][j] == '-' && !visited[i][j])
			{
				BFS(i, j, true);
				wood++;
			}
			//상하 탐색
			else if (floors[i][j] == '|' && !visited[i][j])
			{
				BFS(i, j, false);
				wood++;
			}
		}
	}

	cout << wood;
}

void BFS(int i, int j, bool type)
{
	queue<char>q;
	q.push(floors[i][j]);
	visited[i][j] = true;

	int cnt = 0;

	if (type)  cnt = j;
	else  cnt = i;
	
	while (!q.empty())
	{
		char cnt_floor = q.front();	
		q.pop();

		//우측 탐색일 경우 j값을 더해야함
		if (type)
		{

			if (cnt + 1 >= M) continue;

			if (!visited[i][cnt+1] && floors[i][cnt] == floors[i][cnt + 1])
			{
				q.push(floors[i][cnt+1]);
				visited[i][cnt + 1] = true;
			}
			cnt++;
		}

		//아래측 탐색일 경우  i값을 더해야함 
		else
		{
			if (cnt + 1 >= N) continue;

			if (!visited[cnt + 1][j] && floors[cnt][j] == floors[cnt + 1][j])
			{
				q.push(floors[cnt + 1][j]);
				visited[cnt + 1][j] = true;
			}
			cnt++;
		}
	}
}

 해설

BFS로 2개의 경우의 수 ( - , | ) 를 bool로 구분 후 풀어주었다.

 느낀점 

오랜만에 BFS로 문제를 풀다보니 많이 해맸다.