반응형

https://www.acmicpc.net/problem/3184

 

3184번: 양

첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 지도를 입력받고, v와 o의 개수를 세어 ans에 저장해 줍니다.

 

2. 방문하지 않은 좌표들을 방문하면서, bfs를 돌려주고, 각 영역의 양과 늑대의 수를 세어주고, 늑대가 양보다 많다면 ans에서 양의 수를 빼주고, 그렇지 않다면 늑대의 수를 빼줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
82
83
84
#include<iostream>
#include<queue>
#include<string>
 
using namespace std;
 
int R, C;
string arr[250];
int visited[250][250];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
pair<int, int> ans;
 
void bfs(int y, int x)
{
    int v = 0, o = 0;
 
    queue<pair<int, int>> q;
 
    q.push({ y,x });
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        if (arr[y][x] == 'v') v++;
        else if (arr[y][x] == 'o') o++;
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < R && xx >= 0 && xx < C) {
                if (visited[yy][xx] == 0 && arr[yy][xx] != '#') {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
            }
        }
    }
 
    if (v >= o) {
        ans.first -= o;
    }
    else {
        ans.second -= v;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> R >> C;
 
    for (int i = 0; i < R; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (arr[i][j] == 'v') {
                ans.second++;
            }
            else if(arr[i][j] == 'o') {
                ans.first++;
            }
        }
    }
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (visited[i][j] == 0 && arr[i][j] != '#') {
                visited[i][j] = 1;
                bfs(i, j);
            }
        }
    }
 
    cout << ans.first << ' ' << ans.second;
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 16936번 - 나3곱2 (C++)  (0) 2023.09.08
[ 백준 ] 11567번 - 선진이의 겨울 왕국 (C++)  (0) 2023.09.07
[ 백준 ] 3967번 - 매직 스타 (C++)  (0) 2023.09.05
[ 백준 ] 2146번 - 다리 만들기 (C++)  (0) 2023.09.04
[ 백준 ] 1486번 - 등산 (C++)  (0) 2023.09.03

+ Recent posts

티스토리툴바