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

GitHub : https://github.com/junho0956/Algorithm/blob/master/11725/11725/%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
#include <iostream>
#include <vector>
using namespace std;
 
int arr[100001], v1, v2, N;
vector<int> v[100001];
 
void dfs(int num) {
 
    for (int i = 0; i < v[num].size(); i++) {
        if(!arr[v[num][i]]) arr[v[num][i]] = num, dfs(v[num][i]);
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        cin >> v1 >> v2;
        v[v1].push_back(v2);
        v[v2].push_back(v1);
    }
 
    dfs(1);
    for (int i = 2; i <= N; i++)
        cout << arr[i] << '\n';
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 1167번 트리의 지름  (0) 2020.01.15
BOJ 1967번 트리의 지름  (0) 2020.01.15
BOJ 1991번 트리 순회  (0) 2020.01.14
BOJ 2146번 다리 만들기  (0) 2020.01.14
BOJ 2178번 미로탐색  (0) 2020.01.14

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

+ Recent posts

티스토리툴바