티스토리 뷰
문제
친목하기 위해 7명의 그룹을 만드는데, 지배하기 위해 공주파가 최소 4명있어야한다.
5*5 행렬에서 얼마나 많은 그룹을 만들 수 있을것인가?
해설
백트래킹 기법을 이용하는데, 조금 창의적으로 활용한다.
이 문제를 풀기 위해 미리 알고 있으면 좋은 문제는 유명한 로또 문제이다.
7/45 로또 아님 ㅎ
로또 문제의 링크는 다음과 같다
이 문제는 주어진 수 집합(7~9개) 중 7개를 고르는 문제이다.
이걸 활용한다.
일단 5*5로 되어있는 행렬을 한줄로 펼치고, 차례대로 인덱스를 붙이자.
(0,0)에 있는건 0, (0,1)에 있는건 1.... 이렇게
(i,j)에 있는건 5*i+j의 인덱스를 가지게 된다.
그 다음 로또에서 사용했던 백트래킹 기법으로 7개를 뽑는다.
뽑은 후에 우리가 볼건 2가지
1) 공주파가 4명 이상인가?
2) 서로 붙어있는가?
1번은 처음 입력받은거에서 가져오면 될것이다.
2번은 set에 7개의 좌표를 모두 넣어놓은 다음에, bfs롤 돌린다.
만약 bfs를 통해 7개의 좌표를 모두 방문했으면 다 연결되어있다는 뜻이다.
1번과 2번을 모두 만족하면 +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 | #include <bits/stdc++.h> #pragma warning (disable : 4996) using namespace std; char s[6][6]; int v[26]; int ans[27]; int cnts = 0; int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 }; void backtracking(int l,int cnt) { if (cnt == 7) { int can = 0; for (int i = 0; i < 7; i++) can += v[ans[i]]; if (can < 4) return; set<int> st; for (int i = 0; i < 7; i++) st.insert(ans[i]); bool visit[27] = { 0 }; int tmp = 0; queue<int> bfs; bfs.push(ans[0]); while (!bfs.empty()) { int tp = bfs.front(); bfs.pop(); if (visit[tp]) continue; visit[tp] = true; tmp++; for (int i = 0; i < 4; i++) { int sx = tp / 5, sy = tp % 5; if (sx + dx[i] < 0 || sx + dx[i] >= 5 || sy + dy[i] < 0 || sy + dy[i] >= 5) continue; int wantto = (sx + dx[i]) * 5 + sy + dy[i]; if (st.find(wantto) != st.end()) bfs.push(wantto); } } if (tmp == 7) cnts++; return; } for (int i = l + 1; i <= 24; i++) { ans[cnt] = i; backtracking(i, cnt + 1); } } int main() { for (int i = 0; i < 5; i++) scanf("%s", s[i]); for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) v[i * 5 + j] = (s[i][j] == 'S' ? 1 : 0); backtracking(-1, 0); return !printf("%d", cnts); } | cs |
'알고리즘' 카테고리의 다른 글
[ BOJ 7453 ] 합이 0인 네 정수 (0) | 2020.12.14 |
---|---|
[ BOJ 1071 ] 소트 (0) | 2020.08.30 |
[ 오늘의 연습 ] 1. 622D (0) | 2018.07.31 |
[ 백준 5475, IOI 2007 Day 2 ] 광부들의 식사(Miners) (0) | 2018.07.10 |
[ 백준 5466, IOI 2009 Day 2 ] 상인 (SalesMan) (0) | 2018.07.10 |
댓글
최근에 올라온 글
공지사항
- Total
- Today
- Yesterday
최근에 달린 댓글
링크
TAG
- Backprop
- Deep learning
- 로피탈
- 백준
- 백준 17411
- 해석학 Chapter 5
- JOI 2021
- icpc.me/17411
- 연습문제
- Trace tirck
- cs231n assignment1
- Machine Learning
- 17411
- PMA Ch5
- Differentation
- Derivate
- mathematics
- PMA
- LInear SVM
- 해석학 Ch5
- 수(상)
- joi
- 미분
- 세그먼트 트리
- Trace trick
- 해석학
- 선형대수학
- 해석학II
- PMA 연습문제
- 수학
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함