4963 - 섬의개수

 

4963번: 섬의 개수

stack or queue를 통해 문제를 풀 수 있고 이번에는 stack을 통해 c++ 공부중 배운 개념을 활용해 문제를 풀어보았다.

 

1. stack사용

- <stack>을 include해서 사용.

- 재귀를 사용.

- stack에 담을 정보는 x와 y 좌표를 담아줘야하기에 pair사용

2. pair의 사용

-utility를 include

- stack과 함께 사용할 때 -> pair를 자료형처럼 사용해주면 됨

=> stack <pair <type,type> stack이름

3. 이차원 vector를 사용해 위치정보를 담아주며 중복체크를 할 수 있음

check 배열은 0으로 초기화해서 사용해야함(아래의 예문에서 사용법을 확인가능)

---

#include <iostream>
#include <stack>
#include <vector>
#include <utility>
using namespace std;
vector <vector <int> > check(50, vector<int>(50, 0));
vector <vector <int> > v(50, vector<int>(50));
stack <pair<int, int> > st;

void stk(int n, int m)
{

	int x = st.top().first;
	int y = st.top().second;
	st.pop();

	if (x-1 >= 0 && v[x-1][y]==1&&check[x-1][y] != 1)
	{
		check[x - 1][y] = 1;
		st.push(make_pair(x - 1, y));
		stk(n,m);
	}
	if (x+1 <n && v[x+1][y] == 1&& check[x+1][y] != 1)
	{
		check[x + 1][y] = 1;
		st.push(make_pair(x+1, y));
		stk(n,m);
	}
	if (y-1 >= 0 && v[x][y-1] == 1 && check[x][y-1] != 1)
	{
		check[x][y-1] = 1;
		st.push(make_pair(x, y-1));
		stk(n,m);
	}
	if (y +1 < m && v[x][y+1] == 1 && check[x][y+1] != 1)
	{
		check[x][y+1] = 1;
		st.push(make_pair(x, y+1));
		stk(n,m);
	}//대각선
	if ((x - 1 >= 0 &&y-1>=0) && v[x - 1][y-1] == 1 && check[x - 1][y-1] != 1)
	{
		check[x - 1][y-1] = 1;
		st.push(make_pair(x - 1, y-1));
		stk(n, m);
	}
	if ((x + 1 < n && y-1>=0) && v[x + 1][y-1] == 1 && check[x + 1][y-1] != 1)
	{
		check[x + 1][y-1] = 1;
		st.push(make_pair(x + 1, y-1));
		stk(n, m);
	}
	if ((y + 1 < m && x-1>=0) && v[x-1][y+1] == 1 && check[x-1][y+1] != 1)
	{
		check[x-1][y+1] = 1;
		st.push(make_pair(x-1, y+1));
		stk(n, m);
	}
	if ((y + 1 < m &&x+1<n) && v[x+1][y + 1] == 1 && check[x+1][y + 1] != 1)
	{
		check[x+1][y + 1] = 1;
		st.push(make_pair(x+1, y + 1));
		stk(n, m);
	}

	
	
}

int main()
{
	int w, h;
	int c;
	
	while (1)
	{
		cin >> w >> h;
		swap(w, h);
		if (w == 0 && h == 0)
		{
			break;
		}
		for (int i = 0; i < w; i++)
		{
			for (int j = 0; j < h; j++)
			{
				cin >> c;
				v[i][j] = c;
			}
		}

		int cnt = 0;
		for (int i = 0; i < w; i++)
		{
			for (int j = 0; j < h; j++)
			{
				if (v[i][j] == 1&& check[i][j]==0)
				{
					check[i][j] = 1;
					cnt++;
					st.push(make_pair(i, j));
					stk(w,h);
				}
			}
		}
		for (int i = 0; i < w; i++)
		{
			for (int j = 0; j < h; j++)
			{
				check[i][j] = 0;
			}
		}
		
		st = stack < pair <int, int> > ();
		cout << cnt << '\n';
	}

	
}