C++ / 1081 / 바닥 장식 ( 깊이 우선 탐색 )

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

문제 요약

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

 

방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력해야합니다.

문제 풀이

1. 방 사이즈와 나무 판자를 입력받습니다.

2. dfs 탐색에서는 x좌표 y좌표와 현재 판자를 입력 받습니다. 판자가 ' - '  인 경우는 y값만 4방향 탐색 ( 행 탐색 )

판자가 ' | ' 인 경우는 x값만 4방향 탐색 ( 열 탐색 )을 합니다.

3. 만약 현재 바닥과 다른 바닥이 나오면 무시하고 방문하지 않은 지역일 경우에 다음 dfs 인자로 넘겨줍니다.

4. 바닥 사이즈 만큼 반복문을 만들어서 방문하지 않은 지역일때 dfs함수를 돌리고 개수를 세어줍니다.

5. 개수를 출력합니다.

주의할 점

현재 바닥이 ' - ' 일 경우에는 행으로 ( 가로 ) 탐색해야하고,

' | ' 일 경우에는 열로 ( 세로 ) 로 탐색해야합니다.

코드

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


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

vector<vector<char>>v;
bool visit[100][100];
int n, m, cnt = 0;
string s;

void dfs(int x, int y, char c)
{
	visit[x][y] = true;
	int nx = x;
	int ny = y;
	for (int i = 0; i < 4; i++)
	{
		// - 인 경우
		if (c == '-')
		{
			nx = x;
			ny = dy[i] + y;
		}
		// | 인 경우
		else
		{
			nx = dx[i] + x;
			ny = y;
		}



		if (nx >= n || nx < 0 || ny < 0 || ny >= m)
		{
			continue;
		}
		// 현재 바닥과 다른경우
		if (c != v[nx][ny])
		{
			continue;
		}

		if (!visit[nx][ny])
		{

			visit[nx][ny] = true;
			dfs(nx, ny, c);
		}
	}
}


int main()
{
	cin >> n >> m;
	v.resize(n, vector<char>(m));
	for (int i = 0; i < n; i++)
	{
		cin >> s;
		for (int j = 0; j < m; j++)
		{
			v[i][j] = s[j];
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (!visit[i][j])
			{
				dfs(i, j, v[i][j]);
				// 바닥 갯수
				cnt++;
			}
		}
	}

	cout << cnt;


	return 0;
}

반응형

예제1

4 4
----
----
----
----

결과1

예제2

6 9
-||--||--
--||--||-
|--||--||
||--||--|
-||--||--
--||--||-

결과2

예제3

7 8
--------
|------|
||----||
|||--|||
||----||
|------|
--------

결과3

예제4

10 10
||-||-|||-
||--||||||
-|-|||||||
-|-||-||-|
||--|-||||
||||||-||-
|-||||||||
||||||||||
||---|--||
-||-||||||

결과4

예제5

6 6
-||--|
||||||
|||-|-
-||||-
||||-|
||-||-

결과5