반응형
문제 링크: https://www.acmicpc.net/problem/1941
1941번: 소문난 칠공주
총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작
www.acmicpc.net
<문제 풀이> 백트랙킹
5X5 격자에서 7자리를 뽑아서(2차원 배열에서 조합) BFS로 연결 여부 확인 + S의 개수가 4 이상인지 확인하면 됩니다.
2차원 배열 조합
for (int i = s; i < 25; i++) {
int x = i / 5;
int y = i % 5;
res[x][y] = 1;
dfs(i + 1, k + 1);
res[x][y] = 0;
}
<C++ 소스 코드>
|
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <cmath>
#include <deque>
#include <cstdlib>
using namespace std;
#define X first
#define Y second
int res[5][5];
int dx[4] = {0, 0, 1, -1};
int dy[4] = { -1, 1, 0, 0 };
bool visited[5][5];
vector<vector<char> > v(5);
int cnt = 0;
void dfs(int s, int k) {
if (k == 7) {
int temp = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (res[i][j] == 1 && v[i][j] == 'S') {
temp++;
}
}
}
if (temp >= 4) {
int connected = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (res[i][j] == 1 && !visited[i][j]) {
queue<pair<int, int> > Q;
Q.push({ i, j });
visited[i][j] = true;
while (!Q.empty()) {
auto cur = Q.front(); Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5)continue;
if (visited[nx][ny] || res[nx][ny] == 0)continue;
Q.push({ nx, ny });
visited[nx][ny] = true;
}
}
connected++;
}
}
}
if (connected == 1) cnt++;
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
visited[i][j] = 0;
}
}
return;
}
for (int i = s; i < 25; i++) {
int x = i / 5;
int y = i % 5;
res[x][y] = 1;
dfs(i + 1, k + 1);
res[x][y] = 0;
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
for (int i = 0; i < 5; i++) {
string s; cin >> s;
int s_len = s.length();
v[i].resize(5);
for (int j = 0; j < s_len; j++) {
v[i][j] = s[j];
}
}
dfs(0, 0);
cout << cnt;
return 0;
}
|
cs |
반응형
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [백준 18809번] Gaaaaaaaaaarden (0) | 2022.01.02 |
|---|---|
| [백준 1799번] 비숍 (0) | 2021.12.31 |
| [백준 16987번] 계란으로 계란치기 (0) | 2021.12.30 |
| [백준 2448번] 별 찍기 - 11 (0) | 2021.12.27 |
| [백준 2447번] 별 찍기 - 10 (0) | 2021.12.27 |
