반응형
https://www.acmicpc.net/problem/14466
14466번: 소가 길을 건너간 이유 6
첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다.
www.acmicpc.net
[ 문제풀이 ]
1. road[ r + r` ][ c + c` ] 배열을 만들어 길의 위치를 저장합니다.
2. cow 배열을 만들어 소들의 위치를 저장합니다.
3. for문을 통해 cow 배열을 돌면서 bfs를 이용하여 몇마리의 소를 만날 수 있는지 ans에 저장합니다.
4. ans는 만날 수 있는 모든 경우이므로 겹치는 경우를 빼기 위해 2로 나눈 후, 나올 수 있는 모든 쌍에서 ans/2를 뺀 값을 출력합니다.
[ 소스코드 ]
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 | #include<iostream> #include<queue> #include<vector> using namespace std; int N, K, R; int road[205][205]; int arr[101][101]; int dr[4] = { -1,1,0,0 }; int dc[4] = { 0,0,-1,1 }; vector<pair<int, int>> cow; int bfs(int num) { int ret = 0; int visited[101][101] = { 0 }; queue<pair<int, int>> q; q.push({ cow[num].first, cow[num].second }); while (!q.empty()) { const int r = q.front().first; const int c = q.front().second; q.pop(); if (visited[r][c] == 1) continue; visited[r][c] = 1; if (arr[r][c] == 1) { ret++; } for (int i = 0; i < 4; i++) { const int rr = r + dr[i]; const int cc = c + dc[i]; if (rr > 0 && rr <= N && cc > 0 && cc <= N) { if (road[r + rr][c + cc] != 1) { q.push({ rr,cc }); } } } } return ret - 1; } int main() { scanf("%d %d %d", &N, &K, &R); for (int i = 0; i < R; i++) { int r, c, rr, cc; scanf("%d %d %d %d", &r, &c, &rr, &cc); road[r + rr][c + cc] = 1; //길의 위치 } for (int i = 0; i < K; i++) { int r, c; scanf("%d %d", &r, &c); arr[r][c] = 1; cow.emplace_back(r, c); } int pair = (K) * (K - 1) / 2; //나올 수 있는 모든 쌍 int ans = 0; //길 없이 만날 수 있는 모든 쌍의 수 for (int i = 0; i < cow.size(); i++) { ans += bfs(i); } printf("%d", pair - ans / 2); } | cs |
반응형
'백준' 카테고리의 다른 글
[ 백준 ] 4179번 - 불! (C++) (0) | 2022.12.04 |
---|---|
[ 백준 ] 10159번 - 저울 (C++) (0) | 2022.12.03 |
[ 백준 ] 1039번 - 교환 (C++) (0) | 2022.12.01 |
[ 백준 ] 1669번 - 멍멍이 쓰다듬기 (C++) (0) | 2022.11.30 |
[ 백준 ] 11967번 - 불켜기 (C++) (0) | 2022.11.29 |