16724 피리부는 사나이
알고리즘 (DFS)
1
2
3
4
5
6
7
8
9
10
11
1. 맵에 있는 서로 이어져있는 그래프의 개수를 세면 됨.
2. visit을 만들어, 이미 검사한 그래프의 원소엔 true를 표시한다. 그리고 tempVisit을 만들어, 현재 검사하고 있는 그래프의 원소에 true를 표시한다.
3. 먼저, 첫번째 셀부터 검사하지 않았으면 DFS를 실시한다.
-> 갈수있는데까지 가면서 tempVisit에 true를 표시
-> tempVsit이든 visit 배열이든 true로 표시돼있는 칸에 오면 중지
-> 이때 상태는 두가지 : 자기들끼리 돌다 만난건지, 이미 검사한 그래프로 합쳐지는 건지.
-> 전체 visit 배열이 true이면 원래 DFS에 합쳐지는 것 -> false 반환
-> 전체 visit 배열은 false이고 현재 visit배열도 false 일때 -> 진행
-> 전체 visit 배열은 false이고 현재 visit배열은 true일때 -> 자기끼리 만나는 것 -> true반환
-> 현재 검사하는 원소를 하나씩 list에 넣고, 하나씩 빼가며 전체 visit배열에 true표시하고 현재 배열은 false로 초기화하기
4. true로 반환될 때만 새로운 그래프가 만들어지는 것이므로 safezone의 개수 1증가
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <vector>
#include <string>
#define MAX_WIDTH 1000
using namespace std;
typedef struct Location {
int row;
int col;
} Location;
char map[MAX_WIDTH][MAX_WIDTH];
int n, m, safezone;
bool visit[MAX_WIDTH][MAX_WIDTH], tempVisit[MAX_WIDTH][MAX_WIDTH];
void generateSafezone();
bool DFS(int row, int col);
Location getNextCell(Location cur);
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
string temp;
cin >> temp;
for (int j = 0; j < m; j++) {
map[i][j] = temp[j];
}
}
generateSafezone();
cout << safezone;
}
void generateSafezone() {
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (!visit[i][j]) {
if (DFS(i, j)) {
safezone++;
}
}
}
bool DFS(int row, int col) {
vector<Location> q;
Location cur = { row,col };
while (!visit[cur.row][cur.col] && !tempVisit[cur.row][cur.col]) {
q.push_back({ cur.row, cur.col });
tempVisit[cur.row][cur.col] = true;
cur = getNextCell(cur);
}
bool result;
if (visit[cur.row][cur.col])
result = false;
else
result = true;
for (int i = 0; i < q.size(); i++) {
visit[q[i].row][q[i].col] = true;
tempVisit[q[i].row][q[i].col] = false;
}
return result;
}
Location getNextCell(Location cur) {
if (map[cur.row][cur.col] == 'D')
return { cur.row + 1, cur.col };
else if (map[cur.row][cur.col] == 'U')
return { cur.row - 1, cur.col };
else if (map[cur.row][cur.col] == 'L')
return { cur.row, cur.col - 1 };
else
return { cur.row, cur.col + 1 };
}