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

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

 

정보올림피아드 지역본선 2013년도 고등부1번 문제이다

현재 배열을 1로 주고 1 지역에서 탐색으로 발견되는 0 지역은 1보다 큰 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
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int mx[4] = { -1,1,0,0 };
int my[4] = { 0,0,1,-1 };
int arr[1000][1000];
int zero;
queue<pair<int, int> > q;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int M, N; cin >> M >> N;
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < M; k++) {
            cin >> arr[i][k];
            if (arr[i][k] == 1) q.push({ i,k });
            else if (!arr[i][k]) zero++;
        }
    }
 
    int MAX = 0;
 
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = my[i] + y;
            int xx = mx[i] + x;
            if (yy >= 0 && xx >= 0 && yy < N && xx < M && !arr[yy][xx]) {
                q.push({ yy,xx });
                zero--;
                arr[yy][xx] = arr[y][x] + 1;
            }
        }
        MAX = MAX < arr[y][x] - 1 ? arr[y][x] - 1 : MAX;
    }
 
    if (zero) cout << "-1";
    else cout << MAX;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 2146번 다리 만들기  (0) 2020.01.14
BOJ 2178번 미로탐색  (0) 2020.01.14
BOJ 4963번 섬의 개수  (0) 2020.01.14
BOJ 2667번 단지번호붙이기  (0) 2020.01.14
BOJ 9466번 텀 프로젝트  (0) 2020.01.14

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

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

 

문제에서 요구하는 대로 구현해주면 문제될게 딱히 없는 문제이다.

** 동서남북뿐만아니라 대각선도 다봐야한다 **

더보기
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
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
#pragma warning(disable:4996)
 
vector<int> v;
queue<pair<int, int> > q;
int mx[8] = { -1,1,0,0,-1,1,1,-1 };
int my[8] = { 0,0,1,-1,-1,-1,1,1 };
int arr[50][50];
int T;
 
int main() {
 
    while (1) {
        int w, h;
        scanf("%d%d", &w, &h);
        if (w == 0 && h == 0) break;
 
        for (int i = 0; i < h; i++) {
            for (int k = 0; k < w; k++) {
                scanf("%d", &arr[i][k]);
            }
        }
 
        int cnt = 0;
        for (int i = 0; i < h; i++) {
            for (int k = 0; k < w; k++) {
                if (arr[i][k]) {
                    cnt++;
                    arr[i][k] = 0;
                    q.push({ i,k });
                    while (!q.empty()) {
                        int x = q.front().second;
                        int y = q.front().first;
                        q.pop();
 
                        for (int j = 0; j < 8; j++) {
                            int xx = mx[j] + x;
                            int yy = my[j] + y;
                            if (xx >= 0 && yy >= 0 && xx < w && yy < h && arr[yy][xx]) {
                                q.push({ yy,xx });
                                arr[yy][xx] = 0;
                            }
                        }
                    }
                }
            }
        }
        printf("%d\n", cnt);
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 2178번 미로탐색  (0) 2020.01.14
BOJ 7576번 토마토  (0) 2020.01.14
BOJ 2667번 단지번호붙이기  (0) 2020.01.14
BOJ 9466번 텀 프로젝트  (0) 2020.01.14
BOJ 10451번 순열 사이클  (0) 2020.01.14

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

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

 

정올 KOI 1996 초등부1번 문제이다.

2중 반복을 통해 y, x 좌표를 확인하여 땅이 있을 때 마다 연결된 땅을 탐색해준다.

 

더보기
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
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
#pragma warning(disable:4996)
 
vector<int> v;
queue<pair<int, int> > q;
int mx[4] = { -1,1,0,0 };
int my[4] = { 0,0,1,-1 };
int arr[25][25];
int T;
 
int main() {
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        for (int k = 0; k < T; k++) {
            scanf("%1d", &arr[i][k]);
        }
    }
 
    int cnt = 0;
    for (int i = 0; i < T; i++) {
        for (int k = 0; k < T; k++) {
            if (arr[i][k]) {
                cnt++;
                arr[i][k] = 0;
                int total = 0;
                q.push({ i,k });
                while (!q.empty()) {
                    int x = q.front().second;
                    int y = q.front().first;
                    q.pop();
 
                    total++;
                    for (int j = 0; j < 4; j++) {
                        int xx = mx[j] + x;
                        int yy = my[j] + y;
                        if (xx >= 0 && yy >= 0 && xx < T && yy < T && arr[yy][xx]) {
                            q.push({ yy,xx });
                            arr[yy][xx] = 0;
                        }
                    }
                }
                v.push_back(total);
            }
        }
    }
    sort(v.begin(), v.end());
    printf("%d\n", cnt);
    for (int i = 0; i < v.size(); i++) printf("%d\n", v[i]);
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 7576번 토마토  (0) 2020.01.14
BOJ 4963번 섬의 개수  (0) 2020.01.14
BOJ 9466번 텀 프로젝트  (0) 2020.01.14
BOJ 10451번 순열 사이클  (0) 2020.01.14
BOJ 2331번 반복 수열  (0) 2020.01.14

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

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

 

텀 프로젝트

문제는 이해하는데 어려움이 없을 것이다.

 

** 시간을 빠르게 해결하기 위한 방법이 필요하다 **

** 이 문제의 경우 한 테스트케이스 당 O(N) 에 맞먹는 속도로 풀어내야 문제해결이 가능하다 **

** 나도 그랬지만 간혹 문제를 다 풀고 제출하니 메모리초과가 뜨는 경우가 많은데

이 경우는 스택오버플로 문제일 것이다. ==> dfs 의 깊이가 끝없이 이어진다는 소리

아마 이 예제를 넣어보면 메모리초과에 대한 문제를 해결할 수 있을 것이다.

1

3

2 3 2 **

** O(N) 으로 탐색하라는 말이 어떤식으로 흘러가야되는건지 잘 파악해보자 **

 

더보기
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
#include <iostream>
using namespace std;
#define cur 111111
 
int arr[100001];
int checking[100001];
int T, n, person, find_num;
 
bool dfs(int now, int go, int ii) {
    if (checking[now]) return false;
    checking[now] = cur + ii;
 
    if (checking[go]) {
        if (checking[go] == cur + ii) {
            find_num = go; 
            checking[now] -= cur;
            if (now == go) return false;
            return true; 
        }
        else return false;
    }
 
    if (dfs(go, arr[go], ii)) {
        checking[now] -= cur;
        if (now != find_num) return true;
        else return false;
    }
 
    return false;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> person;
            arr[i] = person;
        }
 
        for (int i = 1; i <= n; i++) {
            if (!checking[i]) {
                find_num = 0;
                if (dfs(i, arr[i], i) && i == find_num) checking[i] -= cur;
            }
        }
 
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (checking[i] > cur) cnt++;
            checking[i] = 0;
        }
 
        cout << cnt << "\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 4963번 섬의 개수  (0) 2020.01.14
BOJ 2667번 단지번호붙이기  (0) 2020.01.14
BOJ 10451번 순열 사이클  (0) 2020.01.14
BOJ 2331번 반복 수열  (0) 2020.01.14
BOJ 1707번 이분 그래프  (0) 2020.01.13

+ Recent posts

티스토리툴바