[백준/baekjoon] Silver4 1388. 바닥 장식

 

#include<iostream>
#include<vector>

using namespace std;

int x, y;
vector<vector<char>> map;
vector<vector<bool>> visited;
int dfs(int i, int j) {
	visited[i][j] = true;
	if (map[i][j] == '|') {
		if (i + 1 == x || map[i + 1][j] != '|') return 1;
		return dfs(i + 1, j);
	}
	else if (map[i][j] == '-') {
		if (j + 1 == y || map[i][j + 1] != '-') return 1;
		return dfs(i, j + 1);
	}
	return 0;
}

int main() {
	cin >> x >> y;
	char tile;
	map = vector<vector<char>>(x, vector<char>(y, 'o'));
	visited = vector<vector<bool>>(x, vector<bool>(y, false));
	for (int i = 0; i < x; i++) {
		for (int j = 0; j < y; j++) {
			cin >> tile;
			map[i][j] = tile;
		}
	}

	int cnt = 0;
	for (int i = 0; i < x; i++) {
		for (int j = 0; j < y; j++) {
			if (!visited[i][j]) cnt += dfs(i, j);
		}
	}

	cout << cnt << endl;
}

---

문제

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

1388번: 바닥 장식

728x90

---

[접근]

DFS 연습용으로 찾았기 때문에 무조건 DFS로 풀려고 생각했다.

DFS

https://jolly-note.tistory.com/62

DFS (Depth First Search, 깊이 우선 탐색)

---

[접근1]

값을 불러와서 저장하는 작업.

map과 visited를 초기화를 먼저 시켜주고 map에 값을 넣어줬다.

map, visited, x, y는 전역변수이다.

cin >> x >> y;
char tile;
map = vector<vector<char>>(x, vector<char>(y, 'o'));
visited = vector<vector<bool>>(x, vector<bool>(y, false));
for (int i = 0; i < x; i++) {
    for (int j = 0; j < y; j++) {
        cin >> tile;
        map[i][j] = tile;
    }
}

---

[접근2]

visited 전체를 돌면서 아직 방문하지 않았다면 dfs를 수행해준다.

dfs의 리턴값은 int로 해서 cnt값을 바로 증가시켜줄 수 있도록 했다.

int cnt = 0;
for (int i = 0; i < x; i++) {
    for (int j = 0; j < y; j++) {
        if (!visited[i][j]) cnt += dfs(i, j);
    }
}

---

[접근3]

visited를 true로 바꿔주고 map[i][j]가 '|'일 때는 마지막 행이거나 다음 행이 '|'이 아니면 1을 리턴해주고

아니면 다음 행의 dfs를 리턴해준다.

'-'인 경우에도 마찬가지로 비슷하게 수행된다.

int dfs(int i, int j) {
	visited[i][j] = true;
	if (map[i][j] == '|') {
		if (i + 1 == x || map[i + 1][j] != '|') return 1;
		return dfs(i + 1, j);
	}
	else if (map[i][j] == '-') {
		if (j + 1 == y || map[i][j + 1] != '-') return 1;
		return dfs(i, j + 1);
	}
	return 0;
}