반응형

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

+ Recent posts

티스토리툴바