백준 14716번 : 현수막

• 문제 선정 이유 : 알고리즘 문제 해결 재활 용 낮은 난이도 문제 풀이
• Solved.ac 기준 실버 1
• 사용언어 C++

문제 해석

• 그래프 탐색 알고리즘을 이용해 가능 여부
• 해당 문제는 DFS 사용

문제 풀이

• 일반 dfs 방식을 사용하면서 8방향 탐색
• dfs의 기본 : 2차원 배열을 두개 만들어서 일반적으로 입력 받을 배열과 방문 여부 배열 만들어 검사

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

int m, n;
vector<vector<int>> arr;
vector<vector<bool>> visited;

int dx[8] = {0, 0, 1, -1, 1, 1,-1,-1};
int dy[8] = { 1,-1, 0 , 0 , 1, -1, 1, -1 };

void dfs(int x, int y) {
	visited[x][y] = true;

	for (int i = 0; i < 8; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 && nx < m && ny >= 0 && ny < n && arr[nx][ny] == 1 && !visited[nx][ny]) {
			dfs(nx, ny);
		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> m >> n;
	arr.assign(m, vector<int>(n));
	visited.assign(m, vector<bool>(n, false));

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

	int cnt = 0;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == 1 && !visited[i][j]) {
				dfs(i, j);
				cnt++;
			}
		}
	}

	cout << cnt;

	return 0;
}