https://www.acmicpc.net/problem/1941
1941번: 소문난 칠공주
총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다. 위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이
www.acmicpc.net
처음에 문제에서 잘못 이해를 했습니다. 파란색으로된 박스랑 초록된 박스를 보면
처음에는 Y를 중심으로 가로세로만 되는줄 알았는데
각각이 가로와 세로에 붙어만 있으면 되는것이였습니다.
그러면 무슨 방식으로 문제를 풀면될까요?
쉽게 2차원배열에서 무작정 7개를 뽑아서 그것이 가로와세로에 붙어만 있는지 확인해서 조건에 맞으면
갯수를 세면 되는 문제입니다.
탈출조건은
아래소스와 같이 Y인 임도연파가 4명일때
S인 이다솜파가 4명이상 이고 7명이고 Y인 임도연파가 4명이 되지 않는다면 그때
가로세로에 위치한지를 파악하기위해 dfs나 bfs 를 돌려서 구역이 몇개인지 세면됩니다.
그렇게 해서 한개의 구역이라면 갯수를 세서 결국 출력만 하면됩니다.
위에서 7개가 뽑히는 방식은 그림을 보면
000
000
000 일때 7 개가뽑히는 방식은
이렇게 5 * 5 에서 뽑힌다고 생각하면됩니다.
|
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
|
#include<stdio.h>
#include<string.h>
using namespace std;
char map[5][5];
int chk[5][5];
int cchk[5][5];
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
int cnt = 0;
void sol(int y,int x) {
for (int d = 0; d < 4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (0 <= ny && ny < 5 && 0 <= nx && nx < 5) {
if (cchk[ny][nx] == 0&&chk[ny][nx]==1) {
cchk[ny][nx] = 1;
sol(ny, nx);
}
}
}
}
void dfs(int y, int x, int idx,int S,int Y) {
if (Y >= 4)return;
if (idx == 7&&S>=4) {
int c = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (chk[i][j] == 1&&cchk[i][j]==0) {
cchk[i][j] = 1;
c++;
sol(i,j);
}
}
}
memset(cchk, 0, sizeof(cchk));
if (c == 1) {
cnt++;
}
return;
}
else {
for (int i = y; i < 5; i++) {
for (int j = x; j < 5; j++) {
if (chk[i][j] == 0) {
chk[i][j] = 1;
if (map[i][j] == 'S') {
dfs(i, j, idx + 1, S + 1, Y);
}
else
{
dfs(i,j, idx + 1, S, Y + 1);
}
chk[i][j] = 0;
}
}
x = 0;
}
}
}
int main(void)
{
for(int i=0;i<5;i++)
scanf("%s", map[i]);
dfs(0, 0, 0,0,0);
printf("%d", cnt);
return 0;
}
|
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 순열의 모든것 풀어봅시다 (0) | 2019.08.20 |
|---|---|
| 백준 1244 스위치 켜고 끄기 (0) | 2019.07.28 |
| 백준 1182 부분수열의 합 (0) | 2019.07.24 |
| 백준 11723 집합 (0) | 2019.07.24 |
| 백준 6603 로또 (0) | 2019.07.24 |
댓글