반응형

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

 

20183번: 골목 대장 호석 - 효율성 2

첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 그래프를 입력받고, vector<pair<int, int>> list[ 100001 ] 배열에 저장합니다. 

 

2. 매개 변수를 활용하여 이동할 수 있는 골목의 최대 비용을 정해서 dijkstra를 돌립니다.

 

3. ans를 -1로 초기화하고, 만약 도착지에 도착하게 되면 ans에 해당 매개 변수 값을 저장합니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<vector>
#define ll long long
 
using namespace std;
 
int N, M;
int A, B;
ll C;
vector<pair<int, int>> list[100001];
int s, e;
int ans = -1;
ll visited[100001];
 
bool dijkstra(int m)
{
    fill(visited, visited + N + 1, 111111111111111);
    priority_queue<pair<ll, int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
 
    pq.push({ 0,A });
 
    while (!pq.empty()) {
        const ll cost = pq.top().first;
        const int cur = pq.top().second;
        pq.pop();
 
        if (cost > C) continue;
 
        if (cur == B) {
            return true;
        }
 
        if (visited[cur] < cost) continue;
        visited[cur] = cost;
 
        for (auto& next : list[cur]) {
            if (visited[next.second] > cost + next.first && next.first <= m) {
                visited[next.second] = cost + next.first;
                pq.push({ cost + next.first, next.second });
            }
        }
    }
 
    return false;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M >> A >> B >> C;
    s = 1;
 
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        list[u].push_back({ w,v });
        list[v].push_back({ w,u });
        e = max(e, w);
    }
 
    while (s <= e) {
        int m = (s + e) / 2;
 
        if (dijkstra(m)) {
            ans = m;
            e = m - 1;
        }
        else {
            s = m + 1;
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 5569번 - 출근 경로 (C++)  (0) 2023.09.18
[ 백준 ] 13398번 - 연속합 2 (C++)  (0) 2023.09.17
[ 백준 ] 5549번 - 행성 탐사 (C++)  (0) 2023.09.15
[ 백준 ] 20160번 - 야쿠르트 아줌마 야쿠르트 주세요 (C++)  (0) 2023.09.14
[ 백준 ] 9084번 - 동전 (C++)  (0) 2023.09.13
반응형

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

 

5549번: 행성 탐사

상근이는 우주선을 타고 인간이 거주할 수 있는 행성을 찾고 있다. 마침내, 전 세계 최초로 인간이 거주할 수 있는 행성을 찾았다. 이 행성은 정글, 바다, 얼음이 뒤얽힌 행성이다. 상근이는 이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 지도를 입력받고, sum[ i ][ j ] = sum[ i ][ j - 1 ] + sum[ i - 1 ][ j ] - sum[ i - 1 ][ j - 1 ] + arr[ i ][ j ]를 통해 구간합을 저장합니다.

 

2. 좌표 a, b, c, d를 입력받고,  ans = sum[ c ][ d ] - sum[ a - 1 ][ d ] - sum[ c ][ b - 1 ] + sum[ a - 1 ][ b - 1 ]을 통해 해당 좌표 내의 J, O, I의 개수를 구해 출력합니다. 

 

[ 소스코드 ]

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
#include<iostream>
#include<string>
 
using namespace std;
 
struct node {
    int J, O, I;
};
 
node sum[1001][1001];
int M, N, K;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> M >> N >> K;
 
    for (int i = 1; i <= M; i++) {
        string temp;
        cin >> temp;
        for (int j = 0; j < N; j++) {
            sum[i][j + 1].J = sum[i][j].J + sum[i - 1][j + 1].J - sum[i - 1][j].J;
            sum[i][j + 1].O = sum[i][j].O + sum[i - 1][j + 1].O - sum[i - 1][j].O;
            sum[i][j + 1].I = sum[i][j].I + sum[i - 1][j + 1].I - sum[i - 1][j].I;
            if (temp[j] == 'J') {
                sum[i][j + 1].J++;
            }
            else if (temp[j] == 'O') {
                sum[i][j + 1].O++;
            }
            else {
                sum[i][j + 1].I++;
            }
        }
    }
 
    for (int i = 0; i < K; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
 
        node ans = { 0 };
 
        ans.J = sum[c][d].J - sum[a - 1][d].J - sum[c][b - 1].J + sum[a - 1][b - 1].J;
        ans.O = sum[c][d].O - sum[a - 1][d].O - sum[c][b - 1].O + sum[a - 1][b - 1].O;
        ans.I = sum[c][d].I - sum[a - 1][d].I - sum[c][b - 1].I + sum[a - 1][b - 1].I;
 
        cout << ans.J << ' ' << ans.O << ' ' << ans.I << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 13398번 - 연속합 2 (C++)  (0) 2023.09.17
[ 백준 ] 20183번 - 골목 대장 호석 - 효율성 2 (C++)  (0) 2023.09.16
[ 백준 ] 20160번 - 야쿠르트 아줌마 야쿠르트 주세요 (C++)  (0) 2023.09.14
[ 백준 ] 9084번 - 동전 (C++)  (0) 2023.09.13
[ 백준 ] 22116번 - 창영이와 퇴근 (C++)  (0) 2023.09.12
반응형

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

 

20160번: 야쿠르트 아줌마 야쿠르트 주세요

첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다. 그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 그래프를 입력받고, vector<pair<int, int>> list[ 10001 ] 배열에 저장합니다. 

 

2. dijkstra를 이용하여 야쿠르트 아줌마의 정점별 도착 거리를 구해 저장합니다.

 

3. dijkstra를 이용하여 나의 정점별 도착 거리를 visited 배열에 저장하고, for문을 통해 돌면서 아줌마의 도착 시점보다 내 도착 시점이 빠르거나 같은 지점을 ans에 저장합니다.

 

4. 만약 어느 정점에도 도착할 수 없다면 -1을 출력하고, 그렇지 않다면 ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<vector>
#define ll long long
 
using namespace std;
 
int V, E;
vector<pair<int, int>> list[10001];
int arr[10];
ll dist[10];
int start;
ll visited[10001];
 
int dijkstra(int s, int e)
{
    fill(visited, visited + V + 1, 11111111111);
    visited[s] = 0;
 
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
 
    pq.push({ 0,s });
 
    while (!pq.empty()) {
        const int cur = pq.top().second;
        const int dist = pq.top().first;
        pq.pop();
 
        if (cur == e) {
            return dist;
        }
 
        if (visited[cur] < dist) continue;
        visited[cur] = dist;
 
        for (auto& next : list[cur]) {
            if (visited[next.second] > dist + next.first) {
                visited[next.second] = dist + next.first;
                pq.push({ visited[next.second], next.second });
            }
        }
    }
 
    return -1;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> V >> E;
 
    for (int i = 0; i < E; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        list[u].push_back({ w,v });
        list[v].push_back({ w,u });
    }
 
    for (int i = 0; i < 10; i++) {
        cin >> arr[i];
    }
 
    cin >> start;
 
    int cnt = 1;
 
    for (int i = 0; i < 9; i++) {
        int next = dijkstra(arr[i], arr[i + cnt]);
        while (next == -1) {
            dist[i + cnt] = -1;
            cnt++;
            if (i + cnt == 10) break;
            next = dijkstra(arr[i], arr[i + cnt]);
        }
        if (i + cnt == 10) break;
        dist[i + cnt] = dist[i] + dijkstra(arr[i], arr[i + cnt]);
        i = i + cnt - 1;
        cnt = 1;
    }
 
    dijkstra(start, 0);
    int ans = 111111;
 
    for (int i = 0; i < 10; i++) {
        if (visited[arr[i]] <= dist[i]) {
            ans = min(ans, arr[i]);
        }
    }
 
    if (ans == 111111) cout << -1;
    else cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 20183번 - 골목 대장 호석 - 효율성 2 (C++)  (0) 2023.09.16
[ 백준 ] 5549번 - 행성 탐사 (C++)  (0) 2023.09.15
[ 백준 ] 9084번 - 동전 (C++)  (0) 2023.09.13
[ 백준 ] 22116번 - 창영이와 퇴근 (C++)  (0) 2023.09.12
[ 백준 ] 3755번 - Double Queue (C++)  (0) 2023.09.11
반응형

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

 

9084번: 동전

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/20

 

[ 백준 ] 12865번 - 평범한 배낭 (C++)

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1

rudalsd.tistory.com

 

1. 점화식 dp[ i ][ j ] = dp[ i ][ j - coin[ i ] ] + dp[ i - 1 ][ j ] 을 통해 방법의 수를 구합니다.

 

2. dp[ N ][ M ] 을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int T, N, M;
int arr[21];
int dp[21][10001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    while (T--) {
        cin >> N;
 
        for (int i = 1; i <= N; i++) {
            cin >> arr[i];
            dp[i][0] = 1;
            for (int j = 1; j <= M; j++) {
                dp[i][j] = 0;
            }
        }
 
        cin >> M;
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (j < arr[i]) {
                    dp[i][j] = dp[i - 1][j];
                }
                else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - arr[i]];
                }
            }
        }
 
        cout << dp[N][M] << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 5549번 - 행성 탐사 (C++)  (0) 2023.09.15
[ 백준 ] 20160번 - 야쿠르트 아줌마 야쿠르트 주세요 (C++)  (0) 2023.09.14
[ 백준 ] 22116번 - 창영이와 퇴근 (C++)  (0) 2023.09.12
[ 백준 ] 3755번 - Double Queue (C++)  (0) 2023.09.11
[ 백준 ] 15918번 - 랭퍼든 수열쟁이야!! (C++)  (0) 2023.09.10
반응형

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

 

22116번: 창영이와 퇴근

A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 격자를 입력받고, arr 배열에 저장합니다.

 

2. visited 배열을 만들어 해당 구간에 도착했을 때 경사로 차가 가장 적었을 때의 값을 저장합니다.

 

3. ans에 경사로 차 중 가장 큰 값을 저장합니다.

 

4. 다익스트라를 이용하여 경사로의 높이차가 작은 구간부터 방문하고, N - 1, N - 1 좌표에 도착하면 ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<cmath>
 
using namespace std;
 
struct node {
    int y, x, h;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.h < right.h;
    }
};
 
int N;
int arr[1000][1000];
int visited[1000][1000];
int ans;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
            visited[i][j] = 1111111111;
        }
    }
 
    priority_queue<node, vector<node>, cmp> pq;
    pq.push({ 0,0,0 });
    visited[0][0] = 0;
 
    while (!pq.empty()) {
        const int y = pq.top().y;
        const int x = pq.top().x;
        const int h = pq.top().h;
        pq.pop();
 
        if (visited[y][x] < h) continue;
 
        ans = max(ans, h);
 
        if (y == N - 1 && x == N - 1) {
            cout << ans;
            return 0;
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                int diff = abs(arr[y][x] - arr[yy][xx]);
                if (visited[yy][xx] > diff) {
                    visited[yy][xx] = diff;
                    pq.push({ yy,xx,diff });
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 20160번 - 야쿠르트 아줌마 야쿠르트 주세요 (C++)  (0) 2023.09.14
[ 백준 ] 9084번 - 동전 (C++)  (0) 2023.09.13
[ 백준 ] 3755번 - Double Queue (C++)  (0) 2023.09.11
[ 백준 ] 15918번 - 랭퍼든 수열쟁이야!! (C++)  (0) 2023.09.10
[ 백준 ] 16940번 - BFS 스페셜 저지 (C++)  (0) 2023.09.09
반응형

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

 

3755번: Double Queue

The new founded Balkan Investment Group Bank (BIG-Bank) opened a new office in Bucharest, equipped with a modern computing environment provided by IBM Romania, and using modern information technologies. As usual, each client of the bank is identified by a

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. priority_queue를 두 개 선언해, 오름차순과 내림차순으로 각각 저장합니다.

 

2. visited 배열을 만들어 현재 K 고객이 서비스를 이용한 상태인지 그렇지 않은 상태인지 저장합니다.

 

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int visited[1000000];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int cmd;
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<>> greater;
    priority_queue<pair<int, int>, vector<pair<int, int>>, less<>> less;
 
    while (1) {
        cin >> cmd;
 
        if (cmd == 1) {
            int K, P;
            cin >> K >> P;
            greater.push({ P,K });
            less.push({ P,K });
            visited[K] = 0;
        }
        else if (cmd == 2) {
            while (1) {
                if (less.empty()) {
                    cout << 0 << '\n';
                    break;
                }
                const int K = less.top().second;
                less.pop();
                if (visited[K] != 1) {
                    visited[K] = 1;
                    cout << K << '\n';
                    break;
                }
            }
        }
        else if (cmd == 3) {
            while (1) {
                if (greater.empty()) {
                    cout << 0 << '\n';
                    break;
                }
                const int K = greater.top().second;
                greater.pop();
                if (visited[K] != 1) {
                    visited[K] = 1;
                    cout << K << '\n';
                    break;
                }
            }
        }
        else {
            return 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 9084번 - 동전 (C++)  (0) 2023.09.13
[ 백준 ] 22116번 - 창영이와 퇴근 (C++)  (0) 2023.09.12
[ 백준 ] 15918번 - 랭퍼든 수열쟁이야!! (C++)  (0) 2023.09.10
[ 백준 ] 16940번 - BFS 스페셜 저지 (C++)  (0) 2023.09.09
[ 백준 ] 16936번 - 나3곱2 (C++)  (0) 2023.09.08
반응형

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

 

15918번: 랭퍼든 수열쟁이야!!

세 자연수 n, x, y가 주어진다. (2 ≤ n ≤ 12, 1 ≤ x < y ≤ 2n, 1 ≤ y-x-1 ≤ n)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. n, x, y를 입력받고, arr[ x ] = arr [ y ] = y - x - 1로 초기화합니다.

 

2. 백트래킹을 이용하여 수열의 자리를 채우고, 수열이 완성되면 ans++를 해줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int n, x, y;
int arr[25];
int visited[13];
int ans;
 
void dfs(int level)
{
    if (level == 2 * n + 1) {
        ans++;
        return;
    }
    if (arr[level]) dfs(level + 1);
 
    for (int i = 1; i <= n; i++) {
        if (visited[i] == 0 && level + i + 1 <= 2 * n && arr[level] == 0 && arr[level + i + 1] == 0) {
            visited[i] = 1;
            arr[level] = i;
            arr[level + i + 1] = i;
            dfs(level + 1);
            visited[i] = 0;
            arr[level] = 0;
            arr[level + i + 1] = 0;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> x >> y;
 
    arr[x] = arr[y] = y - x - 1;
    visited[y - x - 1] = 1;
 
    dfs(1);
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 22116번 - 창영이와 퇴근 (C++)  (0) 2023.09.12
[ 백준 ] 3755번 - Double Queue (C++)  (0) 2023.09.11
[ 백준 ] 16940번 - BFS 스페셜 저지 (C++)  (0) 2023.09.09
[ 백준 ] 16936번 - 나3곱2 (C++)  (0) 2023.09.08
[ 백준 ] 11567번 - 선진이의 겨울 왕국 (C++)  (0) 2023.09.07
반응형

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

 

16940번: BFS 스페셜 저지

올바른 순서는 1, 2, 3, 4와  1, 3, 2, 4가 있다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 그래프를 입력받고, bfs를 돌면서 각 노드의 부모 노드와 깊이를 저장합니다.

 

2. 방문 순서를 입력 받으면서 해당 노드의 순서를 arr 배열에 저장하고, 바로 직전 노드를 temp 변수에 저장합니다.

 

3. 첫 방문 순서가 1이 아니라면 0을 출력합니다.

 

4. 직전 노드의 부모 노드와 현재 노드의 부모 노드의 순서를 비교하고, 진전 노드와 현재 노드의 깊이를 비교하여 직전 노드의 값들이 현재 노드보다 더 크다면 0을 출력하고, 그렇지 않다면 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
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
int N;
vector<int> list[100001];
int visited[100001];
int arr[100001];
int parent[100001];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
 
        list[u].push_back(v);
        list[v].push_back(u);
    }
 
    queue<pair<int, int>> q;
 
    q.push({ 1,1 });
 
    while (!q.empty()) {
        const int cur = q.front().first;
        const int cnt = q.front().second;
        q.pop();
 
        visited[cur] = cnt;
 
        for (auto next : list[cur]) {
            if (visited[next] == 0) {
                parent[next] = cur;
                visited[next] = cnt + 1;
                q.push({ next,cnt + 1 });
            }
        }
    }
 
    int temp = 0;
 
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        arr[num] = i;
 
        if ((i == 0 && num != 1) || arr[parent[num]] < arr[parent[temp]] || visited[num] < visited[temp]) {
            cout << 0;
            return 0;
        }
        
        temp = num;
    }
 
    cout << 1;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 3755번 - Double Queue (C++)  (0) 2023.09.11
[ 백준 ] 15918번 - 랭퍼든 수열쟁이야!! (C++)  (0) 2023.09.10
[ 백준 ] 16936번 - 나3곱2 (C++)  (0) 2023.09.08
[ 백준 ] 11567번 - 선진이의 겨울 왕국 (C++)  (0) 2023.09.07
[ 백준 ] 3184번 - 양 (C++)  (0) 2023.09.06
반응형

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

 

16936번: 나3곱2

나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수열을 입력받고, arr에 저장합니다.

 

2. 재귀함수를 이용하여 수열을 채워 나가는데, 이전 값에 2를 곱한 값이나 3을 나눈 값이 현재 수열의 값일 때만 수열에 넣어줍니다.

 

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N;
ll arr[100];
ll ans[100];
int visited[100];
bool flag = false;
 
void dfs(int level)
{
    if (flag) return;
 
    if (level == N) {
        for (int i = 0; i < N; i++) {
            cout << ans[i] << ' ';
        }
 
        flag = true;
    }
 
    for (int i = 0; i < N; i++) {
        if (visited[i] == 0 && (ans[level-1] * 2 == arr[i] || (ans[level-1] % 3 == 0 && ans[level - 1] / 3 == arr[i]))) {
            visited[i] = 1;
            ans[level] = arr[i];
            dfs(level + 1);
            visited[i] = 0;
            ans[level] = 0;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < N; i++) {
        visited[i] = 1;
        ans[0] = arr[i];
        dfs(1);
        ans[0] = 0;
        visited[i] = 0;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 15918번 - 랭퍼든 수열쟁이야!! (C++)  (0) 2023.09.10
[ 백준 ] 16940번 - BFS 스페셜 저지 (C++)  (0) 2023.09.09
[ 백준 ] 11567번 - 선진이의 겨울 왕국 (C++)  (0) 2023.09.07
[ 백준 ] 3184번 - 양 (C++)  (0) 2023.09.06
[ 백준 ] 3967번 - 매직 스타 (C++)  (0) 2023.09.05
반응형

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

 

11567번: 선진이의 겨울 왕국

첫 번째 테스트 케이스의 경우에는 (1,6) → (2,6) →  (3,6) →  (4,6) → (4,5) → (4,4) → (4,3) →  (4,2) → (4,1) → (3,1) → (2,1) → (2,2) →  (2,3) → (1,3) → (1,2) → (2,2) 의 순서로 가면 탈출이 가능하다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 빙판길을 입력받아 arr에 저장하고, visited 배열을 만들어 방문 여부를 저장합니다.

 

2. X가 있는 좌표는 미리 방문처리를 해줍니다.

 

3. bfs를 통해 이동을 하면서 r2, c2에 도착할 수 있고, 그때 해당 좌표의 visited의 값이 1이라면 YES를 출력하고, 그렇지 않다면 NO를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<string>
 
using namespace std;
 
int n, m;
string arr[500];
int visited[500][500];
int r1, c1, r2, c2;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == 'X') {
                visited[i][j] = 1;
            }
        }
    }
 
    cin >> r1 >> c1 >> r2 >> c2;
    r1--; r2--; c1--; c2--;
 
    queue<pair<int, int>> q;
 
    q.push({ r1,c1 });
    visited[r1][c1] = 1;
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < n && xx >= 0 && xx < m) {
                if (visited[yy][xx] == 0) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
                else if (yy == r2 && xx == c2) {
                    cout << "YES";
                    return 0;
                }
            }
        }
    }
 
    cout << "NO";
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 16940번 - BFS 스페셜 저지 (C++)  (0) 2023.09.09
[ 백준 ] 16936번 - 나3곱2 (C++)  (0) 2023.09.08
[ 백준 ] 3184번 - 양 (C++)  (0) 2023.09.06
[ 백준 ] 3967번 - 매직 스타 (C++)  (0) 2023.09.05
[ 백준 ] 2146번 - 다리 만들기 (C++)  (0) 2023.09.04

+ Recent posts

티스토리툴바