[알고리즘](bfs 유형) 음료수 얼려먹기 (from 이코테)

문제

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된 다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한 다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 충 아이스크림의 개수를 구하는 프로그램을 작성 하시오. 다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.

00110

00011

111111

00000

---

입력

첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1≤ N, M ≤ 1,000)

• 두 번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
• 이때 구멍이 뚫려있는 부분은 0. 그렇지 않은 부분은 1이다.

---

출력 

한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

---

IDEAS

• 인접 리스트나, 인접 매트릭스를 만들고 스택 자료구조를 통해  탐색하는게 정석이지만, 지금의 경우 게임 처럼 맵이 주어지는 문제이기에 인접 리스트를 만들지 않기로 했다.
• 주어진 지점을 기준으로 주변을 탐색하여 더이상 탐색하지 못하는 상황까지 탐색을 하는 문제이다. 따라서 dfs보다는 bfs가 적합하다.
• 모든 지점에서 탐색 함수를 호출하고, 탐색한곳은 값을 바꿔주어 다시 탐색하지 못하게 한다.
• 이러한 탐새의 갯수가 얼음의 갯수가 될것이다.

---

배운점

• dfs 와 bfs를 선택할때 가장 중요한 점은 주변을 탐색하느냐인것 같다.
• c++에서 이차원 배열을 함수의 인자로 넘겨줄 계획이라면, 동적할당을 활용하는게 좋다.

//90 x 100 이차원 정수 배열 동적할당
int **map;
map = new int*[90];
for (int i=0; i<90; i++)
{
    map[i] = new int[100];
}

 

---

#include <iostream>

void	search(int **map, int i, int j, int N, int M)
{
	if (!(0<=i && i<=(N-1) && 0<=j && j<=(M-1)))
		return ;
	if (map[i][j] == 0)
	{
		map[i][j] = 2;
		search(map, i-1, j, N,M);
		search(map, i+1, j,N,M);
		search(map, i, j-1,N,M);
		search(map, i, j+1,N,M);
	}
}

int	main(void)
{
	int			cnt = 0;
	int			N, M;
	std::cin >> N >> M;
	std::string	temp;
	// int			map[N][M];
	int			**map = new int*[N];	//함수로 주고 받는데 동적할당이 가장 좋은 방법일까?
	for (int i=0; i<N; i++)
		map[i] = new int[M];

	std::cin.ignore();	//얘 없으면 쓰레기값 들어있는것 볼수 있다. cin 사용하고 ignore사용하는 습관.
	for (int i=0; i<N; i++)
	{
		getline(std::cin, temp);
		for (int j=0; j<temp.size(); j++)
		{
			map[i][j] = temp[j] - '0';
		}
	}

	for (int i=0; i<N; i++)
	{
		for (int j=0; j<M; j++)
		{
			if (map[i][j] == 0)
			{
				cnt++;
				search(map, i, j, N, M);
			}
		}
	}

	std::cout << cnt << std::endl;
}