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



이분매칭으로 문제를 해결했습니다.


문제해결방법

1. 인풋으로 들어온 상어의 능력치 별로 간선을 만들어줍니다.

a가 b를 먹을 수 있다면 a의 간선에 b를 넣어줍니다.

이 문제의 핵심은 a==b인 경우입니다.(세 개의 능력치가 같은 경우)

이게 왜 중요하냐면

a가 b를 먹었는데

밑에서 b가 a를 또 먹을 수 있기 때문에 이것을 방지해야합니다.


가장 간단한 방법으로(사실 다른 방법따위 모름) 인덱스가 a < b인 경우에만 먹을 수 있게 하면 됩니다.(물론 같은경우에만)

이렇게 되면 a와 b가 능력치가 같을경우 a를 처리할떄 b를 먹을 것이고 b를 처리할 때는 a > b 이므로 먹을 수 없습니다.


2. 간선을 만든 후 상어는 각각 두마리씩 먹을 수 있습니다. 그러므로 한번 처리할떄 두번씩 먹어줍니다 

제가 계속 실수 했던 부분이

visit을 초기화안하고 먹고 또먹었습니다.


이렇게

1
2
3
4
5
6
    for (int i = 0; i < n; i++) {
        memset(visit, 0, sizeof(visit));
        f(i);
        memset(visit, 0, sizeof(visit));
        f(i);
    }

cs


이렇게 멤셋을 두번해줘야합니다!!!
이유는 아래의 예시를 보면서 설명하겠습니다.

이 그림은 현재
1번이 1번과 2번을 매칭했을 때
2번이 1번을 뺏어서 1번이 3번과 매칭된 상황입니다.
2번이 1번을 뺏으면서 visit[1]은 방문한 상태가 되겠죠??
근데 visit초기화를 안하면
2번이  2번에 매칭을 시도하면서 1번으로 들어가서 1-2를 미뤄내고 4번에 연결되어야하는데(1과 4사이에 선이 있다고 가정)
이미 방문했기 때문에 그냥 넘어가버리게 되죠!@

이게 핵심입니당!!

3. 마지막으로 B배열이 -1인 것을 카운트하여 출력하면 정답입니다.(-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
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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 1000
 
using namespace std;
 
int B[MAX_SIZE];
bool visit[MAX_SIZE];
vector<int> edge[MAX_SIZE];
 
int sharkSize[MAX_SIZE];
int sharkIntel[MAX_SIZE];
int sharkSpeed[MAX_SIZE];
 
int n;
 
int eat(int a, int b) {
    int ret = 0;
    if (sharkSize[a] < sharkSize[b]) return 0;
    else if(sharkSize[a] == sharkSize[b]) ret++;
    if (sharkIntel[a] < sharkIntel[b]) return 0;
    else if (sharkIntel[a] == sharkIntel[b]) ret++;
    if (sharkSpeed[a] < sharkSpeed[b]) return 0;
    else if (sharkSpeed[a] == sharkSpeed[b]) ret++;
 
    if (ret == 3) return 2;
    return 1;
}
 
bool f(int from) {
    visit[from] = 1;
 
    for (int i = 0; i < edge[from].size(); i++) {
        int to = edge[from][i];
        if (B[to] == -1 || !visit[B[to]] && f(B[to])) {
            B[to] = from;
            return 1;
        }
    }
 
    return 0;
}
 
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &sharkSize[i], &sharkIntel[i], &sharkSpeed[i]);
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int eatFlag = eat(i, j);
 
            if (eatFlag == 1) edge[i].push_back(j); //먹을 수 있는경우
            else if (eatFlag == 2 && i < j) edge[i].push_back(j); // 능력치가 같은 경우
        }
    }
 
    memset(B, -1, sizeof(B));
    
    for (int i = 0; i < n; i++) {
        memset(visit, 0, sizeof(visit));
        f(i);
        memset(visit, 0, sizeof(visit));
        f(i);
    }
 
    int ret = 0;
    for (int i = 0; i < n; i++) if (B[i] == -1) ret++;
    printf("%d", ret);
 
    return 0;
}
cs





'알고리즘 > 네트워크 플로우' 카테고리의 다른 글

[12843] 복수전공  (0) 2017.08.24
[1017] 소수 쌍  (0) 2017.06.27
[6086] 최대유량  (1) 2017.06.03

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



처음에 행렬 크기도 작고 dfs로 해결하면 끝이겠다 싶었습니다.

하지만.. 예제케이스를보면 ㅜ 모양 등 dfs로는 만들 수 없는 모양이 존재했습니다..


짱돌을 아무리 굴려도 해결할 수 없는..ㅠㅠ

블로그를 참조했습니다.


해결방법은 행렬이 작다는 것을 이용한 아이디어였습니다.

어떻게 이용하냐!


하면...


결국 25칸의 학생들 중에 7명을 고르면 된다는 점입니다!(다른 분은 어떻게 푸셨는지 모르겠음.. 아이디어만 스틸해옴..)


저는 그래서 dfs를 이용하여 학생들을 선택할 수 있는 모든 방법을 만들었습니다.

1번~25번까지의 학생이 있다고 생각하면 !

1,2,3,4,5,6,7

1,2,3,4,5,6,8

..

...

19,20,21,22,23,24,25

까지의 경우가 있겠죠!


이 모든 경우의 수는 25C7 입니다.


이렇게  dfs를 이용해서 깊이가 7 즉 7명의 학생까지 선택하면!

dfs의 매개변수에 S에 다솜파가 몇명인지를 계속 넘겨줍니다!

만약에 다솜파가 4명 이상이면! dfs로 선택한 7명이 전부 연결되어있는지를 확인합니다.!!!

그래서 전부 연결되어있다면 1을 리턴하여 카운트. 아니면 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
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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 5
 
using namespace std;
 
char map[MAX_SIZE][MAX_SIZE];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
 
int visit;
 
pair<int, int> toPos(int num) {
    return make_pair(num / 5, num % 5);
}
 
int toNum(pair<int, int> pos) {
    return pos.first * 5 + pos.second;
}
 
//내가 선택한 7명이 연결되어있는지를 확인하는 함수
bool exploration(int state, pair<int, int> pos) {
    visit |= 1 << toNum(pos); // 전역 변수 visit에 해당 학생을 쉬프트하여 체크
    if (state == visit) return 1; //isConnected에서 넘겨받은 state와 exploration으로 방문한 학생이 같으면 리턴 1
 
    bool ret = 0;
 
    for (int i = 0; i < 4; i++) {
        pair<int, int> npos = make_pair(pos.first + dx[i], pos.second + dy[i]);
 
        if (npos.first < 0 || npos.second < 0 || npos.first >= 5 || npos.second >= 5) continue;
        
        int nNum = toNum(npos);
 
        if (visit & (1 << nNum)) continue;
        if ((1 << nNum) & state) ret = max(ret, exploration(state, npos));
    }
    return ret;
}
 
//전부 연결되어있다면 1을 아니라면 0을 리턴하는 함수
bool isConnected(int state) {
    pair<int, int> now;
    
    //포문을 이용하여 내가 선택한 7명 중 한명을 찾아 탐색의 시작점으로 선택
    for (int i = 0; i < 25; i++) {
        if ((1 << i) & state) {
            now = toPos(i);
            visit = 1 << i;
            break;
        }
    }
    
    return exploration(state, now);
}
 
//dfs를 이용하여 25명의 학생 중 7명을 고르는 함수
int f(int num, int d, int state, int sCnt) {
    if (d == 7) {
        if (sCnt >= 4) return isConnected(state);
        else return 0;
    }
    int ret = 0;
 
    for (int i = num + 1; i < 25; i++) {
        pair<int, int> pos = toPos(i);
        ret += f(i, d + 1, state | (1 << i), map[pos.first][pos.second] == 'S' ? sCnt + 1 : sCnt);
    }
 
    return ret;
}
 
int main() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            map[i][j] = getchar();
        }
        getchar();
    }
 
    int ret = 0;
    for (int i = 0; i < 25 - 6; i++) {
        pair<int, int> pos = toPos(i);
        ret += f(i, 1, 1 << i, map[pos.first][pos.second] == 'S' ? 1 : 0);
    }
    printf("%d", ret);
    return 0;
}
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[10974] 모든 순열  (2) 2017.07.27
[1058] 친구  (0) 2017.07.20
[2146] 다리 만들기  (2) 2017.05.23
[14503] 로봇 청소기  (2) 2017.04.18
[14502] 연구소  (5) 2017.04.18

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



처음엔 이분 매칭 문제인 것을 모르고..

엄청나게 틀렸네요... 시간초과 + 구현실수....


알고나서도 한참을 해맸는데요!

첫번째 이유는 첫번째 수와 매칭되는 수를 출력한다는 점이었어요..


소수 쌍을 구하는 것이기 때문에

홀수 + 홀수 = 짝수(2를 제외하고는 무조건 소수가 안됨)

짝수 + 짝수 = 짝수(무조건 안됨)

홀수 + 짝수 = 홀수(가능성 있음)

입니다!


그렇기 때문에 그룹을 홀수와 짝수로 나누어야하는데요!


첫번쨰 수가 홀수일수 도있고 짝수일 수도 있기 때문에 어떻게 진행해야할지 난해했습니다.

두번째 소수를 구하는 방법입니다. 풀고나니깐 뭐.. 에라토스테네스의 체를 써도 되고 그냥 나눠서 확인해도

입력받는 수가 1000까지기 때문에 최대 1999(두 수를 합쳐야하므로)밖에 안되서 오래걸리진 않습니다.


마지막으로 출력입니다. 입력이 정렬되서 들어온다는 말은 없으므로 출력할 때 정렬을 해야합니다.

저같은 경우는 우선순위 큐에 넣어서 그냥 큐가 빌때까지 출력했습니다.

-1이 출력되는 조건은 큐가 비어있다면 -1을 출력했습니다.


문제 해결 전략은

1. 첫번째 수와 다른 그룹의 수와 매칭을 시킨다.

2. 1에서 매칭된 수가 소수라면 1에서 매칭된 쌍을 제외하고 이분매칭 알고리즘을 이용해서 나머지를 매칭합니다.

3. 만약 전부 매칭해서 매칭 된 수가 입력 받은 N의 절반이 된다면 전부 매칭된 것이므로 우선순위 큐에다가 처음에 첫번째 수와 매칭한 수를 푸시해줍니다.

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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
 
#define ll long long
#define MAX_SIZE 50
#define INF 987654321
#define MOD 1000000
using namespace std;
 
int arrA[MAX_SIZE];
int arrB[MAX_SIZE];
int pick;
int idxA, idxB;
 
int matchA[MAX_SIZE];
int matchB[MAX_SIZE];
bool visit[MAX_SIZE];
 
bool isPrime(int a) {
    if (a == 1) return 0;
    else if (a != 2 && a % 2 == 0) return 0;
    
    for (int i = 3; i * i <= a; i += 2) {
        if (a % i == 0) return 0;
    }
 
    return 1;
}
 
bool f(int idx) {
    if (visit[idx]) return 0;
    visit[idx] = 1;
 
    for (int i = 0; i < idxB; i++) {
        if (i == pick) continue;
 
        if (isPrime(arrA[idx] + arrB[i]) && (matchB[i] == -1 || !visit[matchB[i]] && f(matchB[i]))) {
            matchB[i] = idx;
            matchA[idx] = i;
 
            return 1;
        }
    }
 
    return 0;
}
 
int main() {
    int arr[MAX_SIZE];
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    
    for (int i = 0; i < n; i++) {
        if (arr[0] % 2 == arr[i] % 2) arrA[idxA++] = arr[i];
        else arrB[idxB++] = arr[i];
    }
 
    priority_queue<int> pq;
 
    for (int i = 0; i < idxB; i++) {
        if (isPrime(arrA[0] + arrB[i])) {
            pick = i;
            
            int cnt = 1;
            memset(matchA, -1, sizeof(matchA));
            memset(matchB, -1, sizeof(matchB));
 
            for (int j = 1; j < idxA; j++) {
                memset(visit, 0, sizeof(visit));
                if (f(j)) cnt++;
            }
 
            if (cnt == n / 2) pq.push(-arrB[i]);
        }
    }
 
    if (pq.empty()) puts("-1");
    else {
        while (!pq.empty()) {
            printf("%d ", -pq.top()), pq.pop();
        }
    }
 
    return 0;
}
cs


'알고리즘 > 네트워크 플로우' 카테고리의 다른 글

[12843] 복수전공  (0) 2017.08.24
[1671] 상어의 저녁식사  (0) 2017.07.02
[6086] 최대유량  (1) 2017.06.03

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



처음에 dfs로 방문체크를 하면서 cost가 크거나 같으면 이동하는 식으로 해서 해결해보려고 했으나

65프로에서 시간초과가 뜨더군요.

제한시간이 2초인데

dfs로 하면 최악의 경우 15!의 시간이 걸리기 때문에 해결할 수 없었습니다.


그래서 dp를 이용해야 했는데..

방문한 곳의 상태가 필요했기 때문에 비트마스크를 사용했습니다.


제 dp의 정의는


dp[1 << 15][15][10] : 방문상태, 아티스트 번호, 비용으로 정의했습니다.


아래는 코드입니다.


f함수의 매개변수는 방문상태, 아티스트 번호, 코스트, 깊이 입니다.



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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
 
#define ll long long
#define MAX_SIZE 15
#define INF 987654321
#define MOD 1000000
using namespace std;
 
int dp[1 << MAX_SIZE][MAX_SIZE][10]; //state, artistNumber, cost
int cost[MAX_SIZE][MAX_SIZE];
int n;
 
int f(int state, int artist, int c, int d) {
    int &ret = dp[state][artist][c];
    if (ret != 0) return ret;
    ret = d;
 
    for (int i = 0; i < n; i++) {
        if (state & (1 << i) || cost[artist][i] < c) continue;
        ret = max(ret, f(state | (1 << i), i, cost[artist][i], d + 1));
    }
    return ret;
}
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &cost[i][j]);
        }
    }
 
    printf("%d", f(1, 0, 0, 1));
    
    return 0;
}
cs


'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[1102] 발전소  (0) 2017.07.08
[2698] 인접한 비트의 개수  (0) 2017.07.04
[1915] 가장 큰 정사각형  (0) 2017.06.07
[2629] 양팔 저울  (0) 2017.04.25
[2133] 타일 채우기  (0) 2017.04.20

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


와 너무 신기한 문제에요..ㅠㅠ

N이 진짜 말도안되게 커서 어떻게 접근해야할지 감도 안왔습니다..


규칙이 있나 찾아봤는데 규칙이 있는 것도 아니였습니다.


자료를 찾다보니... 3의 제곱수를 하나씩만 사용할 수 있는게 힌트였습니다!


진짜 엄청난 힌트더군요..


자꾸 사람들이 2진수 이야기를 하길래 무슨 소린가...했는데..


3의 제곱수를 하나씩만 사용한다는 얘기는 !!!

27 9 3 1 이렇게 있다고 치면!

                

27

9

3

1

0

0

0

1

0

0

1

0

0

0

1

1

0

1

0

0

0

1

0

1

0

1

1

0

0

1

1

1

1

0

0

0

1

0

0

1


어디서 많이 보던!!!!!! 표입니다!

그렇습니다! 하나만 쓰게되면 이진수처럼 됩니당!

그래서 N을 2진수로 바꾼 후에 이 2진수를 3진수를 이용해서 10진수로 바꾸면! 결과가 나옵니다.


예제에 N = 4였습니다.

4는 2진수로

100 입니다! 3진수로 100은 9입니다.

그래서 답은 9죠!


진짜 재밌는 문제입니다..... 소오름~~~

아래는 코드입니다.

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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
 
#define ll long long
using namespace std;
 
int main() {
    ll n;
    scanf("%lld", &n);
    
    queue<bool> q;
    while (n) {
        q.push(n % 2);
        n /= 2;
    }
 
    ll ans = 0;
    ll add = 1;
 
    while (!q.empty()) {
        ans += q.front() * add;
        add *= 3;
        q.pop();
    }
 
    printf("%lld", ans);
    
    return 0;
}
 
cs


'알고리즘 > 수학' 카테고리의 다른 글

[13412] 서로소 쌍  (0) 2017.09.07
[2436] 공약수  (2) 2017.09.01

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


요즘 나태해져서.. 다시 열심히 해야겠습니다 ㅎㅎ!!

DP문제입니다!


간단하게 생각하면 별로 안어려운 문제인 것 같습니다!


딱봐도..4인데... 어떻게 dp로 접근했냐하면


for문은 행우선으로 진행하면 됩니다. 행의 모든 열을 다 돌면 다음행!


그리고 중요한 것은 해당 배열의 위, 왼쪽, 그리고 왼쪽위 대각선 이 세방향을 검사했습니다.


내가 1이고 그 세 개중에 가장 작은 값(0은 제외) + 1이 결국 정사각형의 변의 길이입니다.


예제를 보면서 해결해보도록하죠!


4 4

0100

0111

1110

0010


dp테이블을 써보도록하겠습니다.

0100
0111
1120
0010

최대 변의 길이는 2겠지요!?!
그래서 정답은 2 * 2 = 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
#include <cstdio>
#define MAX_SIZE 1000
#define INF 0x7fffffff
 
bool arr[MAX_SIZE][MAX_SIZE];
int dp[MAX_SIZE][MAX_SIZE];
 
int min(int a, int b) {
    return a > b ? b : a;
}
 
int max(int a, int b) {
    return a > b ? a : b;
}
 
int main() {
 
    int m, n;
    scanf("%d %d", &m, &n);
 
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &arr[i][j]);
        }
    }
 
    int ret = 0;
    int dx[3] = { 0, -1, -1 };
    int dy[3] = { -1, 0, -1 };
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!arr[i][j]) continue;
 
            int min_value = INF;
            for (int k = 0; k < 3; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
 
                if (nx < 0 || ny < 0) {
                    min_value = 0;
                    break;
                }
                min_value = min(min_value, dp[nx][ny]);
            }
            if (!min_value) dp[i][j] = 1;
            else if (min_value != INF) dp[i][j] = min_value + 1;
 
            ret = max(dp[i][j], ret);
        }
    }
 
    printf("%d\n", ret * ret);
 
    return 0;
}
cs


'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[2698] 인접한 비트의 개수  (0) 2017.07.04
[1029] 그림 교환  (0) 2017.06.27
[2629] 양팔 저울  (0) 2017.04.25
[2133] 타일 채우기  (0) 2017.04.20
[1309] 동물원  (0) 2017.04.20

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


네트워크 플로우에서 최대 유량 문제입니다.

저도 처음 공부하기 때문에 다른 블로그를 참조하면서 공부했습니다.


필요한 변수 선언입니다.


1
2
3
4
5
    int n; //input으로 받는 edge 수
    vector<int> adj[MAX_SIZE]; // 인접
    int capacity[MAX_SIZE][MAX_SIZE] = { 0, }; // 용량
    int flow[MAX_SIZE][MAX_SIZE] = { 0, }; // 흐르는 양
    int prev[MAX_SIZE]; // 경로를 저장(현재 정점의 이전 정점이 무엇이었는지)
cs


입력 부분입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//입력
    scanf("%d", &n);
    getchar();
 
    for (int i = 0; i < n; i++) {
        char s, e;
        int c;
 
        scanf("%c %c %d", &s, &e, &c);
        getchar();
 
        s = ctoi(s), e = ctoi(e); //입력 받은 정점을 숫자로 변환
 
        //같은 간선이 여러개 들어오면 용량이 그만큼 늘어나면 됨
        capacity[s][e] += c;
 
        //정,역방향 간선 추가
        adj[s].push_back(e);
        adj[e].push_back(s);
    }
cs


15번째 줄의 += 부분이 잘이해가 안가실 수 있습니다.

capacity배열은 0으로 전부 초기화 되어있습니다.

입력에서 만약 A -> B 로 가는 edge를 여러개로 준다면

A->B로 가는 유량은 edge의 총 용량만큼이기 때문에 +=로 해주는 것입니다.


19번째에서 역방향 간선까지 추가하는 것이 포드 풀커슨 알고리즘의 핵심인 것 같습니다..(잘은 이해안감..ㅠㅠ)


처리부분입니다.

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
    //process
    int total_flow = 0;
    const int start = ctoi('A'), end = ctoi('Z');
 
    while (1) {
        for (int i = 0; i < MAX_SIZE; i++) prev[i] = -1;
 
        queue<int> q;
        q.push(start);
 
        while (!q.empty())
        {
            int curr = q.front();
            q.pop();
 
            for (int i = 0; i < adj[curr].size(); i++) {
                int next = adj[curr][i];
 
                if (capacity[curr][next] - flow[curr][next] > 0 && prev[next] == -1) {
                    q.push(next);
                    prev[next] = curr;
                    if (next == end) break;
                }
            }
        }
 
        if (prev[end] == -1) break; //Z까지 가는 길이 없으면..
 
        //A에서 Z로 가는 경로 중에서 가장 작은 용량을 선택    
        int min_flow = INF;
        for (int i = end; i != start; i = prev[i])
            min_flow = min(min_flow, capacity[prev[i]][i] - flow[prev[i]][i]);
 
        //A에서 Z로 가는 경로에 물을 흘림
        //지나간 경로의 반대 경로에는 -값의 물을 흘림
        for (int i = end; i != start; i = prev[i]) {
            flow[prev[i]][i] += min_flow;
            flow[i][prev[i]] -= min_flow;
        }
        
        total_flow += min_flow;
    }
cs

start, end는 시작과 끝점 입니다. 이 문제에서는 'A'와 'Z'가 되겠습니다.

bfs를 통해서 A->Z로 가는 경로를 찾습니다.

경로는 prev배열에 현재 정점 바로 전의 정점을 저장을 해서 경로를 알 수 있습니다.


예를 들어 A->B->C 라면 prev[A] = -1, prev[B] = A, prev[C] = B 입니다.

최종 도착지점은 항상 'Z'이므로 Z부터 역으로 추적하면 A까지 도달할 수 있습니다.


16번째 줄이 굉장히 중요합니다.

1
2
3
4
5
6
7
8
9
for (int i = 0; i < adj[curr].size(); i++) {
    int next = adj[curr][i];
 
    if (capacity[curr][next] - flow[curr][next] > 0 && prev[next] == -1) {
        q.push(next);
        prev[next] = curr;
        if (next == end) break;
    }
}
cs


curr(현재 정점)에서 연결되어 있는 부분을 탐색합니다.


curr->next의 edge에 용량이 꽉 차지 않았다면 그리고 아직 방문하지 않았다면

if (capacity[curr][next] - flow[curr][next] > 0 && prev[next] == -1)

next 정점을 q에 넣고 prev[다음 정점] = 현재 정점 을 넣어줍니다.

만약 다음 정점이 'Z'(end)라면 루프를 빠져나옵니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
        if (prev[end] == -1) break; //Z까지 가는 길이 없으면..
 
        //A에서 Z로 가는 경로 중에서 가장 작은 용량을 선택    
        int min_flow = INF;
        for (int i = end; i != start; i = prev[i])
            min_flow = min(min_flow, capacity[prev[i]][i] - flow[prev[i]][i]);
 
        //A에서 Z로 가는 경로에 물을 흘림
        //지나간 경로의 반대 경로에는 -값의 물을 흘림
        for (int i = end; i != start; i = prev[i]) {
            flow[prev[i]][i] += min_flow;
            flow[i][prev[i]] -= min_flow;
        }
        
        total_flow += min_flow;
cs


주석을 달아 놓은 것처럼

1번째 줄은 정점 'Z'(end)의 이전 정점이 -1라는 것은 bfs에서 Z로 도달하지 못했음을 의미합니다.

그렇기 때문에 더이상 경로가 없음을 의미해서 break;합니다.


그게 아니라면 4번째 줄

bfs로 찾은 경로 구간 중에서 가장 용량이 작은 구간을 선택합니다.

유량을 가장 작은 용량으로 맞춰야만 그 경로로 흘릴 수 있기 때문입니다.

만약 이전 bfs에서 유량이 있을 수 있으므로 최소 용량은 capacity[이전 정점][현재 정점] - flow[이전 정점][현재 정점]으로 구해야 합니다.


그리고


10번째 줄에서 A->Z까지의 경로에 위에서 찾은 min_flow(가장 작은 유량)을 더합니다.

여기서 중요한 부분은 12번째 줄입니다. 경로의 반대 방향으로 -유량을 더해줍니다.

위의 input부분에서 역방향 간선까지 함께 만든 이유입니다.


capacity[curr][next] - flow[curr][next] > 0

아까 이 부분에서 0보다 크면 큐에다가 next를 푸시했는데요.

만약 flow[curr][next]가 -유량이라면 +가 되기 때문에 항상 흐를 수 있습니다.


예시를 보면서 이해하도록 하겠습니다.

이 예시는

http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220804885235

를 참고 했으며 제가 설명하는 것 보다 훨씬 상세하게 설명해주셨습니다. 저도 이 블로그를 보고 이해했습니다.


지저분해도 .. 이해해주세요!


bfs로



이 경로까지는 찾으셨을텐데요..


이 유량을 다합치면 9가 되죠.

이게 최대일 것 같지만 그렇지 않습니다.


A->E->F->D->B->G->Z의 경로로 1만큼 흘린다면 Z에 최대 10까지 도달할 수 있습니다.


저는 여기서 D->B구간이 이해가 안갔는데..

이 부분이 -유량을 흘린 이유입니다.

B->D구간의 유량은 3이 흐르고 있습니다.

D->B구간은 애초에 경로가 없습니다. 어떻게 흐를까요?


사실.. 진짜로 흐르는 것이 아니라 B->D구간을 상쇄시키는 느낌??적인 느낌입니다.

D->B구간으로 1을 흘려보내면 B->D구간에서 원래 3이 흐르고 있었으니.. 2가 되겠죠!


그리고 그 B->D에서 상쇄시킨 그 1을  B->G 구간으로 보내는 것입니다!!!!!....

느낌만 이해했습니다.. 완전 이해는 아닌..

어떻게 이런거 까지 생각해냈는지는 잘 모르겠네요...ㅠㅠㅠ

제가 참고하라고 올려드린 블로그..

http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220804885235

를 참조해주세요!!!!!! 정말 잘 설명해주셨습니다..


아래는 풀 코드입니다.


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
/*
input)
11
A B 3
A C 3
A D 4
B E 2
C B 10
C E 1
D F 5
E D 1
E F 1
E Z 2
F Z 5
output)
7
*/
 
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
 
#define MAX_SIZE 52
#define INF 0x7fffffff
 
using namespace std;
 
int ctoi(char c) {
    if (c <= 'Z') return c - 'A';
    return c - 'a' + 26;
}
 
int main() {
    int n;
    vector<int> adj[MAX_SIZE]; // 인접
    int capacity[MAX_SIZE][MAX_SIZE] = { 0, }; // 용량
    int flow[MAX_SIZE][MAX_SIZE] = { 0, }; // 흐르는 양
    int prev[MAX_SIZE]; // 경로를 저장(현재 정점의 이전 정점이 무엇이었는지)
 
    //입력
    scanf("%d", &n);
    getchar();
 
    for (int i = 0; i < n; i++) {
        char s, e;
        int c;
 
        scanf("%c %c %d", &s, &e, &c);
        getchar();
 
        s = ctoi(s), e = ctoi(e); //입력 받은 정점을 숫자로 변환
 
        //같은 간선이 여러개 들어오면 용량이 그만큼 늘어나면 됨
        capacity[s][e] += c;
 
        //정,역방향 간선 추가
        adj[s].push_back(e);
        adj[e].push_back(s);
    }
 
    //process
    int total_flow = 0;
    const int start = ctoi('A'), end = ctoi('Z');
 
    while (1) {
        for (int i = 0; i < MAX_SIZE; i++) prev[i] = -1;
 
        queue<int> q;
        q.push(start);
 
        while (!q.empty())
        {
            int curr = q.front();
            q.pop();
 
            if (curr == end) break;
 
            for (int i = 0; i < adj[curr].size(); i++) {
                int next = adj[curr][i];
 
                if (capacity[curr][next] - flow[curr][next] > 0 && prev[next] == -1) {
                    q.push(next);
                    prev[next] = curr;
                }
            }
        }
 
        if (prev[end] == -1) break; //Z까지 가는 길이 없으면..
 
        //A에서 Z로 가는 경로 중에서 가장 작은 용량을 선택    
        int min_flow = INF;
        for (int i = end; i != start; i = prev[i])
            min_flow = min(min_flow, capacity[prev[i]][i] - flow[prev[i]][i]);
 
        //A에서 Z로 가는 경로에 물을 흘림
        //지나간 경로의 반대 경로에는 -값의 물을 흘림
        for (int i = end; i != start; i = prev[i]) {
            flow[prev[i]][i] += min_flow;
            flow[i][prev[i]] -= min_flow;
        }
        
        total_flow += min_flow;
    }
 
    printf("%d\n", total_flow);
 
    return 0;
}
cs


'알고리즘 > 네트워크 플로우' 카테고리의 다른 글

[12843] 복수전공  (0) 2017.08.24
[1671] 상어의 저녁식사  (0) 2017.07.02
[1017] 소수 쌍  (0) 2017.06.27

삼성전자 면접 준비 하느라고 블로그 활동을 못했네요.

오랜만에 글 올립니다.

------------------------

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


이 문제는 2가지 절차로 풀었습니다.

1. 대륙마다 번호 붙이기.

2. 대륙끼리 가장 짧은 길이로 연결하기.


input을 받을 때 1이라면 land라는 벡터에 x, y 값을 넣었습니다.

그 후에 land_mark()라는 함수를 통해서 각 대륙마다 번호를 바꿔줍니다. (map[][]에 저장됨.)

번호를 붙인 후 바다와 연결된 대륙이라면(주변에 0이 있으면) bfs를 통해서 자신과 다른 대륙 넘버를 만나면 return해주는 dist()라는 함수를 이용합니다.


아래는 코드입니다.

궁금하신 것은 댓글 달아주세요.


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
142
143
#include <cstdio>
#include <iostream>
#include <list>
#include <queue>
#include <string.h>
#define MAX_SIZE 100
#define INF 0x7fffffff
 
using namespace std;
 
 
//input
int n;//맵크기
int map[MAX_SIZE][MAX_SIZE];//맵
 
//process
int visit[MAX_SIZE][MAX_SIZE];//방문체크
vector<pair<int, int> > land;//땅을 저장할 벡터
int land_number;//땅마다 넘버 붙이기
int visit_number;//방문체크 넘버
 
//direct
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
 
//땅마다 넘버붙이기 함수
void land_mark(int x, int y)
{
    if(visit[x][y] == 1) return;
    visit[x][y] = 1;
 
    queue<pair<int, int> > q;
    q.push(make_pair(x, y));
 
    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        map[x][y] = land_number;
 
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if(nx < 0 || ny < 0 || nx >= n || ny >= n || visit[nx][ny]) continue;
            if(!map[nx][ny]) continue;
            visit[nx][ny] = 1;
 
            q.push(make_pair(nx, ny));
 
        }
    }
 
    land_number++;
}
 
//거리를 측정하는 bfs함수 ln은 랜드 넘버
int dist(int x, int y, int ln)
{
    bool flag = 0;
    for(int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
        if(map[nx][ny] == 0)
        {
            flag = 1;
            break;
        }
    }
 
    if(!flag) return INF;//네 방향에 바다가 없으면 리턴
    visit_number++;
 
    queue<pair<pair<int, int>, int> > q;
    q.push(make_pair(make_pair(x, y), 0));
 
    while(!q.empty())
    {
        x = q.front().first.first;
        y = q.front().first.second;
        int weight = q.front().second;
        q.pop();
 
 
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if(nx < 0 || ny < 0 || nx >= n || ny >= n || visit[nx][ny] == visit_number) continue;
 
            if(map[nx][ny] == ln) continue;
            else if(map[nx][ny] != ln && map[nx][ny] != 0) return weight;
 
            visit[nx][ny] = visit_number;
            q.push(make_pair(make_pair(nx, ny), weight + 1));
        }
    }
 
    return INF;
}
 
 
int main()
{
 
    scanf("%d", &n);
 
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            scanf("%d", &map[i][j]);
            if(map[i][j] == 1) land.push_back(make_pair(i, j));
        }
    }
 
    land_number = 1;
 
    for(int i = 0; i < land.size(); i++) land_mark(land[i].first, land[i].second);
 
    memset(visit, 0, sizeof(visit));
    int ret = INF;
 
    for(int i = 0; i < land.size(); i++)
    {
        int x = land[i].first;
        int y = land[i].second;
        ret = min(ret, dist(x, y, map[x][y]));
    }
 
    printf("%d\n", ret);
 
 
    return 0;
 
}
 
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[1058] 친구  (0) 2017.07.20
[1941] 소문난 칠공주  (1) 2017.07.01
[14503] 로봇 청소기  (2) 2017.04.18
[14502] 연구소  (5) 2017.04.18
[14501] 퇴사  (4) 2017.04.17

+ Recent posts

티스토리툴바