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


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

백준) 13460 구슬 탈출 2 // 구 째로탈출2  (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

구슬 탈출 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] = 0; break;
            case '#':
                map[i][j] = 1; break;
            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

현실에선 사칙연산과 괄호가 포함된 수식을 중위 표기법으로 기술한다.


예를들어 3 + 4 와 같은 꼴이다.



하지만 3 + ( 4 - 7 ) * 8 + 3 * 4 와 같이 우선순위가 꼬여버린 수식은 컴퓨터가 알아먹기 힘들다.


하지만 수식계산은 연산 순서만 잘 정리되면 술술 풀린다.


목표는 숫자(피연산자)는 가만히 냅두고, 연산자들의 서열만 정리시켜주려는 것이다.


위 수식의 연산순서를 그래프로 나타내면 다음과 같다.



위 그래프를 중위순회하면 원래의 수식이 나온다. 위 그래프를 후위순회하면 후위표기법대로 기술된다.


3 4 7 - 8 * + 3 4 * +


우리가 보기엔 해괴한 수식이지만, 컴퓨터가 보기엔 앞에서 부터 계산만 하면 되는 편한 식이다.(괄호가 없다)


어떻게 계산 하냐면, 앞에서부터 보면서 연산자가 나오면 앞의 두 피연산자를 뽑아 연산하는 것이다. 다음과 같다.


1. - 때문에 4와 7을 뺀 -3을 기록한다.


2. * 때문에 (1)의 -3과 8을 곱한 -24를 기록한다.


3. + 때문에 (2)의 -24와 3을 더한 -21을 기록한다.


4. * 때문에 3과 4를 곱한 12를 기록한다.


5. + 때문에 (3)과 (4)의 -21과 12를 더한 -9를 기록한다.


6. 최종기록 -9가 결과다.


따라서 계산하는데 O(n) 걸린다.



따라서 중위식을 후위식으로 변환하는데 O(n)만 걸리면 아름다운 알고리즘이 될 것이다.


이제부터 중위식을 후위식으로 변환하는 과정을 설명하고자 한다.


하려는 짓은 결국엔 연산순서를 잘 일렬로 세워주는 것이다. 숫자는 앞에서 부터 잘 기억만 하면 된다.



아이디어는 다음의 생각들을 잘 섞으면 된다.


1. +와 -는 당연히 *와 /보다 나중에 계산해야 한다.


2. (는 수식안에 새로운 수식이 생기게 한다.


3. )는 그 새로운 수식을 닫는 역할을 한다.


4. 따라서 곱하기 > 더하기 > 괄호질로 연산 우선순위가 높다. ( 다음을 생각해보자. (1+2)*3 ) 



이제 이 아이디어로 중위식을 앞에서부터 보면서 후위식으로 바꿔보자


1. 현재 문자가 ( 라면 스택에 ( 를 넣어준다. 새로운 수식이 언제 시작되었는지 기억하기 위함이다.


2. 현재 문자가 ) 라면 수식이 끝난 것이다. 스택에 ( 가 보일 때 까지 파내면서 후위식에 기록한다. ( 는 버린다.


괄호질은 서열이 제일 낮기때문이다.


3. 현재 문자가 연산자라면, 서열을 정해야 한다. 스택에 나보다 쎈 연산자가 있다면 파내고 후위식에 기록한다.


나와 우선순위가 같은 연산자라면, 수식의 왼쪽이 우선순위가 더 높으므로 사실 나보다 쎈 연산자다. 파내고 기록해야한다.


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
#include "calc.h"
#include <stack>
using namespace std;
 
int order[256];
char post[202];
 
int stoi(char* from, char* to) {
    int ans = 0;
    int t = 1;
    while (1) {
        ans += (*to - '0') * t;
        t *= 10;
 
        if (from == to)
            break;
        else
            to--;
    }
    return ans;
}
 
int calc(char str[])
{
    order['('] = order[')'] = 0;
    order['+'] = order['-'] = 1;
    order['*'] = order['/'] = 2;
 
    char* infix = str;
    char* postfix = post;
 
    stack<char> st;
    while (*infix) {
        if (*infix == '(') {
            st.push('(');
            infix++;
        }
        else if (*infix == ')') {
            while (st.top() != '(') {
                *postfix++ = st.top();
                *postfix++ = ' ';
                st.pop();
            }
            st.pop();
            infix++;
        }
        else if (*infix == '+' || *infix == '-' || *infix == '*' || *infix == '/') {
            while (!st.empty() && order[*infix] <= order[st.top()]) {
                *postfix++ = st.top();
                *postfix++ = ' ';
                st.pop();
            }
            st.push(*infix++);
        }
        else if ('0' <= *infix && *infix <= '9') {
            do {
                *postfix++ = *infix++;
            } while ('0' <= *infix && *infix <= '9');
            *postfix++ = ' ';
        }
    }
 
    while (!st.empty()) {
        *postfix++ = st.top();
        *postfix++ = ' ';
        st.pop();
    }
    --postfix;
    *postfix = '\0';
    //중위표기법 -> 후위표기법
 
    stack<int> ans;
    postfix = post;
    char* from = post;
    char* to = post;
    bool started = false;
 
    while (*postfix) {
        if (*postfix == '+') {
            int a = ans.top(); ans.pop();
            int b = ans.top(); ans.pop();
            ans.push(a + b);
            started = false;
        }
        else if (*postfix == '-') {
            int a = ans.top(); ans.pop();
            int b = ans.top(); ans.pop();
            ans.push(b - a);
            started = false;
        }
        else if (*postfix == '*') {
            int a = ans.top(); ans.pop();
            int b = ans.top(); ans.pop();
            ans.push(a * b);
            started = false;
        }
        else if (*postfix == ' ') {
            if (started) {
                ans.push(stoi(from, to));
                started = false;
            }
        }
        else {
            if (!started) {
                from = to = postfix;
                started = true;
            }
            else
                to = postfix;
        }
        postfix++;
    }
    //후위표기법 계산
 
    return ans.top();
}
cs


calc 함수는 문자열을 받아 계산결과를 리턴해준다.

'알고리즘 > 미분류' 카테고리의 다른 글

백준) 2512 예산  (0) 2018.07.19
백준) 11003 최소값 찾기  (0) 2018.07.13
백준) 2257 화학식량  (0) 2018.01.31
백준) 2841 외계인의 기타 연주  (0) 2018.01.22
백준) 3986 좋은 단어  (0) 2018.01.22

최종 순위




기존 위상이 주어지고, 노드끼리의 위상을 뒤바꿨을 때, 새롭게 위상들이 잘 정렬되는지 확인해야 하는 문제다.

따라서 그래프를 잘 정의해서 위상이 뒤바뀜을 잘 데이터로 표현해야 한다.


위상이 뒤바뀌면 그래프에선 무슨 일이 생길까?

주의할 점은 두 노드끼리의 위상순서만 바꾸는 것이지, 다른 노드들와의 위상순서는 그대로야 한다는 점이다.


첫번째 테스트 케이스를 보면 위상순서는 5 < 4 < 3 < 2 < 1 이다.

이후 2와 4 // 3과 4의 위상순서를 바꾸라고 한다.

기존의 위상비교는 2 > 4 // 3 > 4 였으니, 2 < 4 // 3 < 4로 바꿔야 한다.

이 때 기존의 위상비교, 예를 들어 5 < 4 나 3 < 1 같은 순서는 바뀌면 안되는 것이다.


그래프에선 간선만 휘까닥 뒤집어주면 된다. 애초에 a->b로 진출하는 간선이었다면,

이는 명확히 위상순서가 a<b임을 나타내고 있다.

따라서 간선만 a<-b로 바꿔주면 기존의 위상순서를 지키면서 바꿔줄 수 있다.


이제 그래프를 무엇으로 표현할지 생각해보자.

인접리스트로 표현한 그래프라면 뒤집어야 할 해당간선을 찾는데 해당 리스트를 전부 뒤져야 한다.

하지만 위상정렬을 위한 큐질에서, 진출간선을 찾는 것은 그냥 리스트 전부를 보면 되는데 간편함이 있다.


반면 인접행렬로 표현한 그래프라면 뒤집어야 할 해당간선을 바로 찾을 수 있음에 이점이 있다.

하지만 위상정렬을 위한 큐질에서, 진출간선을 찾는 것은 해당 행을 전부 봐야하는데 단점이 있다.


큐질에서 어차피 둘 다 O(n)이므로 인접행렬로 하자.

주의할 점은 기존 순위로 간선을 만들 때에, 5->4->3->2->1로 간선 4개만 만드는게 아니라,

5->4, 5->3, 5->2, 5->1
4->3, 4->2, 4->1
3->2, 3->1,
2->1

모든 간선을 만들어줘야 한다는 점이다. 이래야 나중에 간선을 뒤집을 때에 기존 위상순서를 유지할 수 있다.


정답은 세 가지로 분류되는데, 확실한 순위가 정해지든지(1), 순위가 안정해지든지(2), 데이터에 일관성이 없든지(3) 세 가지다.

(1)은 위상정렬이 완료되면 당연한 결과다.

(2)는 테크트리가 완료되는 노드가 동시에 2개 이상 생긴다는 뜻으로, 큐에 2개 이상의 노드가 들어가는 결과다.

(3)은 사이클이 생긴다는 의미로, 위상정렬 완료뒤에도 정렬되지 않은 노드가 남아있는 결과다.

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;
 
int tc, n, m, a, b;
int mat[501][501], order[501], in[501];
 
int main() {
    scanf("%d", &tc);
    while (tc--) {
        memset(mat, 0, sizeof(mat));
        memset(in, 0, sizeof(in));
 
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &order[i]);
 
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                mat[order[i]][order[j]] = 1;
                in[order[j]]++;
            }
        }
 
        scanf("%d", &m);
        for (int i = 0; i < m; ++i) {
            scanf("%d %d", &a, &b);
            if (mat[a][b]) {
                mat[a][b] = 0;
                mat[b][a] = 1;
                in[b]--, in[a]++;
            }
            else {
                mat[b][a] = 0;
                mat[a][b] = 1;
                in[a]--, in[b]++;
            }
        }
 
        queue<int> q;
        for (int i = 1; i <= n; ++i)
            if (!in[i])
                q.push(i);
 
        bool certain = true;
        vector<int> ans;
        while (!q.empty()) {
            if (q.size() > 1) {
                certain = false;
                break;
            }
 
            int cur = q.front();
            q.pop();
            ans.push_back(cur);
 
            for (int next = 1; next <= n; ++next) {
                if (mat[cur][next]) {
                    in[next]--;
                    if (!in[next])
                        q.push(next);
                }
            }
        }
 
        if (!certain) //uncertain
            puts("?");
        else if (ans.size() == n) { //possible
            for (int i = 0; i < n; ++i)
                printf("%d ", ans[i]);
            puts("");
        }
        else //impossible
            puts("IMPOSSIBLE");
    }
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 2637 장난감조립  (0) 2018.02.21
백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20

장난감조립




완제품을 조립하기위해 기본 부품들과 기본 부품들로 만드는 중간 부품들이 필요하다.

기본->중간 // 중간->중간 // 중간->완제품 으로 만들기 위해 필요한 개수가 주어질 때,

완제품을 만들기 위해 필요한 기본 부품들의 갯수를 구해보자.


테크트리를 탄다는 점에서 위상정렬을 생각해 볼 수 있다.

또한 부품을 여러개 써야 다음 단계로 넘어갈 수 있다는 점에서, 간선에 그 몇개에 해당하는 정보도 저장해야 한다.

그리으로 나타내면 다음과 같다.


간선을 잘 정의해서 그래프를 구성하자.

또한 각 노드마다 어떤 기본 부품이 몇개 필요한지 저장할 배열도 필요하다.

기본 부품은 진입차수가 0인 노드임을 금방 알 수 있다. 기본 부품들의 부품배열엔 자기 자신만 들어가 있을 것이다.


이제 위상정렬을 위한 큐질을 하면서 노드의 부품배열에 간선의 가중치를 전부 곱해서 다음 노드의 부품배열에 더해주자.

이후 간선을 제거해가면서 진입차수가 0이 된다면 부품이 완성된 것이고, 다음 단계로 넘어갈 수 있다. 큐에 넣는다.

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
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
struct edge {
    int num, val;
};
int blocks[101][101];
int in[101];
int n, m, x, y, k;
 
int main() {
    scanf("%d %d", &n, &m);
    vector<vector<edge>> vec(n+1);
 
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %d", &x, &y, &k);
        vec[y].push_back({ x,k });
        in[x]++;
    }
 
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (!in[i]) {
            q.push(i);
            blocks[i][i] = 1;
        }
    }
        
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        for (auto next : vec[cur]) {
            for (int i = 1; i <= n; ++i)
                blocks[next.num][i] += blocks[cur][i] * next.val;
 
            in[next.num]--;
            if (!in[next.num])
                q.push(next.num);
        }
    }
 
    for (int i = 1; i <= n; ++i)
        if (blocks[n][i])
            printf("%d %d\n", i, blocks[n][i]);
 
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 3665 최종 순위  (0) 2018.02.21
백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20

Strahler 순서




위상정렬의 변형문제.

strachler 순서가 정해지는 데 일련의 규칙이 있고, 따라서 간선을 지울 때 다른 작업을 추가로 해줘야 한다.


먼저 진입차수가 0인 노드들의 strachler 순서는 0이다. 이제 이 노드들이 큐에서 꺼내질 때, 노드의 진출 간선들을 지우면서

규칙에 따른 작업을 한다.


규칙은 다음과 같다.

  • 나머지 노드는 그 노드로 들어오는 강의 순서 중 가장 큰 값을 i라고 했을 때, 들어오는 모든 강 중에서 Strahler 순서가 i인 강이 1개이면 순서는 i, 2개 이상이면 순서는 i+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
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
struct Strahler {
    int max, order_cnt[1001], order;
};
 
int in[1001];
int k, kk, m, p, a, b;
 
int main() {
    scanf("%d", &k);
    while (k--) {
        scanf("%d %d %d", &kk, &m, &p);
        for (int i = 1; i <= m; ++i)
            in[i] = 0;
 
        vector<vector<int>> vec(m + 1);
        for (int i = 0; i < p; ++i) {
            scanf("%d %d", &a, &b);
            vec[a].push_back(b);
            in[b]++;
        }
 
        vector<Strahler> st(m + 1);
        queue<int> q;
        for (int i = 1; i <= m; ++i) {
            if (!in[i]) {
                q.push(i);
                st[i].order = 1;
            }
        }
 
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
 
            for (auto next : vec[cur]) {
                if (st[next].max < st[cur].order)
                    st[next].max = st[cur].order;
 
                st[next].order_cnt[st[cur].order]++;
 
                in[next]--;
                if (!in[next]) {
                    if (st[next].order_cnt[st[next].max] == 1)
                        st[next].order = st[next].max;
                    else if (st[next].order_cnt[st[next].max] > 1)
                        st[next].order = st[next].max + 1;
                    q.push(next);
                }
            }
        }
        printf("%d %d\n", kk, st[m].order);
    }
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 3665 최종 순위  (0) 2018.02.21
백준) 2637 장난감조립  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20

ACM Craft


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



전의 게임 개발 (https://www.acmicpc.net/problem/1516)과 같은 문제다.


게임 개발은 모든 건물의 최소 건설 완료 시간을 물어봤다면, 이 문제는 한 건물만 물어본다.



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
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
int time[1001], in[1001];
int t, n, k, a, b, w;
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &k);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &time[i]);
            in[i] = 0;
        }
 
        vector<vector<int>> vec(n + 1);
        for (int i = 0; i < k; ++i) {
            scanf("%d %d", &a, &b);
            vec[a].push_back(b);
            in[b]++;
        }
 
 
        vector<int> ans(n + 1);
        queue<int> q;
        for (int i = 1; i <= n; ++i) {
            if (!in[i]) {
                q.push(i);
                ans[i] = time[i];
            }
        }
 
        scanf("%d", &w);
        while (!q.empty()) {
            int m = 0;
            int cur = q.front();
            q.pop();
            if (cur == w)
                break;
 
            for (auto next : vec[cur]) {
                in[next]--;
 
                if (ans[next] < ans[cur] + time[next])
                    ans[next] = ans[cur] + time[next];
 
                if (!in[next])
                    q.push(next);
            }
        }
        printf("%d\n", ans[w]);
    }
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 2637 장난감조립  (0) 2018.02.21
백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20
백준) 1766 문제집  (0) 2018.02.20

게임 개발


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



테크트리를 타고 모든 건물을 지어야 한다. 모든 건물을 짓는데 시간이 얼마나 들까?


생각해야 할 점은 건물들이 동시에 지어질 수 있다는 점이다.


예를 들어 현재 배럭과 벙커를 지을 수 있다면, 배럭을 짓는데 시간이 더 오래 걸리므로 배럭 건설시간이 정답이 된다.



큐는 현재 지을 수 있는 건물(진입차수가 0이 된 노드)을 담고 있으므로,


큐를 건설시간이 작은 순으로 정렬되는 우선순위 큐로 바꾼다면, 맨 뒤에 있는 배럭이 정답에 반영될 것이다.



다르게 말하자면,


a->b (10)// c->b (20)라는 테크트리에 대해, 


b를 짓기 위해선 a와 c를 둘 다 지어야 하지만, b를 짓기 위한 준비 시간은 c만 포함된다.



따라서 b로 진입하는 두 간선 중 가벼운 a가 먼저 지어지면서 간선이 없어지지만, 무거운 c간선이 남아있으므로


정답에 반영되지 않는다.


다음으로 c간선이 없어지면서 b를 지을 수 있게되었다. 이제 가장 무거웠던 c간선의 20초가 정답에 들어간다.


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 <stdio.h>
#include <queue>
#include <vector>
using namespace std;
 
struct build {
    int num, time;
};
bool operator <(const build& a, const build& b) {
    if (a.time != b.time)
        return a.time > b.time;
    return a.num > b.num;
}
build buildings[501];
 
int n, a, b, c;
int in[501];
 
int main() {
    scanf("%d", &n);
    vector<vector<int>> vec(n + 1);
 
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a);
        buildings[i].time = a;
 
        while (1) {
            scanf("%d", &a);
            if (a == -1)
                break;
 
            vec[a].push_back(i);
            in[i]++;
        }
    }
 
    priority_queue<build> q;
    for (int i = 1; i <= n; ++i) {
        if (!in[i])
            q.push({i,buildings[i].time});
    }
 
    while (!q.empty()) {
        int cur = q.top().num;
        q.pop();
 
        for (auto next : vec[cur]) {
            in[next]--;
            if (!in[next]) {
                buildings[next].time += buildings[cur].time;
                q.push({next, buildings[next].time});
            }    
        }
    }
 
    for (int i = 1; i <= n; ++i)
        printf("%d\n", buildings[i].time);
 
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 2623 음악프로그램  (0) 2018.02.20
백준) 1766 문제집  (0) 2018.02.20
백준) 2252 줄 세우기  (0) 2018.02.19

음악프로그램





줄 세우기 문제(http://js1jj2sk3.tistory.com/94?category=755224)와 같은 위상정렬문제다.


다만 간선을 만드는 과정과 사이클의 유무를 확인하는 데 유의하자.


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
#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
 
int n, m, a, b, c;
int in[1001];
 
int main() {
    scanf("%d %d", &n, &m);
    vector<vector<int>> vec(n+1);
 
    for (int i = 0; i < m; ++i) {
        scanf("%d", &a);
        scanf("%d", &b);
        for (int j = 1; j < a; ++j) {
            scanf("%d", &c);
            vec[b].push_back(c);
            in[c]++;
            b = c;
        }
    }
 
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (!in[i])
            q.push(i);
    }
 
    vector<int> ans;
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        ans.push_back(t);
 
        for (auto next : vec[t]) {
            in[next]--;
            if (!in[next])
                q.push(next);
        }
    }
 
    if (ans.size() != n) {
        printf("0");
        return 0;
    }
 
    for (auto a : ans)
        printf("%d\n", a);
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 1766 문제집  (0) 2018.02.20
백준) 2252 줄 세우기  (0) 2018.02.19

문제집


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


위상정렬 문제.

다만 스페셜 저지가 아닌만큼, 같은 위상이라도 특수조건이 주어진다.

예제의 경우에, 3과 4는 같은 위상이지만, 조건3에 의해 3이 더 쉬운문제이므로 3을 먼저 풀어야 한다.

이제 3이 없어졌으니까(3이 뿜는 간선도 사라졌다) 문제 4와 1은 같은 위상이다. 조건 3에 의해 1을 먼저 푼다.


즉 큐는 큐지만, 문제 번호가 낮은 걸 먼저 pop해줄 자료구조로 우선순위 큐를 쓰면 풀 수 있다.

heap을 만들어서 풀어봤지만 속도는 같았다.


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
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
int n, m, a, b;
int in[32001];
 
struct heap {
    int* arr;
    int cnt = 0;
 
    heap(int n) { arr = new int[n]; }
    ~heap() { delete[] arr; }
 
    void swap(int& a, int& b) {
        int t = a; a = b; b = t;
    }
 
    void push(int x) {
        ++cnt;
        arr[cnt] = x;
        int v = cnt;
 
        while (v / 2 >= 1 && arr[v/2] > arr[v]) {
            swap(arr[v], arr[v / 2]);
            v /= 2;
        }
    }
 
    void pop() {
        arr[1] = arr[cnt];
        cnt--;
 
        int v = 1;
        while (v * 2 <= cnt) {
            int iv = v * 2;
            if (iv + 1 <= cnt && arr[iv] > arr[iv + 1])
                iv++;
            if (arr[v] > arr[iv]) {
                swap(arr[v], arr[iv]);
                v = iv;
            }
            else
                break;
        }
    }
    int top() { return arr[1]; }
    bool empty() { return cnt == 0; }
};
 
int main() {
    scanf("%d %d", &n, &m);
    vector<vector<int>> edge(n + 1);
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &a, &b);
        edge[a].push_back(b);
        in[b]++;
    }
 
    //priority_queue<int> pq;
    heap pq(n + 1);
    for (int i = 1; i <= n; ++i)
        if (!in[i])
            pq.push(i);
 
    while (!pq.empty()) {
        int t = pq.top();
        printf("%d ", t);
        pq.pop();
 
        for (auto next : edge[t]) {
            in[next]--;
            if (in[next] == 0)
                pq.push(next);
        }
    }
 
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20
백준) 2252 줄 세우기  (0) 2018.02.19

+ Recent posts

티스토리툴바