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

 

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어

www.acmicpc.net

<풀이>

1. 가능한 비의 높이마다 맵 탐색(BFS) 후, 안전영역 개수 구한다.

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
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
struct field {
    //영역 좌표
    int x, y;
};
 
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int N;
int map[100][100];
bool visited[100][100];
queue<field> q;
int tmpRes;
int res = 0;
 
void bfs(int rain) {
    while (!q.empty()) {
        field cur = q.front();
        q.pop();
 
        //4방향 모두 탐색
        for (int i = 0; i < 4; i++) {
            field nxt = cur;
 
            nxt.x += di[i];
            nxt.y += dj[i];
 
            //범위를 벗어나는 경우 continue
            if (nxt.x < 0 || nxt.y < 0 || nxt.x >= N || nxt.y >= N) {
                continue;
            }
 
            //안전한 곳만 큐에 담기
            if (map[nxt.x][nxt.y] > rain && !visited[nxt.x][nxt.y]) {
                visited[nxt.x][nxt.y] = true;
                q.push(nxt);
            }
        }
    }
}
 
int main() {
 
    //입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
 
    //가능한 비의 높이마다 탐색
    for (int rain = 0; rain < 100; rain++) {
 
        //비 높이 때 사용되는 변수들 초기화
        memset(visited, false, sizeof(visited));
        tmpRes = 0;
 
        //맵 완전탐색
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                //안전한 곳 큐에 담고 bfs, 안전영역 찾기
                if (map[i][j] > rain && !visited[i][j]) {
                    field start;
                    start.x = i;
                    start.y = j;
 
                    q.push(start);
                    visited[start.x][start.y] = true;
                    bfs(rain);
 
                    //한 곳에서 안전한 영역을 찾으면, 안전영역++
                    tmpRes++;
                }
            }
        }
 
        //최대 안전영역 개수 저장
        res = max(tmpRes, res);
    }
 
    //출력
    cout << res << "\n";
}

 

BFS에 대해 알아볼 수 있는 문제였습니다.

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 1992 - 쿼드트리  (0) 2020.04.27
[C++] 백준 2436 - 공약수  (0) 2020.04.27
[C++] 백준 2559 - 수열  (0) 2020.04.27
[C++] 백준 2467 - 용액  (0) 2020.04.27
[C++] 백준 2469 - 사다리 타기  (0) 2020.04.27

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

 

2469번: 사다리 타기

첫 줄에는 참가한 사람의 수 k가 나온다(3≤k≤26). 그 다음 줄에는 가로 막대가 놓일 전체 가로 줄의 수를 나타내는 n이 나온다(3≤n≤1,000). 그리고 세 번째 줄에는 사다리를 타고 난 후 결정된 참가자들의 최종 순서가 길이 k인 대문자 문자열로 들어온다.   k와 n, 그리고 도착순서 문자열이 나타난 다음, 이어지는 n개의 줄에는 앞서 설명한 바와 같이 ‘*’와 ‘-’ 문자로 이루어진 길이 k-1인 문자열이 주어진다. 그 중 감추어진 가로 줄

www.acmicpc.net

<풀이>

1. 사다리 시작 알파벳 문자순서와 사다리 종료 알파벳 문자순서를 알고 있으므로, '?'전까지 위와 아래에서 각각 알파벳 문자순서를 수정한다.

2. 위에서 내려온 문자순서와 아래에서 올라온 문자순서를 비교한다.

3. 문자가 같다면 '*', 순서가 서로 교차되어 같다면 '-', 그 외의 경우라면 불가능한 경우이다.

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
85
#include <iostream>
using namespace std;
 
int k, n;
char map[1000][25];
char up[26];
char down[26];
char q[25];
int qLine;
bool isAble = true;
 
int main() {
 
    //입력
    cin >> k >> n;
    for (int i = 0; i < k; i++) {
        up[i] = 'A' + i;
        cin >> down[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k - 1; j++) {
            cin >> map[i][j];
            if (map[i][j] == '?') {
                qLine = i;
            }
        }
    }
 
    //위에서부터 '?'전까지 문자 순서 바꾸기
    for (int i = 0; i < qLine; i++) {
        for (int j = 0; j < k - 1; j++) {
            if (map[i][j] == '-') {
                char tmp = up[j];
                up[j] = up[j + 1];
                up[j + 1] = tmp;
            }
        }
    }
 
    //아래에서부터 '?'전까지 문자 순서 바꾸기
    for (int i = n - 1; i > qLine; i--) {
        for (int j = 0; j < k - 1; j++) {
            if (map[i][j] == '-') {
                char tmp = down[j];
                down[j] = down[j + 1];
                down[j + 1] = tmp;
            }
        }
    }
 
    //위에 문자열, 아래 문자열 비교
    for (int i = 0; i < k - 1; i++) {
 
        //위에 문자 == 아래 문자 : *
        if (up[i] == down[i]) {
            q[i] = '*';
        }
        // 1 2 // 2 1 처럼 교차 : -
        else if (up[i] == down[i + 1] && up[i + 1] == down[i]) {
            q[i] = '-';
            char tmp = up[i];
            up[i] = up[i + 1];
            up[i + 1] = tmp;
        }
        //위에 두경우가 아닐경우 : x
        else {
            isAble = false;
            break;
        }
    }
 
    //출력
    if (isAble) {
        for (int i = 0; i < k - 1; i++) {
            cout << q[i];
        }
        cout << "\n";
    }
    else {
        for (int i = 0; i < k - 1; i++) {
            cout << 'x';
        }
        cout << "\n";
    }
}
 

 

구현에 대해 알아볼 수 있는 문제였습니다.

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 1992 - 쿼드트리  (0) 2020.04.27
[C++] 백준 2436 - 공약수  (0) 2020.04.27
[C++] 백준 2559 - 수열  (0) 2020.04.27
[C++] 백준 2467 - 용액  (0) 2020.04.27
[C++] 백준 2468 - 안전 영역  (0) 2020.04.27

+ Recent posts

티스토리툴바