BOJ - 1388번 바닥 장식, DFS를 이용한 풀이

이번에는 대표적인 그래프 탐색 알고리즘 중 하나인, DFS를 이용해 1388번 바닥 장식 문제를 푼 과정을 정리해 보려고 합니다.

 

우선 문제 링크는 다음과 같습니다.

1388번: 바닥 장식

 

풀이에 들어가기 앞서 혹시 그래프 탐색 알고리즘인 DFS, BFS에 대한 개념 이해가 부족한 분들은 아래의 글을 참고해도 좋을 것 같습니다!

[알고리즘] DFS(Depth First Search), 깊이 우선 탐색 방식

 

[알고리즘] BFS(Breadth-First Search), 너비 우선 탐색 방식

---

● 문제 설명

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

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

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

 

● 입력

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

 

● 출력

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

 

● 예제 입력 및 출력

입력:
4 4
----
----
----
----

출력:
4
--------------------
입력:
6 9
-||--||--
--||--||-
|--||--||
||--||--|
-||--||--
--||--||-

출력:
31
--------------------
입력:
7 8
--------
|------|
||----||
|||--|||
||----||
|------|
--------

출력:
13
--------------------
입력:
10 10
||-||-|||-
||--||||||
-|-|||||||
-|-||-||-|
||--|-||||
||||||-||-
|-||||||||
||||||||||
||---|--||
-||-||||||

출력:
41
--------------------

 

우선 문제 설명을 보면 알 수 있듯이, 이 문제는 바닥 장식의 모양에 따라서 바닥에 쓰일 나무판자의 개수를 결정하게 되고, '-' 모양의 경우에는 가로로 이어지는 나무판자를 표현하며, '|'의 경우 세로로 이어지는 나무 판자를 표현함을 알 수 있습니다.

 

따라서 전체 직사각형 모양의 방의 바닥 장식 모양을 입력받고 난 후, 바닥 장식 모양을 그래프로 삼고 그래프를 DFS 방식으로 탐색하며 현재 칸이 '-' ('|') 모양인 경우에는 다음 가로(세로) 칸을 탐색하며 같은 모양인 경우 계속 탐색하고, 그렇지 않은 경우 그만 탐색하도록 합니다. (방문한 경우 방문 처리를 해줍니다.)

 

이렇게 모든 그래프의 칸에서 DFS를 실행하되, 방문 처리가 진행되지 않은 칸에서만 DFS를 외부에서 수행하여 총 DFS 실행 횟수를 counting 하면, 디자인에 사용되는 나무판자의 개수를 세도록 구현할 수 있습니다.

 

저의 경우에는 위와 같은 방식으로 풀이하기 위해 DFS를 사용했고, BFS를 사용해도 똑같은 방식으로 구현할 수 있을 것 같습니다. 

---

소스 코드

/*
	Date: 2022/07/20
	Brief:
	DFS
	Reference:
*/
#include <iostream>
#define MAX 51

using namespace std;

int n, m;
// 바닥 장식 정보를 입력 받는 배열
string arr[MAX];
// 각 칸에서 방문 처리를 담당
bool visited[MAX][MAX];

bool inRange(int x, int y) {
	return (0 <= x && x < n && 0 <= y && y < m);
}

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

	int d[] = { -1, 1 };

	for (int i = 0; i < 2; i++) {
		int nx = x, ny = y;
		if (arr[x][y] == '|')
		{
			nx += d[i];
		}
		else {
			ny += d[i];
		}
		// 범위 밖인 경우 제외
		if (!inRange(nx, ny))
			continue;
		// 다른 문양인 경우 제외
		if (arr[nx][ny] != arr[x][y])
			continue;
		if (visited[nx][ny])
			continue;
		dfs(nx, ny);
	}
}

int main() {
	cin.tie(NULL);
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int res = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visited[i][j])
				continue;
			else {
				dfs(i, j);
				res++;
			}
		}
	}

	cout << res << endl;

	return 0;
}