dfs : 음료수 얼려먹기

phoenixKim·2021년 9월 24일
0

이코테_알고리즘

목록 보기
10/24

연속 입력값을 하나하나씩 저장하는 방법

https://velog.io/@hk8778/CC-%EC%97%90%EC%84%9C-%EC%88%AB%EC%9E%90-%EB%B0%B0%EC%97%B4%EC%97%90-%ED%95%98%EB%82%98%EC%94%A9-%EC%9E%85%EB%A0%A5%EB%B0%9B%EA%B8%B0

입출력

입력
4 5
00110
00011
11111
00000

출력
3

입력
15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111

출력
8

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n, m;
int v[1000][1000];

bool dfs(int y, int x)
{
	if (y < 0 || y >= n
		|| x < 0 || x >= m)
		return false;

	if (v[y][x] == 1)
	{
		return false;
	}
	else
	{
		v[y][x] = 1;
		dfs(y + 1, x);
		dfs(y - 1, x);
		dfs(y, x + 1);
		dfs(y, x - 1);
	}
	

	return true;
}
int main() {
	
	int cnt = 0;
	cin >> n >> m;

	vector<string>word(n);

	for (int i = 0; i < n; i++)
	{
		cin >> word[i];
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			v[i][j] = word[i][j] - '0';
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (dfs(i, j))
				cnt++;
		}
	}

	cout << cnt;
	return 0;
}
profile
🔥🔥🔥

0개의 댓글

관련 채용 정보