[백준 C++] 1388 바닥 장식

문제

형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.

이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다. 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘|’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자이다.

기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 방 바닥의 세로 크기N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 M개의 문자가 주어진다. 이것은 바닥 장식 모양이고, '-‘와 ’|‘로만 이루어져 있다. N과 M은 50 이하인 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

https://www.acmicpc.net/problem/1388

풀이

문제 카테고리는 그래프이론, DFS, BFS인데, 이것만보고 무작정 큐나 스택으로 구현하려고 하지 말자.
문제를 보면 가로나무판( - )의경우는 가로로탐색을, 세로나무판( | ) 의경우 세로로 탐색을 이어나가도록 코드를 짜야하며, (이때 지나온 나무판은 체크해줘야함)
모든 나무판위치를 전부 검토 해야한다.

즉, 나무판이 전부 이어있지않고 불규칙하고, 모든 바닥패턴을 분석해야하므로 무작정 DFS, BFS 로 접근하면 매칭이되지않는다.

1. find : 모든 나무판을 확인한다.
   
   
   
2. vertical, horizontal : 가로, 세로에따라 이어지는 나무판은 전부 하나임으로, 모두 체크해준다.
   그러면 find 함수에서 다음위치를 탐색시, 이미 하나의 나무판으로 이어졌으면 체크했으므로 건너띄기가능.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
int n, m, ** wood, res = 0;
bool** visited;
void vertical(int x, int y);
void horizontal(int x, int y);

void find() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!visited[i][j]) {
				if (wood[i][j] == 0)
					vertical(i, j);
				else
					horizontal(i, j);
				res++;
			}
		}
	}
}

void vertical(int x, int y) { //가로
	visited[x][y] = true;
	if (0 <= y - 1 && wood[x][y - 1] == 0 && !visited[x][y - 1]) // ←
		vertical(x, y - 1);
	if (y + 1 <= m - 1 && wood[x][y + 1] == 0 && !visited[x][y + 1]) // →
		vertical(x, y + 1);
}


void horizontal(int x, int y) { //세로
	visited[x][y] = true;
	if (0 <= x - 1 && wood[x - 1][y] == 1 && !visited[x - 1][y]) // ↑
		horizontal(x - 1, y);
	if (x + 1 <= n - 1 && wood[x + 1][y] == 1 && !visited[x + 1][y]) // ↓
		horizontal(x + 1, y);
}

int main(char c) {
	scanf("%d%d", &n, &m);
	wood = new int* [n];
	visited = new bool* [n];
	for (int i = 0; i < n; i++) {
		wood[i] = new int[m];
		visited[i] = new bool[m];
		scanf("%c", &c);
		for (int j = 0; j < m; j++) {
			scanf("%c", &c);
			if (c == '-')
				wood[i][j] = 0;
			else
				wood[i][j] = 1;
			visited[i][j] = false;
		}
	}

	find();

	printf("%d", res);

	return 0;
}