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

 

2748번: 피보나치 수 2

문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를

www.acmicpc.net

n번째 피보나치 수를 배열에 저장해놓는다.

그러면 n번째까지의 피보나치 수를 구하는데 O(n)이 걸리고 그 이후로 접근할 때는 O(1)이면 바로 접근 가능하다.

 

i번째 피보나치 수 = i-1번째 피보나치 수 + i-2번째 피보나치 수

0번째와 1번째를 미리 넣어놓고 이 점화식을 이용하면 모든 피보나치수를 구할 수 있다.

 

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
#include <iostream>
using namespace std;
 
long long pibo[91];
 
int main()
{
 
    int n;
    cin >> n;
 
    pibo[0] = 0;
    pibo[1] = 1;
 
    for (int i = 2; i <= 90; i++) {
        pibo[i] = pibo[i - 1] + pibo[i - 2];
    }
 
    cout << pibo[n];
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 1806. 부분합  (0) 2019.07.16
[BOJ] 2003. 수들의 합 2  (0) 2019.07.15
[BOJ] 14889. 스타트와 링크(비트마스크 풀이)  (0) 2019.07.11
[BOJ] 14391. 종이 조각  (0) 2019.07.11
[BOJ] 1182. 부분수열의 합  (0) 2019.07.11

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

 

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

www.acmicpc.net

앞에서 dfs로 풀었던 문제이지만 비트 마스크를 연습할 겸 다시 풀어보았다.

0부터 (1<<n)-1 까지의 모든 경우를 구하고 (1 << k)를 이용해서 각 자리의 수가 0이면 해당 자리는 1번 팀에 1이면 2번 팀에 넣어주도록 했다.

000111처럼 정확히 n/2로 0과 1이 나눠진 경우에만 능력치의 합을 계산해준다.

 

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
#include <iostream>
#include <vector>
using namespace std;
 
int n;
int s[20][20];
vector<int> t1;
vector<int> t2;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> s[i][j];
        }
    }
 
    int ans = -1;
    for (int i = 0; i < (1<<n); i++) {
        
        t1.clear();
        t2.clear();
 
 
        //0인 경우 t1에 그렇지 않은 경우 t1에 넣는다.
        for (int k = 0; k < n; k++) {
            if ((i & (1 << k)) == 0) {
                t1.push_back(k);
            }
            else {
                t2.push_back(k);
            }
        }
 
 
        //팀이 반으로 나눠지지 않은 경우 skip
        if (t1.size() > n / 2) continue;
        if (t2.size() > n / 2) continue;
 
 
        int t1sum = 0;
        int t2sum = 0;
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n / 2; j++) {
                if (i == j) continue;
                t1sum += s[t1[i]][t1[j]];
                t2sum += s[t2[i]][t2[j]];
            }
        }
 
 
        int diff = t1sum - t2sum;
        if (diff < 0) diff = -diff;
        if (ans == -1 || ans > diff) ans = diff;
 
    }
 
    cout << ans << '\n';
 
    return 0;
}
 
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2003. 수들의 합 2  (0) 2019.07.15
[BOJ] 2748. 피보나치 수 2  (0) 2019.07.15
[BOJ] 14391. 종이 조각  (0) 2019.07.11
[BOJ] 1182. 부분수열의 합  (0) 2019.07.11
[BOJ] 11723. 집합  (0) 2019.07.11

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

 

14391번: 종이 조각

영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다. 영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인

www.acmicpc.net

모든 칸(숫자)에 대해서 가로로 자를 경우를 1, 세로로 자를 경우를 0으로 놓고 비트 마스크를 사용하면 모든 경우를 빠르게 계산해줄 수 있다.

 

먼저 모든 경우를 위해 반복문을 0부터 1 << (n*m) 까지로 해준다.

 

n=2 , m=3

123

312

 

위와 같은 예를 들면,

000000부터 111111까지의 모든 경우를 구하는데, 각 행을 한 줄로 합쳐줘서 123312로 보고 계산하면 된다.

001100이라고 치면 3,3만 세로로 자르고 나머지는 가로로 자르는 경우이다.

각 경우마다 합을 구해서 최댓값과 비교해주면 된다.

 

 

각 경우에서는 가로 종이조각과 세로 종이조각의 수들을 구하여 합을 구해주면 된다.

먼저 한 줄로 보고 계산해줘야 하므로 k = i*m +j로 설정했다.

위의 예제에서 1행 2열의 '1'의 index는 k=4가 된다.

 

 

이런 식으로 1 << k와 모든 경우의 수를 해줄 b를 & 연산하여 각 k번째 자리에 1이 있는지 1이 없는지 구해주면 된다.

자리에 1이 있는 경우 세로이고 0이 있는 경우는 가로이다.

 

 

가로인 애들을 먼저 구해주면

각 행에서만 붙어 있는 숫자만이 하나의 숫자가 될 수 있으므로 한 행이 끝나면 sum에 더해주고 새로 숫자를 구해준다.

같은 행에서 숫자를 합치던 중에 세로인 애가 나와도 sum에 더해주면 된다. 그리고 현재 숫자를 나타내는 변수는 0으로 해주고 새로 만들어야 한다.

숫자를 합치는 방법은 (이전 숫자*10 + 현재 숫자)를 해주면 된다.

예를 들어 기존에 2였다면 2*10+3을 해줘서 23을 만들 수 있다.

 

 

세로인 애들도 마찬가지로 구해주면 된다. 대신 한 열의 행을 먼저 봐서 세로로 숫자를 만들어 주도록 하면 된다.

세로는 해당 자리에 1이 있는 경우로 &연산 결과가 (001000) 이런 식으로 나올 것이다. 즉 0이 아닌 값이면 세로 숫자에 더해준다. 가로인 경우와 비슷하게 세로에서는 한 열이 끝나면 sum에 더해주고 새로 숫자를 만들어줘야 한다. 열 중간에 가로가 나오는 경우도 마찬가지이다.

 

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
#include <iostream>
#include <string>
using namespace std;
 
int n, m;
int paper[4][4];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n >> m;
    string s;
 
    for (int i = 0; i < n; i++) {
        cin >> s;
        for (int j = 0; j < m; j++) {
            paper[i][j] = s[j] - '0';
        }
    }
 
    int ans = 0;
 
    //모든 경우 구한다.
    //0인 곳은 가로, 1인 곳은 세로
    for (int b = 0; b < (1 << (n*m)); b++) {
        int sum = 0;
 
 
        //가로모양으로 자른 애들 계산
        for (int i = 0; i < n; i++) {
            
            int now = 0;
            for (int j = 0; j < m; j++) {
                
 
                //정사각형 종이 조각을 한줄로 이어 붙였을 때의 인덱스
                int k = i*m + j;
 
                //k번째 자리값이 0이다(가로로 자를거다)                
                if ((b & (1 << k)) == 0) {
                    now = now * 10 + paper[i][j];
                }
                else { //1인 경우(세로인 경우) 앞에까지 만들어진 조각을 sum에 더해준다.
                    sum += now;
                    now = 0;
                }
            }
 
            //한 행이 끝났으면 만들어진 숫자 sum에 더해준다.
            sum += now;
        }
 
 
 
        //세로 모양으로 자른 애들 계산
        for (int j = 0; j < m; j++) {
 
            int now = 0;
            for (int i = 0; i < n; i++) {
 
                //정사각형 종이 조각을 한줄로 이어 붙였을 때의 인덱스
                int k = i*m + j;
 
                //세로인 경우에 숫자를 만들어준다.
                if ((b & (1 << k)) != 0) {
                    now = now * 10 + paper[i][j];
                }
                else {
                    sum += now;
                    now = 0;
                }
            }
 
            sum += now;
        }
        
 
        //최댓값과 비교
        if (ans < sum) ans = sum;
 
    }
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2748. 피보나치 수 2  (0) 2019.07.15
[BOJ] 14889. 스타트와 링크(비트마스크 풀이)  (0) 2019.07.11
[BOJ] 1182. 부분수열의 합  (0) 2019.07.11
[BOJ] 11723. 집합  (0) 2019.07.11
[BOJ] 1987. 알파벳  (0) 2019.07.11

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

 

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

비트마스크를 이용해서 모든 경우를 구해볼 수 있다.

 

문제의 예제 테스트 케이스를 이용해보면

5 0

-7 -3 -2 5 8

예제의 입력이 위와 같다.

 

 

 index : 4   3   2  1  0

 원소  : -7  -3  -2  5  8

00000 부터 11111( (1 << n) -1)까지의 경우를 모두 해주는데 각 자리의 숫자는 선택할 원소의 index라고 볼 수 있다.

예를 들어, 00101의 경우는 -2와 8을 선택한 경우라고 할 수 있다.

 

 

1을 포함하고 있는 자리(해당 자리의 원소를 선하는 경우)를 확인하기 위해서는 &연산을 사용하면 된다.

 

위의 00101과 1 << 2  (100)를 &연산을 해주면 00100 이 나와서 0이 아닌값(4)가 나오므로 2번째 자리에 1이 있는 것을 확인할 수 있고 마찬가지로 1 << 0 을해서 0번째자리에 1이 있는 것을 확인할 수 있다.

 

반대로 00101과 1<<3 (1000)을 &연산을 해주면 00000 이 나와서 0이 되므로 3번째 자리에 1이 없다는 것을 확인할 수 있따. 

 

이런식으로 각 자리에 1이 있으면 그 자리의 원소값을 sum에 더하고 

각자리의 확인을 마친뒤에는 sum이 s와 같은지 검사해주면된다.

 

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
#include <iostream>
using namespace std;
 
 
int n, s, ans;
int num[20];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n >> s;
 
    for (int i = 0; i < n; i++) {
        cin >> num[i];
    }
 
 
    for (int i = 1; i < (1 << n); i++) {
 
        int sum = 0;
        for (int j = 0; j < n; j++) {
            //j번째 자리수가 1을 가지고 있다.(수열의 j번째 원소를 선택하는 경우)
            if ((i & (1 << j)) != 0) {
                sum += num[j];
            }
        }
 
 
        //다 더한 값이 s
        if (sum == s) {
            ans++;
        }
    }
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 14889. 스타트와 링크(비트마스크 풀이)  (0) 2019.07.11
[BOJ] 14391. 종이 조각  (0) 2019.07.11
[BOJ] 11723. 집합  (0) 2019.07.11
[BOJ] 1987. 알파벳  (0) 2019.07.11
[BOJ] 7562. 나이트의 이동  (0) 2019.07.09

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

 

11723번: 집합

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

www.acmicpc.net

비트마스크를 연습해보는 문제이다.

 

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
#include <iostream>
#include <string>
using namespace std;
 
int m;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> m;
 
    int n = 20;
    int s = 0;
    int x;
    string command;
 
    while (m-- > 0) {
        
        
        cin >> command;
        //연산이 all이나 empty이 아닐때만 x를 입력받는다.
        if (command != "all" && command != "empty") {
            cin >> x;
            x--;
        }
        
 
        if (command == "add") {
            s = s | (1 << x);
        }
        else if (command == "remove") {
            s = s & ~(1 << x);
        }
        else if (command == "check") {
            if ((s & (1 << x)) == 0) {
                cout << 0 << '\n';
            }
            else {
                cout << 1 << '\n';
            }
        }
        else if (command == "toggle") {
            s = s ^ (1 << x);
        }
        else if (command == "all") {
            s = (1 << n ) - 1;
        }
        else if (command == "empty") {
 
            s = 0;
            
        }
        
    }
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 14391. 종이 조각  (0) 2019.07.11
[BOJ] 1182. 부분수열의 합  (0) 2019.07.11
[BOJ] 1987. 알파벳  (0) 2019.07.11
[BOJ] 7562. 나이트의 이동  (0) 2019.07.09
[BOJ] 2638. 치즈  (0) 2019.07.08

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

 

1987번: 알파벳

문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는

www.acmicpc.net

처음 보드를 입력받을 때, 알파벳을 숫자로 변환해서 저장한다.

문자 - 'A'를 해줘서 A는 0, B는 1, C는 2 이런 식으로 저장된다.

 

방문한 알파벳에는 다시 갈 수 없으므로 방문 체크를 해주어야 한다.

A문자를 방문하면 check [0]에 true 체크, B를 방문하면 check [1]을 true 표시해주는 방식으로

방문 체크를 해나간다.

 

인접한 칸으로 이동할 수 있으면 이동할 좌표와 함께 이동 횟수(cnt) 값을 증가시켜서 함께 보내준다.

 

더 이상 갈 수 없는 경우 탐색을 멈추기 위해 z변수를 두고 다음 칸으로 이동할 수 없을 때마다 값을 증가시켜줬다.

z == 4 가 되면(인접한 상하좌우 네 칸으로 모두 갈 수 없으면) 이동한 횟수를 비교해주고 return 한다.

 

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
#include <iostream>
#include <string>
using namespace std;
 
int r, c;
int ans;
bool check[26];
int map[20][20];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void solve(int x, int y, int cnt) {
    
 
    int z = 0;
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx < 0 || ny < 0 || nx >= r || ny >= c) {
            z++;
            continue;
        }
        if (check[map[nx][ny]]) {
            z++;
            continue;
        }
 
        
        check[map[nx][ny]] = true;
        solve(nx, ny, cnt+1);
        check[map[nx][ny]] = false;
    }
 
 
    //인접한 칸으로 더이상 이동할 수 없다.
    if (z == 4) {
        if (ans < cnt) ans = cnt;
        return;
    }
    
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < c; j++) {
            map[i][j] = s[j] - 'A';
        }
    }
 
 
    check[map[0][0]] = true;
    solve(0,0, 1);
 
 
    cout << ans;
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 1182. 부분수열의 합  (0) 2019.07.11
[BOJ] 11723. 집합  (0) 2019.07.11
[BOJ] 7562. 나이트의 이동  (0) 2019.07.09
[BOJ] 2638. 치즈  (0) 2019.07.08
[BOJ] 2636. 치즈  (0) 2019.07.08

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

 

7562번: 나이트의 이동

문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ...

www.acmicpc.net

위의 그림은 체스에서 나이트가 이동할 수 있는 위치를 나타낸다.

시작 위치로부터 도착 위치까지 나이트가 몇 번 움직이면 도착할 수 있는지를 구하는 문제이다.

bfs로 쉽게 최소 이동 횟수를 구해줄 수 있다.

 

 

먼저 시작 위치와 도착 위치가 같은 경우 0을 출력하고 다음 테스트 케이스로 넘어가도록 처리해준다.

그렇지 않다면 bfs로 이동을 시작한다.

현재 좌표에서 나이트가 이동할 좌표를 미리 다음과 같이 만들어 놓는다.

int dx[] = {-2,-2,-1,-1,1,1,2,2};

int dy[] = {-1,1,-2,2,-2,2,-1,1};

 

단계별로 진행하기 위해 큐의 사이즈를 미리 저장해놓고 큐의 사이즈만큼 탐색을 진행한다.

그리고 탐색이 끝날 때마다 count값을 증가시킨다.

도착점에 도착했다면 탐색을 마치고 바로 count값을 출력한다.

 

 

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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int n;
int sx, sy;
int ex, ey;
bool check[300][300];
 
//나이트가 이동할 수 있는 위치
int dx[] = {-2,-2,-1,-1,1,1,2,2};
int dy[] = {-1,1,-2,2,-2,2,-1,1};
 
void bfs() {
    memset(check, false, sizeof(check));
    queue<pair<int, int>> q;
    q.push(make_pair(sx,sy));
    check[sx][sy] = true;
    int count = 0;
 
    while (!q.empty()) {
 
        int qsize = q.size();
 
        while (qsize-- > 0) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int k = 0; k < 8; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                if (check[nx][ny]) continue;
 
                q.push(make_pair(nx, ny));
                check[nx][ny] = true;
            }
        }
 
        count++;
 
        //도착 위치에 도착한 경우 탐색 중단
        if (check[ex][ey]) {
            break;
        }
    }
 
    
    //이동 횟수 출력
    cout << count << '\n';
    
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
 
    for (int tc = 1; tc <= T; tc++) {
        cin >> n;
        cin >> sx >> sy;
        cin >> ex >> ey;
        
 
        //시작위치와 도착위치가 같은 경우 0을 출력하고 다음 테스트케이스 진행
        if (sx == ex && sy == ey) {
            cout << 0 << '\n';
            continue;
        }
 
 
        bfs();
    }
 
    
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 11723. 집합  (0) 2019.07.11
[BOJ] 1987. 알파벳  (0) 2019.07.11
[BOJ] 2638. 치즈  (0) 2019.07.08
[BOJ] 2636. 치즈  (0) 2019.07.08
[BOJ] 1347. 미로 만들기  (0) 2019.07.06

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

 

2638번: 치즈

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

www.acmicpc.net

앞에서 풀었던 2636번 치즈 (풀이 링크)문제와 비슷한 문제이다.

다른 점은 4 변 중 2 변 이상이 공기에 접촉해야 치즈가 놓는다.

답도 시간만 출력하면 된다.

 

 

앞의 문제와 마찬가지로 테두리에는 치즈가 없으므로

(0,0)을 먼저 큐에 넣어 바깥 영역을 먼저 bfs로 구하고

치즈가 두번 이상 바깥 영역(공기 부분)과 접촉해있다면 치즈가 녹는다(0이 된다).

 

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
int r, c;
int board[100][100];
bool check[100][100];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
 
 
//치즈수를 카운트
int countCheese() {
    int cnt = 0;
    for (int i = 1; i < r - 1; i++) {
        for (int j = 1; j < c - 1; j++) {
            if (board[i][j] == 1) {
                cnt++;
            }
        }
    }
 
    return cnt;
}
 
 
 
void solve() {
 
    //bfs로 바깥 영역을 체크
    queue<pair<int, int>> q;
    memset(check, false, sizeof(check));
    int x = 0;
    int y = 0;
 
    q.push(make_pair(x,y));
    check[x][y] = true;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
            if (check[nx][ny]) continue;
            if (board[nx][ny] == 1) continue;
 
            q.push(make_pair(nx, ny));
            check[nx][ny] = true;;
        }
    }
 
 
 
    for (int i = 1; i < r-1; i++) {
        for (int j = 1; j < c-1; j++) {
            if (board[i][j] == 0) continue;
 
            
            int cnt = 0;
            //네방향을 검사
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
 
                if (check[nx][ny]) {
                    //공기에 접촉하는 횟수
                    cnt++;
                }
            }
 
 
            //두 변 이상 공기에 접촉하면 녹는다.
            if (cnt >= 2) {
                board[i][j] = 0;
            }
        }
    }
 
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    cin >> r >> c;
 
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> board[i][j];
        }
    }
 
    int time = 0;
    while (true) {
        int tmp = countCheese();
 
        //치즈가 모두 녹으면 break
        if (tmp == 0) {
            break;
        }
    
        solve();
        time++;
    }
 
    cout << time << '\n';
 
 
    return 0;
}
Colored by Color Scripter
  

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 1987. 알파벳  (0) 2019.07.11
[BOJ] 7562. 나이트의 이동  (0) 2019.07.09
[BOJ] 2636. 치즈  (0) 2019.07.08
[BOJ] 1347. 미로 만들기  (0) 2019.07.06
[BOJ] 14620. 꽃길  (0) 2019.07.06

+ Recent posts

티스토리툴바