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

GitHub : https://github.com/junho0956/Algorithm/blob/master/1991/1991/%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 <iostream>
#include <vector>
using namespace std;
 
struct node {
    char my;
    char left = NULL, right = NULL;
    bool visit = false;
}node[26];
 
void pre_order(char ch) {
    if (node[ch - 'A'].visit == true) return;
    node[ch - 'A'].visit = true;
    cout << ch;
    if (node[ch - 'A'].left != NULL) pre_order(node[ch - 'A'].left);
    if (node[ch - 'A'].right != NULL) pre_order(node[ch - 'A'].right);
}
 
void in_order(char ch) {
    if (node[ch - 'A'].visit == true) return;
    node[ch - 'A'].visit = true;
 
    if (node[ch - 'A'].left != NULL) in_order(node[ch - 'A'].left);
    cout << ch;
    if (node[ch - 'A'].right != NULL) in_order(node[ch - 'A'].right);
}
 
void post_order(char ch) {
    if (node[ch - 'A'].visit == true) return;
    node[ch - 'A'].visit = true;
    
    if (node[ch - 'A'].left != NULL) post_order(node[ch - 'A'].left);
    if (node[ch - 'A'].right != NULL) post_order(node[ch - 'A'].right);
    cout << ch;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int N; cin >> N;
    char ch, chl, chr;
    for (int i = 0; i < N; i++) {
        cin >> ch >> chl >> chr;
        node[ch - 'A'].my = ch;
        if(chl != '.') node[ch - 'A'].left = chl;
        if(chr != '.') node[ch - 'A'].right = chr;
    }
 
    pre_order('A'); cout << '\n';
    for (int i = 0; i < N; i++) node[i].visit = 0;
    in_order('A'); cout << '\n';
    for (int i = 0; i < N; i++) node[i].visit = 0;
    post_order('A');
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 1967번 트리의 지름  (0) 2020.01.15
BOJ 11725번 트리의 부모 찾기  (0) 2020.01.14
BOJ 2146번 다리 만들기  (0) 2020.01.14
BOJ 2178번 미로탐색  (0) 2020.01.14
BOJ 7576번 토마토  (0) 2020.01.14

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

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

 

탐색은 역시 재밌는거 같다.

다리 만들기는 떨어진 지역(?) 간의 연결을 할 수 있는 최소 칸을 구하는 문제이다.

풀어낸 과정을 간략해보면

1) 일단 모든 지역을 재정의했다. 지역1, 지역2, 지역3, .. 이런식으로

2) 1)과정에서 주변에 바다가 있을 경우 임의의 큐에 넣어준다. (다리를 연결하기 위한 시작점이 된다)

3) 2)과정에서 만들어진 큐를 이용하여 좌표를 하나씩 꺼내어 다른 지역을 찾는다.

4) Min 이 설정이 되면 그 다음부터는 탐색간 다리가 Min과 같아지게되면 더이상 탐색할 필요가 없으니 중지시킨다.

 

이정도 과정이면 이 문제를 해결하는데 문제가 없을 것 같다.

 

더보기
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
#include <iostream>
#include <queue>
using namespace std;
 
typedef pair<pair<int, int>, int> pii;
int mx[4] = { 1,-1,0,0 };
int my[4] = { 0, 0, 1, -1 };
int N;
int arr[100][100];
int visit[100][100];
queue<pair<int,int> > q;
queue<pair<int, int> > qq;
queue<pii> qqq;
 
bool location(int y, int x) {
    for (int i = 0; i < 4; i++) {
        int yy = my[i] + y;
        int xx = mx[i] + x;
        if (yy >= 0 && yy < N && xx >= 0 && xx < N && !arr[yy][xx]) return true;
    }
    return false;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++) {
            cin >> arr[i][k];
        }
    }
 
    int land = 2;
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++) {
            if (arr[i][k] && !visit[i][k]) {
                qq.push({i,k});
                arr[i][k] = land;
                while (!qq.empty()) {
                    int y = qq.front().first;
                    int x = qq.front().second;
                    qq.pop();
 
                    if (location(y, x)) q.push({y,x});
                    for (int j = 0; j < 4; j++) {
                        int yy = my[j] + y;
                        int xx = mx[j] + x;
                        if (yy >= 0 && yy < N && xx >= 0 && xx < N && arr[yy][xx] == 1) {
                            qq.push({ yy,xx });
                            arr[yy][xx] = land;
                            visit[yy][xx] = 1;
                        }
                    }
                }
                land++;
            }
        }
    }
 
     int Min = 10000000;
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        bool check = false;
        land = arr[y][x];
        q.pop();
        qqq.push({ {y,x},0 });
        while (!qqq.empty()) {
            int yy = qqq.front().first.first;
            int xx = qqq.front().first.second;
            int cnt = qqq.front().second;
            qqq.pop();
            
            if (cnt >= Min) {
                while (!qqq.empty()) qqq.pop();
                break;
            }
 
            for (int i = 0; i < 4; i++) {
                int yyy = my[i] + yy;
                int xxx = mx[i] + xx;
                if (yyy >= 0 && yyy < N && xxx >= 0 && xxx < N) {
                    if (arr[yyy][xxx] == 0) {
                        arr[yyy][xxx] = 1;
                        qqq.push({ {yyy,xxx},cnt + 1 });
                        qq.push({ yyy,xxx });
                    }
                    else if (arr[yyy][xxx] != 1 && arr[yyy][xxx] != land) {
                        check = true;
                        Min = Min > cnt ? cnt : Min;
                        break;
                    }
                }
            }
            if (check) {
                while (!qqq.empty())qqq.pop();
            }
        }
        while (!qq.empty()) {
            int yy = qq.front().first;
            int xx = qq.front().second;
            qq.pop(); arr[yy][xx] = 0;
        }
    }
 
    if (Min == 10000000) Min = 0;
    cout << Min;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 11725번 트리의 부모 찾기  (0) 2020.01.14
BOJ 1991번 트리 순회  (0) 2020.01.14
BOJ 2178번 미로탐색  (0) 2020.01.14
BOJ 7576번 토마토  (0) 2020.01.14
BOJ 4963번 섬의 개수  (0) 2020.01.14

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

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

 

필요한 것은 현재 1 인지 0인지 확인할 배열, 현재까지 오는데 필요한 최소 횟수를 포함한 배열 2가지이다.

현재 접점에서 동서남북으로 갈 수 있는 곳을 체크하되,

만약 그곳이 방문했던 곳이라면 현재까지 오는데 필요한 횟수+1 과 방문확인하는 위치의 횟수를 비교해주는 작업으로

bfs 를 통해 탐색을 하면 된다.

 

더보기
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 <cstdio>
#include <vector>
#include <queue>
using namespace std;
#pragma warning(disable:4996)
 
queue<pair<int, int> > q;
int mx[4] = { -1,1,0,0 };
int my[4] = { 0,0,1,-1 };
int N, M;
int arr[100][100];
int check[100][100];
 
int main() {
    scanf("%d%d", &N, &M);
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < M; k++) {
            scanf("%1d", &arr[i][k]);
        }
    }
 
    check[0][0] = 1;
    q.push({ 0,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]) {
                if (check[yy][xx] == 0) {
                    q.push({ yy,xx });
                    check[yy][xx] = check[y][x] + 1;
                }
                else {
                    if (check[yy][xx] > check[y][x] + 1) {
                        q.push({ yy,xx });
                        check[yy][xx] = check[y][x] + 1;
                    }
                }
            }
        }
    }
 
    printf("%d", check[N - 1][M - 1]);
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 1991번 트리 순회  (0) 2020.01.14
BOJ 2146번 다리 만들기  (0) 2020.01.14
BOJ 7576번 토마토  (0) 2020.01.14
BOJ 4963번 섬의 개수  (0) 2020.01.14
BOJ 2667번 단지번호붙이기  (0) 2020.01.14

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

+ Recent posts

티스토리툴바