BOJ : https://www.acmicpc.net/problem/14502

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.  일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.

www.acmicpc.net

이 문제를 해결하는데 필요한 알고리즘 : BFS or Brute force (or DFS)

나는 BFS로 풀었다.

처음에는 배열의 크기를 생각하지 못하고 시간초과 없이 어떻게 해결해야하나 했는데

8*8 크기라면 전범위를 다돌아도 괜찮을 것 같았다.

바이러스가 없는 0 부분에 1을 2칸 집어넣고 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
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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int arr[8][8];
int ans[8][8];
int Arr[8][8];
int temp[4] = { -1,1,0,0 };
int temp2[4] = { 0,0,-1,1 };
typedef pair<int, int> pii;
vector<pii> v;
int MAX, first, second;
int N, M, virus;
bool visit;
bool check[8][8];
 
void dfs(int n, int m) { // n -> 세로 m -> 가로
 
    for (int i = 0; i < 4; i++) {
        if (n + temp[i] >= 0 && n + temp[i] < N && m + temp2[i] >= 0 && m + temp2[i] < M) {
            if (arr[n + temp[i]][m + temp2[i]] == 0) {
                arr[n + temp[i]][m + temp2[i]] = 2;
                dfs(n + temp[i], m + temp2[i]);
            }
        }
    }
 
}
 
void lab() {
 
    if (virus == 3) {
        int zero = 0;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                ans[i][j] = arr[i][j];
        for (int i = 0; i < v.size(); i++) {
            dfs(v[i].first, v[i].second);
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 0) zero++;
                arr[i][j] = ans[i][j];
                ans[i][j] = Arr[i][j];
            }
        }
        MAX = max(MAX, zero);
        return;
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (i == N-1 && j == M-1) 
                visit = true;
            if (arr[i][j] == 0) {
                if (!check[i][j]) {
                    if (virus == 1)
                        check[i][j] = true, first = i, second = j;
                    arr[i][j] = 1, virus++;
                    lab();
                    if (i != first || j != second)
                        arr[i][j] = 0, virus--;
                }
            }
            if (visit == true) {
                if (i == first && j == second) {
                    visit = false;
                    if (first != N - 1 || second != M - 1) {
                        arr[first][second] = 0, virus--;
                        if (second != M - 1) {
                            j = second;
                        }
                        else {
                            i = first;
                            j = -1;
                        }
                    }
                }
                else return;
            }
        }
    }
}
 
int main() {
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
            Arr[i][j] = arr[i][j];
            if (arr[i][j] == 2) v.push_back(make_pair(i, j));
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 0) {
                arr[i][j] = 1, virus = 1, visit = false;
                lab();
                if (Arr[N - 1][M - 1] != 1)
                    if (arr[N - 1][M - 1] == 1) arr[N - 1][M - 1] = 0;
                arr[i][j] = 0;
            }
            for (int i = 0; i < N; i++)
                for (int j = 0; j < M; j++)
                    check[i][j] = false;
        }
    }
 
    cout << MAX;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

6603번 : 로또 - junnnho  (0) 2019.04.07
1182번 : 부분수열의 합 - junnnho  (0) 2019.04.07
16235번 : 나무제테크 - Junnnho  (0) 2019.04.07
BOJ 1463번 1로 만들기  (0) 2019.04.07
BOJ 1965번 상자넣기  (0) 2019.04.07

BOJ : https://www.acmicpc.net/problem/16235

 

16235번: 나무 재테크

부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든

www.acmicpc.net

이 문제를 해결하는데 필요한 알고리즘 : 구현, BFS

 

그냥 문제에 적힌 그대로 따라가면 되는 문제이다.

sort를 잘못된 위치에 적어주면 시간초과가 발생할수 있으니,

어린 나무를 확인해야하는 봄에만 sort를 시켜주면 된다.

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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
 
int N, M, K, a, b, c, temp;
int A[11][11]; // A배열은 양분을 저장할 배열
int Aarr[11][11]; // Aarr배열은 현재 양분이 저장되어 있는 배열
int x[] = { -1,-1,-1,0,0,1,1,1 };
int y[] = { -1,0,1,-1,1,-1,0,1 };
int Summer[11][11];
typedef struct _Tree {
    vector<int> tree;
};
 
_Tree Tree[11][11];
 
void spring() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (Tree[i][j].tree.size() != 0) {
                sort(Tree[i][j].tree.begin(), Tree[i][j].tree.end());
                for (int k = 0; k < Tree[i][j].tree.size(); k++) {
                    if (Aarr[i][j] >= Tree[i][j].tree[k]) {
                        Aarr[i][j] -= Tree[i][j].tree[k];
                        Tree[i][j].tree[k]++;
                    }
                    else {
                        Summer[i][j] += Tree[i][j].tree[k] / 2;
                        Tree[i][j].tree.erase(Tree[i][j].tree.begin() + k--);
                    }
                }
            }
        }
    }
}
 
void summer() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            Aarr[i][j] += Summer[i][j];
            Summer[i][j] = 0;
        }
    }
}
 
void autumn() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (Tree[i][j].tree.size() != 0) {
                for (int k = 0; k < Tree[i][j].tree.size(); k++) {
                    if (Tree[i][j].tree[k] % 5 == 0) {
                        for (int h = 0; h < 8; h++) {
                            if (i + x[h] > 0 && i + x[h] <= N && j + y[h] > 0 && j + y[h] <= N) {
                                Tree[i + x[h]][j + y[h]].tree.push_back(1);
                            }
                        }
                    }
                }
            }
        }
    }
}
 
void winter() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            Aarr[i][j] += A[i][j];
        }
    }
}
 
int main() {
    scanf("%d%d%d", &N, &M, &K);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &A[i][j]);
            Aarr[i][j] = 5;
        }
    }
    for (int i = 0; i < M; i++) {
        scanf("%d%d%d", &a, &b, &c);
        Tree[a][b].tree.push_back(c);
    }
    while (K--) {
        spring(), summer(), autumn(), winter();
    }
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            temp += Tree[i][j].tree.size();
 
    printf("%d", temp);
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

1182번 : 부분수열의 합 - junnnho  (0) 2019.04.07
14502번 : 연구소 - Junnnho  (0) 2019.04.07
BOJ 1463번 1로 만들기  (0) 2019.04.07
BOJ 1965번 상자넣기  (0) 2019.04.07
BOJ 1937번 욕심쟁이 판다  (0) 2019.04.06

BOJ : https://www.acmicpc.net/problem/1463

GitHub : https://github.com/junho0956/Algorithm/blob/master/1463/1463/%EC%86%8C%EC%8A%A4.cpp

 

주어진 숫자를 가지고 1을 찾아가는 단순한 방법을 사용하면

테스트케이스의 수가 많아 시간초과에 걸리게 된다.

1로 가게 되는 경우를 거꾸로 생각해서 최적의 계산 횟수를 저장해둔다면 1~1000000 의

모든 경우를 1번만 계산한 후 테스트케이스에 맞게 바로바로 출력해주면 된다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
#pragma warning(disable:4996)
 
int arr[1000001];
 
int main() {
    arr[1] = 0, arr[2] = 1, arr[3] = 1, arr[4] = 2;
    int number;
    cin >> number;
 
    for (int i = 5; i <= number; i++) {
        if (i % 2 != 0 && i % 3 != 0) {
            arr[i] = arr[i - 1] + 1;
        }
        else {
            arr[i] = arr[i - 1] + 1;
            if (i % 2 == 0) if (arr[i] > arr[i / 2] + 1) arr[i] = arr[i / 2] + 1;
            if (i % 3 == 0) if (arr[i] > arr[i / 3] + 1) arr[i] = arr[i / 3] + 1;
        }
    }
    printf("%d", arr[number]);
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

 

복습) 20.02.08

'algorithm > BOJ' 카테고리의 다른 글

14502번 : 연구소 - Junnnho  (0) 2019.04.07
16235번 : 나무제테크 - Junnnho  (0) 2019.04.07
BOJ 1965번 상자넣기  (0) 2019.04.07
BOJ 1937번 욕심쟁이 판다  (0) 2019.04.06
BOJ 14003번 가장 긴 증가하는 부분수열5  (0) 2019.04.06

BOJ : https://www.acmicpc.net/problem/1965

 

일반적인 lis 알고리즘이다.

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
#include <iostream>
#include <algorithm>
using namespace std;
 
int lis, n;
int arr[1000];
int Lis[1001];
 
int lower_bound(int start, int end, int key) {
    int mid;
    while (start < end) {
        mid = (start + end) / 2;
        if (Lis[mid] < key)
            start = mid + 1;
        else
            end = mid;
    }
    return end + 1;
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    lis = 0, Lis[0] = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > Lis[lis]) {
            Lis[lis + 1] = arr[i], lis++;
        }
        else {
            int ans = lower_bound(0,lis,arr[i]);
            Lis[ans-1] = arr[i];
        }
    }
    cout << lis+1;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

 

복습 20.02.10

'algorithm > BOJ' 카테고리의 다른 글

16235번 : 나무제테크 - Junnnho  (0) 2019.04.07
BOJ 1463번 1로 만들기  (0) 2019.04.07
BOJ 1937번 욕심쟁이 판다  (0) 2019.04.06
BOJ 14003번 가장 긴 증가하는 부분수열5  (0) 2019.04.06
BOJ 14002번 가장 긴 증가하는 부분수열4  (0) 2019.04.06

+ Recent posts

티스토리툴바