일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- silver
- BOJ
- 영화
- 백준
- benefits
- array
- 리뷰
- 코딩 테스트
- review
- Greedy
- 나는솔로
- 2020
- Netflix
- 알고리즘
- 수능
- 카카오
- parametric search
- BFS
- coding
- Recursive
- kakao
- 넷플릭스
- Algorithm
- 추천
- 완전탐색
- Movie
- health
- usaco
- 영어
- 해설
Archives
- Today
- Total
Young
Why Did the Cow Cross the Road III (Silver) 본문
728x90
반응형
https://www.acmicpc.net/problem/14466
개인적으로 해석을 문제를 햇갈리게 하여, 영어로 문제를 읽는걸 추천한다.
(r,c) - (r`,c`) 의 의미는 이 두개의 vertex를 직접 가기 위해서는 길을 건너야 한다는 뜻이다.
즉, 이 두 개 사이에 길이 있다.
이 문제를 풀기 위해서 길이 있으면, 문제에서 건너지 못한다는 조건은 없었으나 이 조건을 하나 더 추가했다.
그렇게 조건을 주고, 임의의 한 소에서 출발하여 BFS를 돌면, 도달하지 못하는 소가 있거나, 없을 수 있는데
이때 도달하지 못하는 소는 반드시 길을 건너야 한다는 것을 생각할 수 있었다.
가지 못한다는 표현을 여러가지 다양하게 할 수 있다. 나는 비트마스크를 사용해서 구현해봤다.
모든 소에서 출발하는 BFS를 돌리고 2로 나눠줘서 출력하면 된다.
A소에서 B소를 도달하지 못하면, B소 또한 A소를 도달하지 못하기 때문이다.
좀 더 정교하게 만들수도 있는데, 굳이 그럴필요는 없어 보여서 마무리 지었다.
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
|
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <map>
#define endl '\n'
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
map<pii, int> st;
bool range(int y, int x, int n) {
return !(y <= 0 || y > n || x <= 0 || x > n);
}
int mp[101][101];
bool cow_mp[101][101];
int n, k, r;
bool chk[101][101];
int main() {
FastIO;
for (int dir = 0; dir < 4; dir++) // 비트마스킹을 하기 위해서 방향도 4개밖에 되지 않는데, 굳이 맵 자료구조를 쓸 필요가 있나 싶겠지만 써봤다.
st[pii(dy[dir], dx[dir])] = dir;
// 0 : e / 1 : s / 2 : w / 3 : n
cin >> n >> k >> r;
for (int i = 0; i < r; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
int dyy = c - a, dxx = d - b; // 방향을 구한다.
mp[a][b] |= (1<<st[pii(dyy, dxx)]);
dyy *= -1, dxx *= -1;
mp[c][d] |= (1<<st[pii(dyy, dxx)]);
}
vector<pii> cows(k);
for (int i = 0; i < k; i++) {
cin >> cows[i].first >> cows[i].second;
cow_mp[cows[i].first][cows[i].second] = true; // 소를 만났는지 확인하기 위해서 따로 맵을 만들었다.
}
int ans = 0;
for (int i = 0; i < k; i++) {
int cnt = k - 1; // bfs를 돌면서 몇명의 소를 마주쳤는지만 알면 된다. 문제가 요구하는건 이보다 더 자세히 요구하지 않는다.
memset(chk, 0, sizeof(chk));
queue<pii> q;
q.push(cows[i]);
chk[cows[i].first][cows[i].second] = true;
while (!q.empty()) {
pii f = q.front();
q.pop();
for (int dir = 0; dir < 4; dir++) {
if (mp[f.first][f.second] & (1 << dir)) continue; // 비트마스크 표시해논걸 이곳에서 처리하여 걸러낸다.
int ny = f.first + dy[dir], nx = f.second + dx[dir];
if (!range(ny, nx, n) || chk[ny][nx]) continue;
q.push({ ny,nx });
chk[ny][nx] = true;
if (cow_mp[ny][nx]) cnt -= 1; // 소를 마주쳤으므로 하나를 빼준다.
}
}
ans += cnt; // 이곳에 달했을 땐 마주치지 않은 소들의 수만 남는다.
}
cout << (ans >> 1);
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter
|
728x90
반응형
'코딩 테스트 대비 추천 문제 > USACO' 카테고리의 다른 글
Hoof, Paper, Scissors (Silver) (0) | 2019.04.05 |
---|---|
Cow Dance Show (0) | 2019.04.05 |
Moocast (0) | 2019.04.04 |
Why Did the Cow Cross the Road (Silver) (0) | 2019.04.04 |
Build Gates (0) | 2019.04.02 |