백준 1012번, "유기농 배추" ( BFS 알고리즘 )

문제

#include <iostream>
#include <vector>
#include <deque>

using namespace std; 




int main()
{

	int i_TestCase; 
	cin >> i_TestCase; 
	vector<int> m_vecAnswer;	
	
	for(int i=0; i<i_TestCase; i++)
	{
	
		vector<vector<int>> m_vec(51, vector<int>(51, 0));
		vector<vector<bool>> m_vecVisited(51, vector<bool>(51, false));

		int answer = 0;	
		deque<pair<int, int>> m_deque;
		

		int i_Row, i_Col, i_CabbageCount;

		cin >> i_Row >> i_Col >> i_CabbageCount; 
		
		for(int j=0; j<i_CabbageCount; j++)
		{
			int x, y;

			cin >> x >> y; 

			m_vec[x][y] = 1; 

			m_deque.push_back(make_pair(x, y));	
		}


		//검사 및 지렁이 개수 
		for(auto& iter : m_deque) // 배추가 심어진 구역
		{
			int i_CurX = iter.first;
			int i_CurY = iter.second;

			if (m_vecVisited[i_CurX][i_CurY] == true)
			{
				continue;
			}

			deque<pair<int, int>> routeTrack;

			routeTrack.push_back(make_pair(i_CurX, i_CurY));
			m_vecVisited[i_CurX][i_CurY] = true;	
			bool routecheck = false; 

			while(!routeTrack.empty())
			{
				i_CurX = routeTrack.front().first;
				i_CurY = routeTrack.front().second;

				// 동
				if ((i_CurX + 1) < 50)
				{
					if (m_vec[i_CurX + 1][i_CurY] == 1
						&& m_vecVisited[i_CurX + 1][i_CurY] == false)
					{
						routeTrack.push_back(make_pair(i_CurX + 1, i_CurY));
						m_vecVisited[i_CurX + 1][i_CurY] = true;
						routecheck = true;
					}
				}


				//서
				if ((i_CurX - 1) >= 0)
				{
					if( m_vec[i_CurX - 1][i_CurY] == 1
						&& m_vecVisited[i_CurX - 1][i_CurY] == false)
					{
							routeTrack.push_back(make_pair(i_CurX - 1, i_CurY));
							m_vecVisited[i_CurX - 1][i_CurY] = true;
							routecheck = true;
					}
				}


				// 남
				if ((i_CurY + 1) < 50)
				{
					if( m_vec[i_CurX][i_CurY + 1] == 1
						&& m_vecVisited[i_CurX][i_CurY + 1] == false)
					{
							routeTrack.push_back(make_pair(i_CurX, i_CurY + 1));
							m_vecVisited[i_CurX][i_CurY + 1] = true;
							routecheck = true;
					}
				}


				// 북
				if ((i_CurY - 1) >= 0)
				{
					if (m_vec[i_CurX][i_CurY - 1] == 1
						&& m_vecVisited[i_CurX][i_CurY - 1] == false)
					{
						routeTrack.push_back(make_pair(i_CurX, i_CurY - 1));
						m_vecVisited[i_CurX][i_CurY - 1] = true;
						routecheck = true;
					}
				}

				routeTrack.pop_front();

			}

			// 고립된 경우
			if (m_vecVisited[i_CurX][i_CurY] == true 
				&& routecheck == false)
				answer++; 
			

			if (routecheck)
				answer++; 
		}

		m_vecAnswer.push_back(answer);

	}


	for (auto& iter : m_vecAnswer)
	{
		cout << iter << endl;
	}

	return 0; 
}

 

 

문제 접근 방식

 

1. 일단 문제를 이해하고 어떤 알고리즘으로 접근할지가 고민이였다.

   그렇게 고민하던 와중 문제의 핵심은 인접한 배추를 검사하면서 최솟값을 구하는 것이므로 BFS 알고리즘이 생각났다.

   즉, 지렁이가 인접한 모든 배추를 돌아다니면  answer++ 하는 경우로 구상했다.

 

 

2. BFS 알고리즘으로 문제를 해결하려면 

   방문을 했는지 안했는지에 대한 정보와 해당 지점을 방문할 수 있는지 없는지의에 대한 판단 

   그리고 현재 이동한 경로에 대한 계속적인 갱신이 필요하여 

   4가지 ( m_vec = "전체 밭에서 배추가 심어진지 or 안심어졌는지") , ( m_vecVisited = "해당 배추를 방문했는지 안했는지 " ) 

             ( m_deque = "배추가 심어진 곳") , ( route = "인접한 배추를 모두 찾는 경로 및 기록")

 

 

3. 생각하지 못해 틀렸던 부분

    - 인접한 배추가 하나도 없이 고립되어 있는 경우

    - 백터 인덱스 초과 체크