2048 (Easy)



2048 게임을 하는데 5번 이동에 제일 큰 블록을 만들어야 한다.


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


블록이 어떻게 주어질지 모르니까 전략이 없다. 모든 경우를 실험해보자.


같은 상태에 도달하면 다시 할 필요가 없긴 하지만, 같은 상태를 확인하기도, 도달하기도 어렵다.


걍 백트래킹으로 조져보자.



백트래킹 함수는 다음과 같이 구성했다.


상단엔 5번 이동했는지 확인한다. 5번이면 가장 큰 블록을 찾아 답과 비교하고 종료시킨다.


5번 이하의 경우에 완전탐색을 수행해야 하는데,


이전 상태를 저장 -> 재귀호출 -> 복귀 와 같은 아주 간단한 구조로 되어있다.


아래 코드는 매우 더러우니 안 보는 것을 추천합니다..

4방향의 규칙을 다 하드코딩으로 해놓았기 때문에 가독성이 구리다.

포문으로 임시변수 가로줄에 옮기고, 합치고, 되돌려주면 되긴 하는데 시간에 쫓겨 그냥 다 해버렸다 ^오^


아이디어만 얻어가시면 되는데,

한 줄씩 블록을 합치는 것과, 진짜 블록만 스택에 넣고 다시 줄을 채우는 것으로 병합을 구현했다.


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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <stdio.h>
#include <stack>
using namespace std;
 
int n, ans;
int map[20][20];
 
void save(int tmap[][20]) {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            tmap[i][j] = map[i][j];
}
 
void restore(int tmap[][20]) {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            map[i][j] = tmap[i][j];
}
 
void backtracking(int cnt) {
    if (cnt == 5) {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (ans < map[i][j])
                    ans = map[i][j];
 
        return;
    }
 
    stack<int> st;
    int tmap[20][20];
    save(tmap);
 
    for (int i = 0; i < n; ++i) { //우
        for (int j = 0; j < n; ++j) {
            if (map[i][j]) {
                st.push(map[i][j]);
                map[i][j] = 0;
            }
        }
 
        int b = n - 1;
        while (!st.empty()) {
            int t = st.top();
            st.pop();
 
            if (!map[i][b])
                map[i][b] = t;
            else if (t == map[i][b])
                map[i][b--*= 2;
            else
                map[i][--b] = t;
        }
    }
    backtracking(cnt + 1);
    restore(tmap);
 
    for (int i = 0; i < n; ++i) { //좌
        for (int j = n - 1; j >= 0--j) {
            if (map[i][j]) {
                st.push(map[i][j]);
                map[i][j] = 0;
            }
        }
 
        int b = 0;
        while (!st.empty()) {
            int t = st.top();
            st.pop();
 
            if (!map[i][b])
                map[i][b] = t;
            else if (t == map[i][b])
                map[i][b++*= 2;
            else
                map[i][++b] = t;
        }
    }
    backtracking(cnt + 1);
    restore(tmap);
 
    for (int j = 0; j < n; ++j) { //위
        for (int i = 0; i < n; ++i) {
            if (map[i][j]) {
                st.push(map[i][j]);
                map[i][j] = 0;
            }
        }
 
        int b = n - 1;
        while (!st.empty()) {
            int t = st.top();
            st.pop();
 
            if (!map[b][j])
                map[b][j] = t;
            else if (t == map[b][j])
                map[b--][j] *= 2;
            else
                map[--b][j] = t;
        }
    }
    backtracking(cnt + 1);
    restore(tmap);
 
    for (int j = 0; j < n; ++j) { //아래
        for (int i = n - 1; i >= 0--i) {
            if (map[i][j]) {
                st.push(map[i][j]);
                map[i][j] = 0;
            }
        }
 
        int b = 0;
        while (!st.empty()) {
            int t = st.top();
            st.pop();
 
            if (!map[b][j])
                map[b][j] = t;
            else if (t == map[b][j])
                map[b++][j] *= 2;
            else
                map[++b][j] = t;
        }
    }
    backtracking(cnt + 1);
    restore(tmap);
}
 
int main() {
    scanf("%d"&n);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            scanf("%d"&map[i][j]);
 
    backtracking(0);
    printf("%d", ans);
 
    return 0;
}
cs


구슬 탈출 2 


보드에 빨간 공과 파란 공을 올려 두고, 보드를 4방향으로 기울여보면서 빨간 공을 보드의 구멍으로 탈출시키는게 목표다.

이 때 가장 적게 기울여보는 횟수는 얼마나 될까?


맵이 어떻게 주어질지 모르기 때문에 다 해보는 완전탐색이 필요하다. 동시에 최소 횟수를 요구하므로 bfs가 적당하다.

참고로 진짜 모든 경우를 탐색해보는 방법으로도 통과가 가능하긴 하다. 시간이 더 걸리긴 하지만..


공이 두 개씩 굴러다니므로 visit 확인을 두 공의 좌표를 모두 확인해야 한다는 점을 유의해야 한다.

규칙이 조금 까다로운데, 분기를 다음과 같이 할 수 있다.

1. 일단 상대 공을 무시하고 두 공을 굴려서 어디로 가는지 확인한다.

2. 만약 파란 공이 구멍에 빠지면 이 경우는 글러먹은 경우니까 버린다.

3. 두 공이 겹칠 경우도 있다. 이 때는 굴리기 전의 좌표를 보고 잘 조정해줘야 한다. 아래로 굴렸고 겹쳤는데, 원래 빨간공이 위에 있었다면 빨간공을 파란공 위로 옮겨 줘야한다.

친절하게도 10을 초과하는 답은 원하지 않는다니까 4 ^ 10 안에 수행가능하다. 물론 한 번 굴리고, 다음번에 또 같은 방향으로 굴리는 경우 visit확인을 통해 가지치기가 되니까 훨씬 빠르게 문제가 풀린다.

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
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
 
struct balls {
    int depth;
    int rx, ry, bx, by;
};
int irx, iry, ibx, iby, hx, hy;
 
int n, m, ans = -1;
int map[10][10];
int dir[4][2= { {1,0},{0,1},{-1,0},{0,-1} };
bool visit[10][10][10][10];
char str[11];
 
void move(int& x, int& y, int d) {
    while (1) {
        x += dir[d][0]; y += dir[d][1];
        if (map[x][y] == 1) {
            x -= dir[d][0]; y -= dir[d][1];
            break;
        }
        else if (map[x][y] == 2)
            break;
    }
}
 
int main() {
    scanf("%d %d"&n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", str);
        for (int j = 0; j < m; ++j) {
            switch (str[j]) {
            case '.':
                map[i][j] = 0break;
            case '#':
                map[i][j] = 1break;
            case 'O':
                map[i][j] = 2; hx = i, hy = j; break;
            case 'R':
                irx = i, iry = j; break;
            case 'B':
                ibx = i, iby = j; break;
            }
        }
    }
 
    queue<balls> q;
    q.push({ 0,irx,iry,ibx,iby });
    visit[irx][iry][ibx][iby] = true;
 
    while (!q.empty()) {
        balls cur = q.front(); q.pop();
 
        if (cur.depth > 10)
            break;
        if (cur.rx == hx && cur.ry == hy) {
            ans = cur.depth;
            break;
        }
 
        for (int i = 0; i < 4++i) {
            int rx = cur.rx, ry = cur.ry;
            int bx = cur.bx, by = cur.by;
            move(rx, ry, i), move(bx, by, i);
 
            if (bx == hx && by == hy)
                continue;
 
            if (rx == bx && ry == by) {
                switch (i) {
                case 0:
                    cur.rx < cur.bx ? rx-- : bx--break;
                case 2:
                    cur.rx < cur.bx ? bx++ : rx++break;
                case 1:
                    cur.ry < cur.by ? ry-- : by--break;
                case 3:
                    cur.ry < cur.by ? by++ : ry++break;
                }
            }
 
            if (!visit[rx][ry][bx][by]) {
                balls next = { cur.depth + 1,rx,ry,bx,by };
                q.push(next);
                visit[rx][ry][bx][by] = true;
            }
        }
    }
 
    printf("%d", ans);
 
    return 0;
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 12100 2048 (Easy)  (0) 2018.04.11
백준) 14868 문명 - bfs, 유니온 파인드  (1) 2018.02.08
백준) 2615 오목  (0) 2018.02.06
백준) 1182 부분집합의 합  (0) 2018.02.06
백준) 4963 섬의 개수  (0) 2018.01.14

문명 


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



제대로 푼건지 모르겠다. 주변에 잘하시는 분들을 보면 다 유니온 파인드를 최적화하셨던데,


쌩 유니온 파인드로 제출했더니 맞긴했다.


나중에 재채점되면 틀릴 것 같지만, 일단 풀이를 공유하고자 한다.




맵에 k개의 문명 발상지가 있고, 매 턴마다 문명들은 사방향으로 진출하고, 경계선이 맞닿는다면(사방향) 해당 문명을 흡수한다.


이렇게 턴들이 진행될 때, 몇번째 턴에 모든 문명이 하나로 통일될 것인지 계산해야 한다.


예외적으로, 처음부터 k개의 발상지들이 모두 붙어있었다면, 바로 하나로 통일되고 답은 0이다.



사방향과 최소턴이라는 키워드로 일단 bfs를 쓰기로 했다.


탈출조건은, 문명이 줄고 줄어서 하나로 통일될 때 인데, 이를 구분하기 위해 유니온-파인드를 썼다.


맞닿는 경우에, 두 문명의 부모를 찾고, 다르다면 유니온하면서 문명 카운트를 하나 줄이는 것이다.


만약 카운트가 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
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
#include <stdio.h>
#include <queue>
using namespace std;
 
int map[2000][2000];
int dir[4][2= { { 10 }, { 01 }, { -10 }, { 0-1 } };
int n, k, a, b;
 
struct civil{
    int num;
    int y, x;
};
queue<civil> init, q;
 
int p[100001];
 
int find(int x){
    if (x == p[x])
        return x;
    else
        return p[x] = find(p[x]);
}
void unite(int x, int y){
    x = find(x);
    y = find(y);
 
    if (x != y)
        p[x] = y;
}
 
int main(){
    scanf("%d %d"&n, &k);
 
    for (int i = 1; i <= k; ++i){
        scanf("%d %d"&a, &b);
        init.push({ i, b - 1, a - 1 });
        p[i] = i;
 
        map[b - 1][a - 1= i;
    }
 
    while (!init.empty()){
        civil tmp = init.front();
        init.pop();
 
        for (int i = 0; i < 4++i){
            int yy = tmp.y + dir[i][0];
            int xx = tmp.x + dir[i][1];
 
            if (yy < 0 || xx < 0 || yy >= n || xx >= n)
                continue;
 
            if (map[yy][xx] != 0){
                if (find(tmp.num) != find(map[yy][xx])){
                    unite(tmp.num, map[yy][xx]);
                    map[yy][xx] = tmp.num;
                    k--;
                }
            }
        }
        q.push({ map[tmp.y][tmp.x], tmp.y, tmp.x });
    }
 
    if (k == 1){
        printf("0");
        return 0;
    }
 
    int ans = 0;
    while (!q.empty()){
        ans++;
        int s = q.size();
        for (int i = 0; i < s; ++i){
            civil tmp = q.front();
            q.pop();
 
            for (int i = 0; i < 4++i){
                int yy = tmp.y + dir[i][0];
                int xx = tmp.x + dir[i][1];
 
                if (yy < 0 || xx < 0 || yy >= n || xx >= n)
                    continue;
 
                if (map[yy][xx] != 0)
                    continue;
 
                map[yy][xx] = tmp.num;
                for (int j = 0; j < 4++j){
                    int yyy = yy + dir[j][0];
                    int xxx = xx + dir[j][1];
 
                    if (yyy < 0 || xxx < 0 || yyy >= n || xxx >= n)
                        continue;
 
                    if (map[yyy][xxx] != 0 && find(map[yyy][xxx]) != find(tmp.num)){
                        unite(tmp.num, map[yyy][xxx]);
                        k--;
 
                        if (k == 1){
                            printf("%d", ans);
                            return 0;
                        }
                    }
                }
                q.push({ tmp.num, yy, xx });
            }
        }
    }
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 12100 2048 (Easy)  (0) 2018.04.11
백준) 13460 구슬 탈출 2 // 구 째로탈출2  (0) 2018.04.11
백준) 2615 오목  (0) 2018.02.06
백준) 1182 부분집합의 합  (0) 2018.02.06
백준) 4963 섬의 개수  (0) 2018.01.14

오목


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



오목판이 주어지고 현재 누가 이겼는지를 판별해야한다.


모든 알을 보고 최대한 빨리 판별해보자.



오목에서 승리란 알을 연속으로 5개 두어야 생긴다. 방향은 가로, 세로, 대각선이 가능하다.


왼쪽 위부터 오른쪽으로, 아래로 모든 알을 본다면, 네 가지 방향으로 연속적인지만 판별하면 된다.


1. 아래 2. 오른쪽 3. 우하 대각선 4.우상 대각선



6개 두면 이긴게 아니기 때문에, 기존에 6개를 카운트 한 것을 방향 때문에 5개로 착각할 수 있다.


따라서 5개로 착각하지 않게 하기 위해, 정반대 방향의 돌을 하나 봐서, 현재 보는 돌이 시작점인지 확인할 수 있다.


visit으로 체크하는 방법은, 오목이 돌이 여러 방향들에 걸쳐진다는 점에서 쓸 수 없다.



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
#include <stdio.h>
 
int map[19][19];
int dir[4][2= { {1,0},{1,1},{0,1},{-1,1} };
 
bool is_in_range(int y, int x) {
    return (y >= 0 && x >= 0 && y < 19 && x < 19);
}
 
int getMap(int y, int x) {
    if (y < 0 || x < 0 || y >= 19 || x >= 19)
        return 0;
    return map[y][x];
}
 
int main() {
    for (int i = 0; i < 19++i)
        for (int j = 0; j < 19++j)
            scanf("%d"&map[i][j]);
 
    int ans_y = -1, ans_x = -1, ans_c = -1;
 
    for (int d = 0; d < 4++d) {
        for (int x = 0; x < 19++x) {
            for (int y = 0; y < 19++y) {
                if (map[y][x] == 0)
                    continue;
 
                if (getMap(y - dir[d][0], x - dir[d][1]) == map[y][x])
                    continue;
 
                int yy = y, xx = x, cnt = 0;
                while (1) {
                    yy += dir[d][0];
                    xx += dir[d][1];
 
                    if (!is_in_range(yy, xx))
                        break;
 
                    if (map[yy][xx] != map[y][x])
                        break;
 
                    cnt++;
                }
                if (cnt == 4) {
                    ans_y = y;
                    ans_x = x;
                    ans_c = map[y][x];
                }
            }
        }
    }
 
    if (ans_c == -1) {
        printf("0");
        return 0;
    }
 
    printf("%d\n%d %d", ans_c, ans_y + 1, ans_x + 1);
    return 0;
}
cs


부분집합의 합 





각 원소들을 넣던지, 빼던지 해서 2가지 경우씩 발생한다. 따라서 모든 원소와 관련해 부분집합은 2^n개 생긴다.

원소가 최대 20개 이므로 브루트포스로 백만번의 연산으로 답을 얻을 수 있다.

하지만 분명 쓸따리 없는 연산도 존재한다.


가령 예를 들어 {0, 1, 2, 3, 4, 5}의 집합에서, S=6을 만드는 부분집합을 찾기위해, 첫 원소부터 넣을 것인지를 고려하다가,

{0, 1, 2, 3}까지 더해서 이미 6을 만들었는데, 나머지 {4, 5}를 넣을지 뺄지 고민할 필요가 없는 것이다.


하지만 이러한 가지치기(prunning)는 뒤의 수가 앞의 수보다 크다는 가정하에 진행되므로, 배열의 정렬이 필요하다.

정렬 이후엔 재귀안에 가지치는 코드를 넣어주자.


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
#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n[20], N, S, ans;
 
void dfs(int cur_sum, int cnt, int idx) {
    if (idx >= N)
        return;
 
    if (cur_sum + n[idx] > S) {
        if (n[idx] >= 0)
            return;
    }
 
    if (cur_sum + n[idx] == S)
        ans++;
 
    dfs(cur_sum + n[idx], cnt + 1, idx + 1);
    dfs(cur_sum, cnt, idx + 1);
}
 
int main() {
    scanf("%d %d"&N, &S);
    for (int i = 0; i < N; ++i)
        scanf("%d"&n[i]);
 
    sort(n, n + N);
    dfs(000);
 
    printf("%d", ans);
 
    return 0;
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 14868 문명 - bfs, 유니온 파인드  (1) 2018.02.08
백준) 2615 오목  (0) 2018.02.06
백준) 4963 섬의 개수  (0) 2018.01.14
백준) 1012 유기농 배추  (0) 2018.01.14
백준) 2206 벽 부수고 이동하기  (0) 2018.01.14

섬의 개수






유기농 배추(http://js1jj2sk3.tistory.com/71?category=725176)와 같은문제.

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
#include <stdio.h>
 
int map[50][50], w, h;
int dir[8][2= { {1,1},{1,0},{1,-1},{0,1},{0,-1},{-1,1},{-1,0},{-1,-1} };
 
void dfs(int x, int y) {
    map[x][y] = 0;
 
    for (int i = 0; i < 8++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
 
        if (xx < 0 || yy < 0 || xx >= h || yy >= w)
            continue;
 
        if (map[xx][yy] == 1)
            dfs(xx, yy);
    }
}
 
int main() {
    while (1) {
        scanf("%d %d"&w, &h);
        if (w == 0 && h == 0)
            return 0;
 
        for (int i = 0; i < h; ++i)
            for (int j = 0; j < w; ++j)
                scanf("%d"&map[i][j]);
 
        int cnt = 0;
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                if (map[i][j] == 1) {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
 
        printf("%d\n", cnt);
    }
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 2615 오목  (0) 2018.02.06
백준) 1182 부분집합의 합  (0) 2018.02.06
백준) 1012 유기농 배추  (0) 2018.01.14
백준) 2206 벽 부수고 이동하기  (0) 2018.01.14
백준) 3055 탈출  (3) 2018.01.14

유기농 배추




DFS의 기본적인 버전이다.

재귀적으로 돌아가는 과정만 이해하면 DFS만큼 편한게 없다.

코드는 다음과 같다.

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
#include <stdio.h>
 
int t;
int m, n, k;
int x, y;
int ans;
 
int map[50][50];
int dir[4][2= { {-1,0},{1,0},{0,-1},{0,1} };
 
void dfs(int x, int y) {
    map[x][y] = 0;
 
    for (int i = 0; i < 4++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
 
        if (xx < 0 || yy < 0 || xx >= n || yy >= m)
            continue;
 
        if (map[xx][yy] != 1)
            continue;
 
        dfs(xx, yy);
    }
}
 
int main() {
    scanf("%d"&t);
 
    while (t--) {
        scanf("%d %d %d"&m, &n, &k);
 
        ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                map[i][j] = 0;
 
        for (int i = 0; i < k; ++i) {
            scanf("%d %d"&x, &y);
            map[y][x] = 1;
        }
 
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (map[i][j] == 1) {
                    ans++;
                    dfs(i, j);
                }
            }
        }
            
 
        printf("%d\n", ans);
    }
 
    return 0;
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 1182 부분집합의 합  (0) 2018.02.06
백준) 4963 섬의 개수  (0) 2018.01.14
백준) 2206 벽 부수고 이동하기  (0) 2018.01.14
백준) 3055 탈출  (3) 2018.01.14
백준) 10216 Count Circle Groups  (0) 2017.10.09

벽 부수고 이동하기




지도가 제공되고 최단 경로의 길이를 구하는 문제다.

벽을 한 개는 부술 수 있다는 추가 조건이 있긴 하지만, 최단 경로 문제니까 BFS로 풀어보자.


BFS는 완전탐색 알고리즘이므로, 잘만 하면 벽을 전부 하나씩 부수고 탐색하는 케이스들도 전부 탐색할 수 있다.

평행세계를 생각해보면 좋은데, 여기서 벽을 부술지 돌아갈지를 두 차원으로 나눠서 생각하는 것이다.

그러면 부순 세계와 돌아간 세계는 독립되고 서로 영향을 주지 않는다.


이를 구현하기 위해, BFS에서 주로 쓰는 VISIT배열을 삼차원으로 만든다.

즉, 이차원 배열이 두 개 쌓인 것이다. 기본적으론 벽을 부수지 않은 세계에서 출발하며,

벽을 만날 시에 벽을 부수고 다른 세계로 넘어가는 경우와, 벽을 돌아서 가는 경우를 모두 큐에 넣으면 된다.

이 후의 탐색은 개별적으로 진행된다.


코드로 옮기면 다음과 같다.


STL을 쓰지 않아 코드가 매우 길다.


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
#include <stdio.h>
 
typedef struct col {
    int x, y, z;
};
col que[2000000];
int que_front, que_back;
#define que_size 2000000
void que_push(int x, int y, int z) {
    que[que_back] = { x,y,z };
    que_back = (que_back + 1) % que_size;
}
col que_pop() {
    col tmp = que[que_front];
    que_front = (que_front + 1) % que_size;
 
    return tmp;
}
int abs(int x) {
    return x > 0 ? x : -x;
}
 
int n, m;
char buf[1001];
int map[1000][1000];
int visit[1000][1000][2];
int dir[4][2= { { 1,0 },{ 0,1 },{ -1,0 },{ 0,-1 } };
 
void bfs(int x, int y, int z) {
    que_push(x, y, z);
    visit[x][y][0= 1;
 
    int cnt = 2;
    while (que_front != que_back) {
 
        int size = abs(que_front - que_back);
        while (size--) {
            col tmp = que_pop();
 
            for (int i = 0; i < 4++i) {
                int xx = tmp.x + dir[i][0];
                int yy = tmp.y + dir[i][1];
                int zz = tmp.z;
 
                if (xx < 0 || yy < 0 || xx >= n || yy >= m)
                    continue;
 
                if (visit[xx][yy][zz])
                    continue;
 
                if (map[xx][yy] == 0) {
                    que_push(xx, yy, zz);
                    visit[xx][yy][zz] = cnt;
                }
 
                if (map[xx][yy] == 1) {
                    if (zz == 1)
                        continue;
                    else {
                        que_push(xx, yy, 1);
                        visit[xx][yy][1= cnt;
                    }
                }
            }
        }
        cnt++;
    }
}
 
int main() {
    scanf("%d %d"&n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", buf);
        for (int j = 0; j < m; ++j)
            map[i][j] = buf[j] - '0';
    }
 
    bfs(000);
 
    int ans1 = visit[n - 1][m - 1][0];
    int ans2 = visit[n - 1][m - 1][1];
 
    if (ans1 == 0 && ans2 == 0)
        printf("-1");
    else if (ans1 == 0)
        printf("%d", ans2);
    else if (ans2 == 0)
        printf("%d", ans1);
    else
        printf("%d", ans1 < ans2 ? ans1 : ans2);
 
    return 0;
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 4963 섬의 개수  (0) 2018.01.14
백준) 1012 유기농 배추  (0) 2018.01.14
백준) 3055 탈출  (3) 2018.01.14
백준) 10216 Count Circle Groups  (0) 2017.10.09
백준) 2606 바이러스  (0) 2017.10.09

탈출




물이 인접한 칸으로 계속 불어날 때, 고슴도치가 물에 닿지 않고 목표지점까지 갈 수 있는지,

간다면 최단거리는 몇인지 알아내야 한다.


그래프 탐색문제이며, 최단거리를 알아내야 하므로 BFS를 써보기로 했다.

물과 고슴도치를 모두 큐에 넣고 BFS를 돌려버릴 수 있겠다.

하지만 둘 다 같은 시간에 같은 칸에 도착한다면 물이 이기는 경우를 처리할 수 없다.(내 생각에는)


그래서 물은 고슴도치의 이동에 전혀 영향을 받지 않으므로,

물만 BFS를 먼저 돌려서 언제 어디까지 불어나는지를 먼저 확인하자.

이 후 고슴도치는 물이 어떻게 불어나는지 저장된 지도를 보고 도착지점까지 BFS로 도착하면 된다.


코드로 옮기면 다음과 같다.

요새 STL을 쓰지 않는 연습을 하고 있는지라, 코드가 매우 길다.


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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <stdio.h>
 
typedef struct col {
    int x, y;
}col;
 
col que[10000];
int que_front, que_back;
#define que_size 10000
void que_push(int x, int y) {
    que[que_back] = { x,y };
    que_back = (que_back + 1) % que_size;
}
col que_pop() {
    col tmp = que[que_front];
    que_front = (que_front + 1) % que_size;
 
    return tmp;
}
 
char buf[51];
int r, c;
int map[50][50];
int waters_cnt;
col waters[2500];
col start, dst;
 
int dir[4][2= { { 1,0 },{ 0,1 },{ -1,0 },{ 0,-1 } };
int abs(int x) {
    return x > 0 ? x : -x;
}
 
void water_bfs() {
    int cnt = 2;
 
    while (que_front != que_back) {
        int size = abs(que_back - que_front);
 
        while (size--) {
            col tmp = que_pop();
 
            for (int i = 0; i < 4++i) {
                int xx = tmp.x + dir[i][0];
                int yy = tmp.y + dir[i][1];
 
                if (xx < 0 || yy < 0 || xx >= r || yy >= c)
                    continue;
 
                if (map[xx][yy] != 0)
                    continue;
 
                que_push(xx, yy);
                map[xx][yy] = cnt;
            }
        }
        cnt++;
    }
}
 
int beaber_bfs() {
    int cnt = 2;
 
    while (que_front != que_back) {
        int size = abs(que_front - que_back);
 
        while (size--) {
            col tmp = que_pop();
 
            for (int i = 0; i < 4++i) {
                int xx = tmp.x + dir[i][0];
                int yy = tmp.y + dir[i][1];
 
                if (xx < 0 || yy < 0 || xx >= r || yy >= c)
                    continue;
 
                if (xx == dst.x && yy == dst.y)
                    return cnt;
 
                if (map[xx][yy] == 0) {
                    que_push(xx, yy);
                    map[xx][yy] = -1;
                    continue;
                }
 
                if (map[xx][yy] == -1)
                    continue;
 
                if (map[xx][yy] <= cnt)
                    continue;
 
                que_push(xx, yy);
                map[xx][yy] = -1;
            }
        }
 
        cnt++;
    }
    return -1;
}
 
int main() {
    scanf("%d %d"&r, &c);
 
    for (int i = 0; i < r; ++i) {
        scanf("%s", buf);
        for (int j = 0; j < c; ++j) {
            if (buf[j] == '.'// 길
                continue;
            else if (buf[j] == 'D') { // 비버굴
                dst = { i,j };
                map[i][j] = -1;
            }
            else if (buf[j] == 'S') { // 고슴도치
                start = { i,j };
            }
            else if (buf[j] == 'X'// 돌
                map[i][j] = -1;
            else { // 물 
                waters[waters_cnt++= { i,j };
                map[i][j] = 1;
            }
        }
    }
 
    //물이 번지는 시간 기록
    for (int i = 0; i < waters_cnt; ++i)
        que_push(waters[i].x, waters[i].y);
    water_bfs();
 
 
    map[start.x][start.y] = -1;
    que_push(start.x, start.y);
    
    int ans = beaber_bfs();
    if (ans == -1)
        printf("KAKTUS");
    else
        printf("%d\n", ans - 1);
 
    return 0;
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 1012 유기농 배추  (0) 2018.01.14
백준) 2206 벽 부수고 이동하기  (0) 2018.01.14
백준) 10216 Count Circle Groups  (0) 2017.10.09
백준) 2606 바이러스  (0) 2017.10.09
백준) 2178 미로 탐색  (3) 2017.10.09

Count Circle Groups

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






1. 접근


캠프들 끼리는 통신영역에 따라 한 그룹이 될 수도 안될 수도 있다.


그래프에서 총 그룹은 몇개나 나올까?


그래프는 n^2 에 만들 수 있을 것이다. 서로서로 비교해가면서 간선을 만들어준다.


그러고 나면 그래프에서 그룹이 총 몇개 있는지 찾는 법은 디스조인트-셋 이나 BFS / DFS 로 조질 수 있다.



2-1) 풀이 1


그래프에 대해 DFS로 그룹이 몇 개 있는지 셀 수 있을 것이다. 


visit을 확인해가면서 모든 캠프에 대해 DFS()를 호출해버린다.


간선이 N^2 개니까, 따라서 모든 캠프 N * DFS의 시간복잡도 (N + N^2) -> N^3 이나 걸린다.



2-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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <vector>
using namespace std;
 
int t, n;
int camp[3000][3];
int visit[3000];
vector<vector<int>> map;
 
int dfs(int x) {
    int cnt = 1;
    visit[x] = 1;
 
    for (auto a : map[x]) {
        if (visit[a])
            continue;
        cnt += dfs(a);
    }
    return cnt;
}
 
int main() {
    scanf("%d"&t);
    while (t--) {
        map.clear();
        memset(visit, 0sizeof(visit));
 
        scanf("%d"&n);
        map.resize(n);
 
        for (int i = 0; i < n; ++i)
            scanf("%d %d %d"&camp[i][0], &camp[i][1], &camp[i][2]);
 
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int x = camp[i][0- camp[j][0];
                int y = camp[i][1- camp[j][1];
                double r = (double)camp[i][2+ (double)camp[j][2];
                double d = sqrt(x*+ y*y);
 
                if (d <= r) {
                    map[i].push_back(j);
                    map[j].push_back(i);
                }
            }
        }
 
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (visit[i])
                continue;
 
            cnt++;
            for (auto v : map[i])
                dfs(v);
        }
 
        printf("%d\n", cnt);
    }
    return 0;
}
cs



3-1) 풀이 2


사실 집합이 몇개나 생기는지 세기만 하면 된다. 집합에 몇개나 들어있는지 알 필요가 없다


그러면 각 노드에 대해 그래프를 만들면서 동시에 두 노드간 부모가 다르면(find) 집합을 만들어 버릴 수 있다.(merge)


처음의 각 노드가 하나의 집합이었다면, merge를 할 수록 집합 갯수는 줄어든다.



디스조인트 셋은 선형시간에 연산하므로 이 방법은 N^2 이다.



3-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
47
48
49
50
51
52
53
54
55
#include <stdio.h>
#include <math.h>
using namespace std;
 
int t, n;
int camp[3000][3];
int parent[3000];
 
int find(int x) {
    if (x == parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}
 
void merge(int x, int y) {
    x = find(x);
    y = find(y);
 
    if (x == y)
        return;
    else
        parent[x] = y;
}
 
int main() {
    scanf("%d"&t);
    while (t--) {
        scanf("%d"&n);
        for (int i = 0; i < n; ++i) {
            scanf("%d %d %d"&camp[i][0], &camp[i][1], &camp[i][2]);
            parent[i] = i;
        }
            
        int cnt = n;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int x = camp[i][0- camp[j][0];
                int y = camp[i][1- camp[j][1];
                int r = camp[i][2+ camp[j][2];
                int d = x*+ y*y;
 
                if (d <= r * r) {
                    if (find(i) != find(j)) {
                        merge(i, j);
                        cnt--;
                    }
                }
            }
        }
 
        printf("%d\n", cnt);
    }
    return 0;
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 2206 벽 부수고 이동하기  (0) 2018.01.14
백준) 3055 탈출  (3) 2018.01.14
백준) 2606 바이러스  (0) 2017.10.09
백준) 2178 미로 탐색  (3) 2017.10.09
백준) 7569 토마토  (3) 2017.09.28

+ Recent posts