백준 1388번 : 바닥 장식 C++ dfs

 

dfs 문제이다. 

모든 바닥을 다 살펴봐야하므로 main에서 바닥을 전부 탐색하는 이중 for문을 썼다.

해당 for문은 각 바닥 장식의 시작점일때 바닥 판자 갯수를 ++하고, dfs를 호출하는 역할을 한다.

즉 dfs 가 main에서 불리고 나서 다음 바닥이 계속 같은 바닥 장식이면 dfs내에서 재귀로 계속 돌아가고 다르면 return 하여 다시 for문을 돌며 카운트 되지 않은 바닥을 찾는다. 

 

주어진 예시 말고 

4 4

-|-|

|-|-

-|-|

|-|-

일땐 답은 16이 되어야하고

4 4

---|

|--|

--||

--|-

이면 답은 8이 되어야한다.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>

using namespace std;

const int MAX = 101;
int n,m;
char badak[MAX][MAX];
int visited[MAX][MAX];
int cnt;
char now = '-';

void dfs(int i, int j) {
	// 다른 바닥 장식이면 return
	if (badak[i][j] != now) return;
	visited[i][j] = 1;
	// 바닥 장식 모양이 - 일 때
	if (badak[i][j] == '-') {
		if (j + 1 < m) {
			if (!visited[i][j + 1]) {
				dfs(i, j + 1);
			}
		}
	}
	// 바닥 장식 모양이 | 일 때
	else if (badak[i][j] == '|') {
		if (i + 1 < n) {
			if (!visited[i + 1][j]) {
				dfs(i + 1, j);
			}
		}
	}
}


int main(void) {
	cin >> n >> m;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> badak[i][j];
		}
	}
	
	// badak을 돌면서 방문하지 않은 나무판자 시작부분에서 cnt++한다.
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			// 방문하지 않은 바닥일 때
			if (!visited[i][j]) {
				visited[i][j] = 1;
				// 바닥 판자 갯수 ++
				cnt++;
				// 바닥 장식 모양이 - 일 때
				if (badak[i][j] == '-') {
					if (j + 1 < m) {
						// 다음 바닥이 방문하지 않은 것이면..
						if (!visited[i][j+1]) {
							now = '-';
							dfs(i, j + 1);
						}
					}
				}
				// 바닥 장식 모양이 | 일 때
				else if (badak[i][j] == '|') {
					if (i + 1 < n) {
						// 다음 바닥이 방문하지 않은 것이면..
						if (!visited[i+1][j]) {
							now = '|';
							dfs(i + 1, j);
						}
					}
				}
			}
		}
	}

	cout << cnt << "\n";
}