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



n개의 선분들이 각각 두 개의 좌표로 표현되어서 주어진다.


이 각각의 선분이 교차하는 경우에 같은 그룹으로 본다고 했을 때, 그룹의 수와 가장 멤버수가 많은 그룹에 속한 선분의 개수는?



[알고리즘]


1. 입력으로 들어오는 모든 선분들에 대해서 교차판별을 진행한다.


2. union-find를 활용해서, 교차한다면 같은 그룹으로 root를 묶어준다.


3. root인 선분의 개수를 파악한다. (root의 개수가 곧 그룹의 개수)


4. 그룹을 이루는 선분의 수가 가장 많은 그룹의 선분의 수를 파악한다.



[풀이]


교차 판별은 CCW를 활용한다. 1. 선분 A에 대해서 B의 각 점과 CCW를 돌리고, 2. 선분 B에 대해서 A의 각 점과 CCW를 돌린다.


1과 2의 결과가 모두 음수여야 기본적으로 교차할 수 있는 각도로 주어져있는 상태이다.


추가적으로 문제에서 관통하지 않고 딱 만나기만 해도 교차로 간주한다고 했으므로 위 조건에 0이 되는 경우까지 추가해야 한다.



이제 놓여있는 상태에 따라서 만날 수도 있고 아닐 수도 있다.


선분 A를 이루는 두 점의 x좌표가 선분 B를 이루는 두 점의 X좌표 모두보다 작다면 당연히 만날 수 없다. y좌표의 경우도 마찬가지.


그리고 선분 B에 대해서도 마찬가지이다. 이럴 경우에는 위의 CCW결과의 곱이 둘 다 음수로 나오더라도 만날 수 없는 경우이다.



이를 진행할 때, 만난다고 판단되는 경우 union작업을 해줘야 한다. union-find를 진행하기 위해, 부모 배열(r[])을 모두 자기 자신으로 초기화 해준다.


그리고 만난다고 판단되는 경우 union해준다.


이 작업을 마쳤다 하더라도, 모든 노드의 r[] 값이 최상위 부모로 갱신되었다는 보장이 없다. 따라서 getParent를 모든 지점에 대해 수행하여 r[] 값을 최상위 부모로 갱신해준다.


cnt[] 배열은 인덱스를 최상위 부모로 하는 선분의 수이다. cnt[1] = 3이라면, 1을 최상위 부모로하는 노드가 3개 있다는 것이다.


따라서 cnt[] 값이 0초과인 경우를 카운트 해주면, 그룹의 수를 셀 수 있다.


cnt[] 값이 최대인 곳이 최대 크기의 그룹일 것이다.



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
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
struct LINE {
    int x1, y1, x2, y2;
 
};
LINE L[3001];
 
int r[3001]; // index의 root를 저장
int cnt[3001]; //index를 root로 하는 그룹 구성원 수
 
int getParent(int a) {
    if (r[a] == a) return a;
    else
        return r[a] = getParent(r[a]); //갱신하면서 찾으러 올라가야함
}
 
void join(int a, int b) {
    r[getParent(a)] = getParent(b);
}
 
ll ccw(int x1, int y1, int x2, int y2, int x3, int y3) { 
    ll ret = (x1*y2 + x2*y3 +x3*y1) - (y1*x2 + y2*x3 + y3*x1);
    if (ret < 0) return -1;
    else if (ret > 0) return 1;
    else return 0;
}
 
bool isCross(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    //만나면 true, 아니면 false -> 선분 ccw 곱의 결과가 음수이지만 안 만나는 경우
    //예외 처리 필요 -> 0인 경우도 예외 처리에 포함시켜야함(평행이동 하면 관통안하고 만나기만하는 경우)
    if (ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) <= 0 &&
        ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2) <= 0) {
        //여기까지 보면 각도 상으로는 만날 수 있는 조건을 갖춤
        if ((x1 > x3 && x1 > x4 && x2 > x3 && x2 > x4) ||
            (x3 > x1 && x3 > x2 && x4 > x1 && x4 > x2)) return false;
        else if ((y1 > y3 && y1 > y4 && y2 > y3 && y2 > y4) ||
            (y3 > y1 && y3 > y2 && y4 > y1 && y4 > y2)) return false;
        else
            return true;
    }
    return false; //애초에 양수면 교차X
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) //유니온 파인드 할 때 편하라고 1-indexed
        cin >> L[i].x1 >> L[i].y1 >> L[i].x2 >> L[i].y2;
    
    for (int i = 1; i <= n; i++) r[i] = i; //root 자기 자신으로 초기화
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (isCross(L[i].x1, L[i].y1, L[i].x2, L[i].y2, L[j].x1, L[j].y1, L[j].x2, L[j].y2))
                join(i, j);
        }
    }
    //여기까지 join해도, r[]이 최상위 부모노드를 가지지 않음. 따라서 추가 순회하면서 카운트
    for (int i = 1; i <= n; i++)
        cnt[getParent(i)]++;
    /* 부모 최신화와, 카운팅 분리
    for (int i = 1; i <= n; i++)
        int tmp = getParent(i);
    
    for (int i = 1; i <= n; i++)
        cnt[r[i]]++;
        */
    
    int groupCnt = 0, maxCnt = 0;
    for (int i = 1; i <= n; i++) {
        //cnt[]가 0이 아닌 곳이 그룹인 곳
        if (cnt[i] > 0) groupCnt++;
 
        if (cnt[i] > maxCnt) 
            maxCnt = cnt[i];    
    }
    cout << groupCnt << '\n' << maxCnt;
    return 0;
}
cs





복습


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<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
struct POT {
    ll x, y;
    POT operator - (POT a) { return{x-a.x, y-a.y}; }
};
 
struct LINE {
    POT st, en;
}l[3001];
 
int n, r[3001], cnt[3001];
ll ccw(POT p1, POT p2) {
    ll ret = p1.x*p2.y - p1.y*p2.x;
    if (ret == 0) return 0;
    else if (ret > 0) return 1;
    else return -1;
}
ll ccw(POT p1, POT p2, POT p3) {
    return ccw(p2 - p1, p3 - p1);
}
int getPar(int a) {
    if (r[a] == a) return a;
    else
        return r[a] = getPar(r[a]);
}
void join(int a, int b) {
    a = getPar(a);
    b = getPar(b);
    if (a < b) 
        r[b] = a;
    
    else 
        r[a] = b;
    
}
bool isCross(LINE l1, LINE l2) {
    if (ccw(l1.st, l1.en, l2.st) * ccw(l1.st, l1.en, l2.en) <= 0 &&
        ccw(l2.st, l2.en, l1.st) * ccw(l2.st, l2.en, l1.en) <= 0) {
        if ((l1.st.x < l2.st.x && l1.st.x < l2.en.x && l1.en.x < l2.st.x&&l1.en.x < l2.en.x) ||
            (l2.st.x < l1.st.x && l2.st.x < l1.en.x && l2.en.x < l1.st.x&&l2.en.x < l1.en.x)) return false;
        if ((l1.st.y < l2.st.y && l1.st.y < l2.en.y && l1.en.y < l2.st.y&&l1.en.y < l2.en.y) ||
            (l2.st.y < l1.st.y && l2.st.y < l1.en.y && l2.en.y < l1.st.y&&l2.en.y < l1.en.y)) return false;
        return true;
    }
    return false; //안 만남
}
int main(void) {
    cin >> n;
    for(int i = 0 ; i < n ; i++)
        cin >> l[i].st.x >> l[i].st.y >> l[i].en.x >> l[i].en.y;
    
    for (int i = 0; i < n; i++) 
        r[i] = i; //자기 자신으로 최상위 부모 초기화
    
 
    //겹치면 union
    for (int i = 0; i < n; i++) 
        for (int j = i+1; j < n; j++) {
            if (isCross(l[i], l[j])) {
                join(i, j);
            }
        }
    
    for (int i = 0; i < n; i++)
        cnt[getPar(i)]++;
 
    int mx = -1, ct = 0;
    for (int i = 0; i < n; i++) {
        if (mx < cnt[i]) 
            mx = cnt[i];
        if (cnt[i] > 0) ct++;
    }
    printf("%d\n%d", ct, mx);
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1485 정사각형 C++  (0) 2019.08.11
백준 6439 교차 C++  (0) 2019.08.11
백준 2166 다각형의 면적 C++  (0) 2019.08.10
백준 11758 CCW C++  (0) 2019.08.10
백준 1941 소문난 칠공주 C++  (0) 2019.08.10

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



CCW를 활용하여 면적을 구하는 문제이다.


여러개의 좌표가 주어질 때, CCW를 활용해서 면적을 구하는 방법에도 여러가지가 있다.



필자가 구현한 것처럼, 다각형을 이루는 점 하나를 중심으로 CCW를 돌리는 방법이 있고,


원점과 같은 다각형 외부의 정점을 잡아서 CCW를 수행하는 방법이 있다.


CCW 함수가 시행되는 횟수의 차이가 있을 것이다.



이 문제에서 또 유의할 것은, 어떤 자료형을 사용할 것이냐이다. n이 10만을 넘어가기 때문에, 면적을 구하는 과정에서 int 범위 밖으로 나갈 수 있다.


따라서 long long을 사용해주면 되겠다.



면적을 구하는 중간에 음수가 나오더라도, 계산 중간중간에 나오는 양수들 때문에 알아서 절댓값은 넓이만큼 구해지게 된다. 따라서 결과에서만 절댓값을 취하고, 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
//좌표값 정수
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
struct POT {
    ll x, y;
}p[10001];
int n;
 
ll ccw(POT p1, POT p2, POT p3) {
    ll ret;
    ret = (p1.x*p2.y + p2.x*p3.y + p3.x* p1.y) - 
        (p1.y*p2.x + p2.y*p3.x + p3.y* p1.x);
    return ret;
}
 
int main(void) {
    cin >> n;
    for(int i = 0 ; i < n ; i++)
        cin >> p[i].x >> p[i].y;
    ll Sum = 0;
    for (int i = 0; i < n-1; i++)
        Sum += ccw(p[0], p[i], p[i + 1]);
    printf("%.1lf", abs(Sum / 2.0));
    return 0;
}
cs



기준벡터를 원점으로 평행이동 시켜서



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
//좌표값 정수
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
struct POT {
    ll x, y;
    POT operator - (POT a) { return{x-a.x, y-a.y}; }
}p[10001];
 
int n;
ll ccw(POT p1, POT p2) {
    return p1.x*p2.y - p1.y*p2.x;
}
ll ccw(POT p1, POT p2, POT p3) {
    return ccw(p2 - p1, p3 - p1);
}
 
int main(void) {
    cin >> n;
    for(int i = 0 ; i < n ; i++)
        cin >> p[i].x >> p[i].y;
    ll Sum = 0;
    for (int i = 0; i < n-1; i++)
        Sum += ccw(p[0], p[i], p[i + 1]);
    printf("%.1lf", abs(Sum / 2.0));
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 6439 교차 C++  (0) 2019.08.11
백준 2162: 선분 그룹 C++  (0) 2019.08.11
백준 11758 CCW C++  (0) 2019.08.10
백준 1941 소문난 칠공주 C++  (0) 2019.08.10
백준 2023 신기한 소수 C++  (0) 2019.08.10

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



CCW 알고리즘을 그대로 구현해주면 된다.


p1 p2 p3가 있을 때, 순서대로 선분을 만들면 선분 p1p2, 선분 p2p3가 생긴다.


나중에 생긴 선분 p2p3가 선분 p1p2에 대해서 어떻게 위치하고 있는지 생각해보면 된다.


p2를 p1으로 평행이동해서 벡터를 생각해본다면 이해가 좀 더 쉽다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//좌표값 정수
#include<iostream>
using namespace std;
typedef long long ll;
struct POT {
    int x, y;
};
int ccw(POT p1, POT p2, POT p3) {
    ll ret;
    ret = (p1.x*p2.y + p2.x*p3.y + p3.x* p1.y) - 
        (p1.y*p2.x + p2.y*p3.x + p3.y* p1.x);
    if (ret < 0) return -1;
    else if (ret == 0) return 0;
    else return 1;
}
int main(void) {
    POT p1, p2, p3;
    cin >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y;
    cout << ccw(p1, p2, p3);
    return 0;
}
cs






1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
 
using namespace std;
 
int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    if ((x1*y2 + x2 * y3 + x3 * y1) - (y1*x2 + y2 * x3 + y3 * x1) > 0) return 1;
    else if ((x1*y2 + x2 * y3 + x3 * y1) - (y1*x2 + y2 * x3 + y3 * x1) < 0) return -1;
    else
        return 0;
}
 
int main(void) {
 
    int x1, y1, x2, y2, x3, y3;
 
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
 
    cout << ccw(x1, y1, x2, y2, x3, y3) << '\n';
    
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2162: 선분 그룹 C++  (0) 2019.08.11
백준 2166 다각형의 면적 C++  (0) 2019.08.10
백준 1941 소문난 칠공주 C++  (0) 2019.08.10
백준 2023 신기한 소수 C++  (0) 2019.08.10
백준 2661 좋은수열 C++  (0) 2019.08.09

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



오답에서 적었듯이, 일반적인 dfs로는 해결하기 까다로운 문제이다.



우선, 들어오는 입력만으로는 (y/s)여부 만으로는 그 성분의 자리가 어디인지 알 수 없다.


따라서 자리번호를 매겼다.


그리고 그 자리번호를 7개 선택해서, 뽑힌 7개의 자리번호가 인접한 상태이고, S를 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
#include<iostream>
#include<string>
#include<queue>
using namespace std;
char m[6][6];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int seat[6][6];
bool isused[25];
int st = 0, arr[8], dis[6][6], map[6][6];
queue<pair<int, int> > q;
int res = 0;
bool endFlag = false;
 
void process() {
    int idx = 0;
    endFlag = false;
    for (int i = 0; i < 5; i++) { //뽑힌 학생의 자리번호 1로
        for (int j = 0; j < 5; j++) {
            if (seat[i][j] == arr[idx]) {
                map[i][j] = 1;
                idx++;
                //if (idx == 7) return; 이 구문 때문에 아래 카운트가 안먹혀서 시간낭비
            }
        }
    }
 
    int sCnt = 0;
    //소영 카운트
    for (int i = 0; i < 5; i++) 
        for (int j = 0; j < 5; j++) 
            if (map[i][j] == 1 && m[i][j] == 'S') sCnt++;
        
    
    if (sCnt < 4) endFlag = true;
}
void init() {
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++) {
            map[i][j] = 0; //자리번호 배열 초기화
            dis[i][j] = -1; //방문처리 배열
        }
    
}
 
void bfs(pair<int, int> start) {
    q.push(start);
    dis[start.first][start.second]++;
    int cnt = 0;
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            if (nr < 0 || nc < 0 || nr >= 5 || nc >= 5) continue;
            if (dis[nr][nc] >= 0 || map[nr][nc] != 1) continue;
            q.push({ nr, nc });
            cnt++;
            dis[nr][nc] = cnt;
        }
    }
    
    if (cnt == 6) //7명이 붙어 앉은 경우
        res++;
    
}
 
void pick(int k) {
    if (k == 7) { //1. 자리번호 7개 선택
    
        init(); 
 
        process();
        if (endFlag) return;
 
        for (int i = 0; i < 5; i++) 
            for (int j = 0; j < 5; j++) 
                if (map[i][j] == 1 && dis[i][j] < 0) 
                    bfs({ i, j }); 
        
        return;
    }
    
    if (k == 0) st = 0;
    for (int i = st; i < 25; i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            pick(k + 1);
            isused[i] = false;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int cnt = 0;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++) {
            cin >> m[i][j];
            seat[i][j] = cnt;
            cnt++;
        }
    
    pick(0);
    cout << res;
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2166 다각형의 면적 C++  (0) 2019.08.10
백준 11758 CCW C++  (0) 2019.08.10
백준 2023 신기한 소수 C++  (0) 2019.08.10
백준 2661 좋은수열 C++  (0) 2019.08.09
백준 2210번: 숫자판 점프 (C++)  (0) 2019.08.09

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



자리수가 추가될 때마다 현재 상태의 수가 소수인지 아닌지를 판별해주면 된다.


가령 7331을 만들기 위해서, 처음에 7을 골라서 확인하고, 73을 확인하고, 733을 확인하고 ... 이런 흐름이다.


처음에 2를 고르고, 다음에 21이 나왔을텐데, 21은 소수가 아니기 때문에 21#$!@#는 더이상 확인할 필요가 없는 것이다.



신경써줄 부분은, 소수 판별 함수에서 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
/*특정 수열이 만들어질 때마다
소수 여부 판별해서, 소수 아닐 때만 이어서 진행*/
#include<iostream>
#include<vector>
using namespace std;
int n, arr[10], st = 0;
bool isPrime(int val) {
    if (val == 1) return false; //1은 소수가 아님
    for (int i = 2; i*i <= val; i++)
        if (val % i == 0) return false;
    return true;
}
void backTracking(int k, int num) {
    
    //소수검사
    if (k != 0) 
        if (!isPrime(num)) return;
    
    if (k == n) {
        cout << num << '\n';
        return;
    }
 
    //가장 큰 자리수로 0못오게
    if (k == 0)st = 1;
    else
        st = 0;
 
    for (int i = st; i <= 9; i++) 
        backTracking(k + 1, num * 10 + i);
}
int main(void) {
    cin >> n;
    backTracking(0,0);
    
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 11758 CCW C++  (0) 2019.08.10
백준 1941 소문난 칠공주 C++  (0) 2019.08.10
백준 2661 좋은수열 C++  (0) 2019.08.09
백준 2210번: 숫자판 점프 (C++)  (0) 2019.08.09
백준 2589번: 보물섬 (C++)  (0) 2019.08.09

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



1,2,3 세개의 숫자를 활용해서 길이 n의 수열을 만들면 된다.


기본적으로 여기까지는 백트래킹을 활용해서 진행해주면 된다.


이후에 나쁜 수열을 걸러내는 과정에서 substr을 적절히 활용해주면 되겠다.


주의할 점은, 검사를 재귀의 진입 부분에서 해야 한다는 것이다.



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<set>
#include<string>
using namespace std;
int n, a[3] = { 1,2,3 }, arr[81];
string str = "";
set<string> ans;
bool ef = false;
void backTracking(int k) {
 
    str = "";
    for (int i = 0; i < k; i++)
        str += (arr[i] + '0');
    
    //부분 수열 존재 검사
    for (int i = 1; i <= k / 2; i++) { //수열 길이 절반까지만 확인하면 됨
        for (int j = 0; j <= k - 2 * i; j++) {
            if (str.substr(j, i) == str.substr(j + i, i)) {
                return;
            }
        }
    }
 
    //길이 n 완성
    if (k == n) {
        for (int i = 0; i < k; i++)
            cout << arr[i];
        exit(0); //가장 먼저 나오는 게 제일 작은 수열
        return;
    }
 
    for (int i = 0; i < 3; i++) {
        arr[k] = a[i];
        backTracking(k + 1);
        if (ef) return;
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    backTracking(0);
 
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1941 소문난 칠공주 C++  (0) 2019.08.10
백준 2023 신기한 소수 C++  (0) 2019.08.10
백준 2210번: 숫자판 점프 (C++)  (0) 2019.08.09
백준 2589번: 보물섬 (C++)  (0) 2019.08.09
백준 17069번: 파이프 옮기기 2 (C++)  (0) 2019.08.09

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


5 * 5의 격자판이 주어진다.


그 격자판에 있는 정수들을 활용해서 길이 6의 수열을 만들어야 한다.


이 때 사용했던 숫자라도 중복해서 사용할 수 있다.


또한, 숫자는 직전에 선택했던 숫자의 동서남북 방향에 위치한 숫자중에 하나로 선택해야 한다.



중복 제거를 간편하게 하기 위해서 set을 사용했다.



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<iostream>
#include<set>
#include<string>
using namespace std;
int m[6][6];
string str = "";
set<int> res;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void dfs(int depth, int row, int col, int cur) {
    if (depth == 5) { //depth가 0일때 이미 처음게 골라져있는 상태임
        res.insert(cur);
        
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        int nr = row + dr[i];
        int nc = col + dc[i];
        if (nr < 0 || nc < 0 || nr >= 5 || nc >= 5) continue;
        dfs(depth + 1, nr, nc, cur * 10 + m[nr][nc]);
    }
}
 
int main(void) {
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            cin >> m[i][j];
 
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            dfs(0, i, j, m[i][j]);
        }
    }
 
    cout << res.size();
 
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2023 신기한 소수 C++  (0) 2019.08.10
백준 2661 좋은수열 C++  (0) 2019.08.09
백준 2589번: 보물섬 (C++)  (0) 2019.08.09
백준 17069번: 파이프 옮기기 2 (C++)  (0) 2019.08.09
백준 17070번: 파이프 옮기기 1 (C++)  (0) 2019.08.09

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

 

2589번: 보물섬

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지

www.acmicpc.net

육지가 될 수 있는 땅 한 칸 한 칸에 대해 개별적으로 bfs를 수행해주면 된다.

 

방문처리를 거리 측정으로 하면서 최댓값을 구해주면 된다.

 

 

 

저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2661 좋은수열 C++  (0) 2019.08.09
백준 2210번: 숫자판 점프 (C++)  (0) 2019.08.09
백준 17069번: 파이프 옮기기 2 (C++)  (0) 2019.08.09
백준 17070번: 파이프 옮기기 1 (C++)  (0) 2019.08.09
백준 14890번: 경사로 (C++)  (0) 2019.08.09

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


간단한 DP 문제이다.


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
//1-indexed
#include<iostream>
 
using namespace std;
typedef long long ll;
ll m[33][33], d[33][33][3];
int main(void) {
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> m[i][j];
 
    d[1][2][0] = 1; //초기에는 1,2로 가로로 들어가는 방법 한가지
    d[1][2][1] = 0;
    d[1][2][2] = 0;
 
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 1 && j <= 2) continue;
            if (m[i][j] == 1)  //현재 지점이 벽이면, 그 지점까지 오는 경로는 모두0 (그냥 스킵해도 초기화 0으로 되어있음)
                continue;
            
            if (m[i][j - 1] == 1) d[i][j][0] = 0; //가로로 들어오는 방법이 없는 경우 = 그 바로 왼쪽 벽인 경우
            else
                d[i][j][0] = d[i][j - 1][0] + d[i][j - 1][2];
 
            if (m[i - 1][j] == 1) d[i][j][1] = 0; //세로로 들어오는 방법이 없는 경우 = 그 바로 위쪽이 벽인 경우
            else
                d[i][j][1] = d[i - 1][j][1] + d[i - 1][j][2];
 
            if (m[i - 1][j] == 1 || m[i][j - 1] == 1) d[i][j][2] = 0; //대각으로 오는 방법이 없는 경우 = 날개 둘 중 하나라도 벽인 경우
            else
                d[i][j][2] = d[i - 1][j - 1][0] + d[i - 1][j - 1][1] + d[i - 1][j - 1][2];
        }
    }
 
    cout << d[n][n][0] + d[n][n][1] + d[n][n][2]; //모든 방향으로 들어오는 경우의 합
 
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2210번: 숫자판 점프 (C++)  (0) 2019.08.09
백준 2589번: 보물섬 (C++)  (0) 2019.08.09
백준 17070번: 파이프 옮기기 1 (C++)  (0) 2019.08.09
백준 14890번: 경사로 (C++)  (0) 2019.08.09
백준 14889번: 스타트와 링크 (C++)  (0) 2019.08.07

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


삼성 상시 검정 A형 기출 문제이다. 삼성의 문제이니만큼 완전탐색 혹은 시뮬레이션 문제일 것이다.


하지만 이를 생각하더라도, 동적계획법을 통해서 너무 쉬운 풀이가 가능하기 때문에 DP를 활용해서 간단하게 풀었다.


정점 i,j에 도착할 때, 어떤 방향 상태를 가지고 도착하는지 생각해보면, 세가지가 가능함을 알 수 있다.


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
//1-indexed
#include<iostream>
 
using namespace std;
int m[18][18], d[18][18][3];
int main(void) {
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> m[i][j];
 
    d[1][2][0] = 1; //초기에는 1,2로 가로로 들어가는 방법 한가지
    d[1][2][1] = 0;
    d[1][2][2] = 0;
 
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 1 && j <= 2) continue;
            if (m[i][j] == 1)  //현재 지점이 벽이면, 그 지점까지 오는 경로는 모두0 (그냥 스킵해도 초기화 0으로 되어있음)
                continue;
            
            if (m[i][j - 1] == 1) d[i][j][0] = 0; //가로로 들어오는 방법이 없는 경우 = 그 바로 왼쪽 벽인 경우
            else
                d[i][j][0] = d[i][j - 1][0] + d[i][j - 1][2];
 
            if (m[i - 1][j] == 1) d[i][j][1] = 0; //세로로 들어오는 방법이 없는 경우 = 그 바로 위쪽이 벽인 경우
            else
                d[i][j][1] = d[i - 1][j][1] + d[i - 1][j][2];
 
            if (m[i - 1][j] == 1 || m[i][j - 1] == 1) d[i][j][2] = 0; //대각으로 오는 방법이 없는 경우 = 날개 둘 중 하나라도 벽인 경우
            else
                d[i][j][2] = d[i - 1][j - 1][0] + d[i - 1][j - 1][1] + d[i - 1][j - 1][2];
        }
    }
 
    cout << d[n][n][0] + d[n][n][1] + d[n][n][2]; //모든 방향으로 들어오는 경우의 합
 
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2589번: 보물섬 (C++)  (0) 2019.08.09
백준 17069번: 파이프 옮기기 2 (C++)  (0) 2019.08.09
백준 14890번: 경사로 (C++)  (0) 2019.08.09
백준 14889번: 스타트와 링크 (C++)  (0) 2019.08.07
백준 14891번: 톱니바퀴 (C++)  (0) 2019.08.07

+ Recent posts

티스토리툴바