문제링크 : https://www.acmicpc.net/problem/2638


아이디어

  • 모든 노드 돌면서 주변에 2변 이상 외부 공기에 접촉되어있는지 확인

    • 이럴경우, 안쪽에 있는 공기도 외부공기로 간주되게 됨

  • 바깥 공기에 접촉하는지를 확인

    • 0,0부터 bfs 사용해서 이어져있는 공기 먼저 색칠하기
    • 단 계속 확대될 것이기 때문에 원래대로 색칠 안해줘도됨

  • 접촉되어있을경우 리스트에 넣었다가 한번에 지우기

  • 모두 없어질때까지 반복


시간복잡도 계산

  • Flood-fill로 외부공기 확인 : O(NM) = O(N^2)
  • 모든 노드 순회 : O(NM) = O(N^2)
  • 반복하는 최대상황 : O(N)
    • 가장자리 제외하고 모두 치즈가 꽉찬경우
  • 총합 : O((N^2 * N^2) * N) = O(N^3) : 1e6 가능

인트 계산

  • 치즈 위치 map : 0,1
  • 2변이상 노출시 넣을 벡터 : pair<int, int>
  • 없어지는데 걸리는 최대 횟수 : 100

코드(C++)

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
90
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int map[110][110];
bool chk[110][110];
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M; cin >> N >> M;
    
    // map 먼저 세팅
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) {
            cin >> map[j][i];
        }
    }
    
    // 없어질 치즈
    vector<pair<int, int>> v;
    int t=0;
    while(1) {
        v.clear();
        
        // 바깥 공기 먼저 설정
        fill(&chk[0][0], &chk[109][110], 0);
        queue<pair<int, int>> q;
        q.push(make_pair(0,0));
        chk[0][0] = 1;
        
        
        while(!q.empty()) {
            auto eq = q.front(); q.pop();
            int ey = eq.first;
            int ex = eq.second;
            map[ey][ex] = 2;
            
            for(int k=0; k<4; k++) {
                int ny = ey + dy[k];
                int nx = ex + dx[k];
                if(ny>=0 && ny<N && nx>=0 && nx< M) {
                    if(chk[ny][nx] == 0 && (map[ny][nx] == 0 || map[ny][nx] == 2)) {
                        chk[ny][nx] = 1;
                        q.push(make_pair(ny, nx));
                    }
                }
            }
        }
        
        // 모든 노드 순회하면서 없어질 치즈 확인
        for(int j=0; j<N; j++) {
            for(int i=0; i<M; i++) {
                if(map[j][i] == 1) {
                    int cnt=0;
                    for(int k=0; k<4; k++) {
                        int ny = j + dy[k];
                        int nx = i + dx[k];
                        if(ny>=0 && ny<N && nx>=0 && nx < M) {
                            if(map[ny][nx] == 2) cnt++;
                        }
                    }
                    if(cnt>=2) v.push_back(make_pair(j,i));
                }
            }
        }
        
        // 없앨 치즈 없을경우 종료
        if(v.empty()) break;
        
        // 치즈 없애기
        for(auto x : v) {
            int ej = x.first;
            int ei = x.second;
            map[ej][ei] = 0;
        }
        
        t++;
    }
    
    cout << t << '\n';
    
    return 0;
}
 
cs

문제유형

  • BFS - Flood Fill
    • 이어져있는 노드를 연결하는 문제
    • BFS 사용해서, 이어져 있는 노드 확인

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 9019 DSLR  (0) 2021.03.13
백준 1747 소수&팰린드롬  (0) 2021.03.13
백준 11066 파일 합치기  (0) 2021.03.09
백준 10775 공항  (0) 2021.03.09
백준 2820 자동차 공장 쉬운 풀이 (C++/CPP)  (0) 2021.03.05

문제링크 : https://www.acmicpc.net/problem/11066


문제 추상화

  • 연속해있는 값들을 두개씩 합칠 때마다 각 값을 더한 비용이 생긴다
  • 모든 값을 하나로 합칠때, 최소의 비용을 구하기

아이디어

  • 모든 경우의 수를 확인 가능?
    • 경우의 수 : 각 위치에서 앞의 것과 합칠떄, 그리고 합치지 않을때를 각각 계산
    • 그럼 중간에 하나씩 떨어져 있는 것을 계산이 불가
  • DP 사용
    • 개념이 복잡해서 헷갈릴수 있는데 천천히 읽어보자.
    • DP[x][y] : x부터 y까지 더할때 최소값
    • DP[x][y] = min(DP[x][z] + DP[z+1][y]) + sum(x~y)
    • 3중 루프를 돌아야하는데
      • y-x 값 기준
      • 시작값 x
      • 중간에 끊는 z값을 기준
    • 즉, 3중루프가 다음처럼 구현됨
      • 일단, dp[1][2], dp[2][3], dp[3][4] ... 구하고
      • dp[1][3] = dp[1][2] + dp[2][3], dp[2][4] = dp[2][3] + dp[3][4], ...
      • dp[1][4] = min(dp[1][2] + dp[2][4], dp[1][3] + dp[3][4]) ...
        • 이걸 시험 중 생각해낼 수 있을까? > 불가능
    • 문제 유형을 외우자

시간복잡도 계산

  • O(T * K^3) : T * 1.25e8

인트 계산

  • DP 최대값 : 모든 숫자가 K번 더해질경우 : 10000 * 500 * 500 = 25e8 > INT 불가, LL 사용

코드(C++)

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
#include <iostream>
 
using namespace std;
typedef long long ll;
 
const ll inf  = 2.6e9;
ll dp[510][510];
int sum[510];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t; cin >> t;
    while(t--) {
        fill(&dp[0][0], &dp[509][510], 0);
        fill(sum, sum+510, 0);
        
        int K; cin >> K;
        
        // 합을 추후 계산해야해서 미리 구함
        for(int i=1; i<=K; i++) {
            int ei; cin >> ei;
            sum[i] = sum[i-1] + ei;
        }
        
        for(int d=1; d<K; d++) {
            for(int st=1; st+d<=K; st++) {
                int en = st+d;
                
                // 초기값 무한대로 설정
                dp[st][en] = inf;
                for(int mid = st; mid<en; mid++) {
                    dp[st][en] = min(dp[st][en], dp[st][mid] + dp[mid+1][en] + sum[en]-sum[st-1]);
                }
                
            }
        }
        
        cout << dp[1][K] << '\n';
        
    }
    return 0;
}
 
cs

문제유형

  • DP - 연속한 값끼리 더해서 최소값구하기
    • 일반적 DP 사용할 경우, 중간에 홀로 떨어지는 값 발생
    • DP[st][en] : st부터 en까지의 최소값
    • DP[st][en] = min(DP[x][z] + DP[z+1][en]) + sum(st~en)
    • 3중루프가 다음처럼 구현됨
      • 일단, dp[1][2], dp[2][3], dp[3][4] ... 구하고
      • dp[1][3] = dp[1][2] + dp[2][3], dp[2][4] = dp[2][3] + dp[3][4], …
      • dp[1][4] = min(dp[1][2] + dp[2][4], dp[1][3] + dp[3][4]) ..

'알고리즘 > 백준' 카테고리의 다른 글

백준 1747 소수&팰린드롬  (0) 2021.03.13
백준 2638 치즈  (0) 2021.03.13
백준 10775 공항  (0) 2021.03.09
백준 2820 자동차 공장 쉬운 풀이 (C++/CPP)  (0) 2021.03.05
백준 6549 히스토그램에서 가장 큰 직사각형 쉬운 풀이 (C++/CPP)  (0) 2021.03.04

문제링크 : https://www.acmicpc.net/problem/10775


문제 추상화

  • 문제가 잘 이해가 안되서 한참을 해석했다.
    • 각 비행기가 1~gi에 도킹
    • 이때 최대한 도킹할 수 있는 개수 구하기

아이디어

  • 모든 경우 탐색
    • 각 비행기를 모든 게이트에 주차할 수 있는지 확인
    • 모든 게이트(G) * 비행기수(P) : G*P = 1e10 > 시간초과
      • 각 게이트가 빈 게이트를 바라보도록 함
    • union-find
    • p 배열 : 각 게이트보다 작은 게이트 중 비어있는 값
    • p 배열의 0을 지시 : 더이상 주차할 게이트가 없음 >> 종료

시간복잡도 계산

  • 모든 비행기에서 : O(G) = 1e5
  • 게이트를 확인 : O(1)
  • 게이트에 비행기 넣은후 이전 비어있는 게이트를 재확인 : O(1)

인트 계산

  • p : 게이트 최대 값 : 1e5 > INT 가능

코드

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
#include <iostream>
 
using namespace std;
 
int p[100010];
int find(int v) {
    if(p[v] == v) return p[v];
    return p[v] = find(p[v]);
}
 
void merge(int v1, int v2) {
    v1 = find(v1);
    v2 = find(v2);
    p[v1] = v2;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int G,P; cin >> G >> P;
    int cnt=0;
    // 부모 배열 초기 셋팅
    for(int i=1; i<=G; i++) {
        p[i] = i;
    }
    
    for(int i=0; i<P; i++) {
        int gate; cin >> gate;
        
        // 게이트 비어있는 곳이 없을경우
        int parentGate = find(gate);
        if(parentGate == 0) {
            break;
        }
        
        // 비어있는 게이트가 있을 경우
        cnt++;
        merge(parentGate, parentGate-1);
        
    }
    
    cout << cnt << '\n';
    
    
    
    return 0;
}
 
cs

문제유형

  • Union Find - 앞의 노드 중 비어있는 값 확인
    • 부모노드를 찾은 다음
    • 부모노드가 빈값이 없으면 종료
    • 빈값이 있을경우, 부모노드와 부모노드 이전값이랑 merge 수행

'알고리즘 > 백준' 카테고리의 다른 글

백준 2638 치즈  (0) 2021.03.13
백준 11066 파일 합치기  (0) 2021.03.09
백준 2820 자동차 공장 쉬운 풀이 (C++/CPP)  (0) 2021.03.05
백준 6549 히스토그램에서 가장 큰 직사각형 쉬운 풀이 (C++/CPP)  (0) 2021.03.04
백준 1865 웜홀 쉬운 풀이 (C++/CPP)  (0) 2021.03.04

+ Recent posts

티스토리툴바