반응형

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

 

1245번: 농장 관리

첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. arr 배열을 만들어 높이를 저장하고, visited 배열을 만들어 각 방문 여부를 저장합니다.

 

2. 모든 좌표를 돌면서 해당 좌표가 0이 아니고 방문하지 않았다면 bfs를 통해 같은 높이의 인접한 격자만 방문하면서 인접한 격자의 높이 가 자신보다 높으면 false를 return, 그렇지 않다면 true를 return 합니다.

 

3. bfs가 true를 return 할 때마다 ans++를 해주고, 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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[100][70];
int visited[100][70];
int dy[8] = { -1,-1,0,1,1,1,0,-1 };
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
 
bool bfs(int y, int x)
{
    bool ret = true;
 
    queue<pair<int, int>> q;
    q.push({ y,x });
    visited[y][x] = 1;
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 8; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (visited[yy][xx] != 1 && arr[yy][xx] == arr[y][x]) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
                else if (arr[yy][xx] > arr[y][x]) {
                    ret = false;
                }
            }
        }
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visited[i][j] != 1 && arr[i][j] != 0) {
                if (bfs(i, j)) ans++;
            }
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 16509번 - 장군 (C++)  (0) 2023.07.28
[ 백준 ] 15558번 - 점프 게임 (C++)  (0) 2023.07.27
[ 백준 ] 16934번 - 게임 닉네임 (C++)  (0) 2023.07.25
[ 백준 ] 7432번 - 디스크 트리 (C++)  (0) 2023.07.24
[ 백준 ] 16929번 - Two Dots (C++)  (0) 2023.07.23

+ Recent posts

티스토리툴바