반응형

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

 

17835번: 면접보는 승범이네

첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐

www.acmicpc.net

 

 

[ 문제풀이 ]

1. visited 배열을 만들고 visited [ i ] = 9999999999로 초기화해 줍니다.

 

2. node struct를 만들고, vector<node> list[ 100001 ]를 만들어 V, C를 저장합니다.

 

3. 각 도시에서 면접장까지 가지 않고, 반대로 면접장에서 출발할 예정이므로, U, V, C를 입력받고, list[ V ].push_back({ U, C })를 해줍니다.

 

4. 면접장이 있는 도시를 priority_queue에 넣고 dijkstra를 돌립니다.

 

5. for문을 통해 모든 도시를 돌며 거리가 가장 먼 도시를 city 변수에 저장합니다.

 

6. city와 visited[ city ]를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<vector>
#define ll long long
#define INF 9999999999
 
using namespace std;
 
struct node {
    int V;
    ll C;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.C < right.C;
    }
};
 
int N, M, K;
vector<node> list[100001];
ll visited[100001];
 
int main()
{
    priority_queue<node, vector<node>, cmp> pq;
    scanf("%d %d %d", &N, &M, &K);
 
    for (int i = 1; i <= N; i++) {
        visited[i] = INF;
    }
 
    for (int i = 0; i < M; i++) {
        int U, V;
        ll C;
        scanf("%d %d %lld", &U, &V, &C);
        list[V].push_back({ U, C });
    }
 
    for (int i = 0; i < K; i++) {
        int city;
        scanf("%d", &city);
        pq.push({ city,0 });
        visited[city] = 0;
    }
 
    while (!pq.empty()) {
        const int V = pq.top().V;
        const ll C = pq.top().C;
        pq.pop();
 
        if (visited[V] < C) continue;
 
        for (auto& next : list[V]) {
            if (visited[next.V] > C + next.C) {
                visited[next.V] = C + next.C;
                pq.push({ next.V, C + next.C });
            }
        }
    }
 
    int city = 0;
    ll ans = 0;
 
    for (int i = 1; i <= N; i++) {
        if (ans < visited[i]) {
            city = i;
            ans = visited[i];
        }
    }
 
    printf("%d\n%lld", city, ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2458번 - 키 순서 (C++)  (0) 2023.02.07
[ 백준 ] 2211번 - 네트워크 복구 (C++)  (0) 2023.02.06
[ 백준 ] 1368번 - 물대기 (C++)  (0) 2023.02.04
[ 백준 ] 1261번 - 알고스팟 (C++)  (0) 2023.02.03
[ 백준 ] 10423번 - 전기가 부족 (C++)  (0) 2023.02.02
반응형

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

 

1261번: 알고스팟

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited [ 100 ][ 100 ] 배열을 만들어서 방문 여부를 저장합니다.

 

2. 0-1 너비 우선 탐색을 통해 빈 에 들어가면 deque의 front에 push 하고, 벽을 부시면 deque의 back에 push 하고 cnt + 1을 해줍니다.

 

3. (N - 1,M - 1) 좌표에 도착하면 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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
char arr[101][101];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int visited[100][100];
 
struct node {
    int y;
    int x;
    int cnt;
};
 
int main()
{
    deque<node> deq;
    scanf("%d %d", &M, &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%s", &arr[i]);
    }
 
    deq.push_back({ 0,0,0 });
    visited[0][0] = 1;
 
    while (!deq.empty()) {
        const int y = deq.front().y;
        const int x = deq.front().x;
        const int cnt = deq.front().cnt;
        deq.pop_front();
 
        if (y == N - 1 && x == M - 1) {
            printf("%d", cnt);
            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 < M) {
                if (visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    if (arr[yy][xx] == '0') {
                        deq.push_front({ yy,xx,cnt });
                    }
                    else {
                        deq.push_back({ yy,xx,cnt + 1 });
                    }
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17835번 - 면접보는 승범이네 (C++)  (0) 2023.02.05
[ 백준 ] 1368번 - 물대기 (C++)  (0) 2023.02.04
[ 백준 ] 10423번 - 전기가 부족 (C++)  (0) 2023.02.02
[ 백준 ] 5214번 - 환승 (C++)  (0) 2023.02.01
[ 백준 ] 1584번 - 게임 (C++)  (0) 2023.01.31
반응형

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

 

1584번: 게임

첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited [ 501 ][ 501 ] 배열을 만들어서 방문 여부를 저장합니다.

 

2. 위험 지역과 죽음 지역의 좌표를 받고, 해당 지역을 for문을 통해 위험 지역은 1, 죽음 지역은 2로 초기화합니다.

 

3. 0-1 너비 우선 탐색을 통해 안전 지역에 들어가면 deque의 front에 push 하고, 위험 지역에 들어가면 deque의 back에 push 하고 cnt + 1을 해줍니다.

 

4. (500,500) 좌표에 도착하면 cnt를 출력합니다.

 

5. 위의 좌표에 도착하지 못하면 -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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[501][501];
int visited[501][501];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct node {
    int y;
    int x;
    int cnt;
};
 
void setArea(int X1, int Y1, int X2, int Y2, int num)
{
    if (X1 > X2) swap(X1, X2);
    if (Y1 > Y2) swap(Y1, Y2);
 
    for (int i = Y1; i <= Y2; i++) {
        for (int j = X1; j <= X2; j++) {
            arr[i][j] = num;
        }
    }
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int X1, Y1, X2, Y2;
        scanf("%d %d %d %d", &X1, &Y1, &X2, &Y2);
        setArea(X1, Y1, X2, Y2, 1);
    }
 
    scanf("%d", &M);
 
    for (int i = 0; i < M; i++) {
        int X1, Y1, X2, Y2;
        scanf("%d %d %d %d", &X1, &Y1, &X2, &Y2);
        setArea(X1, Y1, X2, Y2, 2);
    }
 
    deque<node> deq;
 
    deq.push_back({ 0,0,0 });
    visited[0][0] = 1;
 
    while (!deq.empty()) {
        const int y = deq.front().y;
        const int x = deq.front().x;
        const int cnt = deq.front().cnt;
        deq.pop_front();
 
        if (y == 500 && x == 500) {
            printf("%d", cnt);
            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 <= 500 && xx >= 0 && xx <= 500) {
                if (visited[yy][xx] == 0 && arr[yy][xx] != 2) {
                    visited[yy][xx] = 1;
                    if (arr[yy][xx] == 0) {
                        deq.push_front({ yy,xx,cnt });
                    }
                    else {
                        deq.push_back({ yy,xx,cnt + 1 });
                    }
                }
            }
        }
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 10423번 - 전기가 부족 (C++)  (0) 2023.02.02
[ 백준 ] 5214번 - 환승 (C++)  (0) 2023.02.01
[ 백준 ] 1175번 - 배달 (C++)  (0) 2023.01.30
[ 백준 ] 13418번 - 학교 탐방하기 (C++)  (0) 2023.01.29
[ 백준 ] 16398번 - 행성 연결 (C++)  (0) 2023.01.28
반응형

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

 

16118번: 달빛 여우

첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited[ node ][ speed ] 배열을 만들어 속도별로 각 노드까지의 최단 거리를 저장합니다.

 

2. dijkstra를 통해 각 노드별로 최단거리를 구하고, 늑대가 빠르게 달릴 경우 거리 * 1, 여우의 경우 거리 * 2, 늑대가 느리게 달릴 경우 거리 * 4를 통해 속도를 조절합니다.

 

3. 여우의 도착시간보다 늑대의 도착 시간이 더 느릴 경우 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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
int N, M;
vector<pair<int, int>> list[4001];
int visited[4001][3];
 
struct node {
    int to;
    int dist;
    int speed;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.dist < right.dist;
    }
};
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 2; i <= N; i++) {
        visited[i][0] = visited[i][1] = visited[i][2] = 2087654321;
    }
    visited[1][0] = 2087654321;
 
    for (int i = 0; i < M; i++) {
        int a, b, d;
        scanf("%d %d %d", &a, &b, &d);
 
        list[a].emplace_back(b, d);
        list[b].emplace_back(a, d);
    }
 
    priority_queue<node, vector<node>, cmp> pq;
 
    pq.push({ 1,0,1 });
    pq.push({ 1,0,2 });
 
    while (!pq.empty()) {
        const int dist = pq.top().dist;
        const int cur = pq.top().to;
        const int speed = pq.top().speed;
        pq.pop();
 
        if (visited[cur][speed] < dist) continue;
        visited[cur][speed] = dist;
 
        if (speed == 0) {
            for (auto &next : list[cur]) {
                const int nNode = next.first;
                const int nDist = next.second * 4;
 
                if (visited[nNode][2] > dist + nDist) {
                    visited[nNode][2] = dist + nDist;
                    pq.push({ nNode,visited[nNode][2],2 });
                }
            }
        }
        else if (speed == 1) {
            for (auto& next : list[cur]) {
                const int nNode = next.first;
                const int nDist = next.second * 2;
 
                if (visited[nNode][speed] > dist + nDist) {
                    visited[nNode][speed] = dist + nDist;
                    pq.push({ nNode,visited[nNode][speed],1 });
                }
            }
            
        }
        else {
            for (auto& next : list[cur]) {
                const int nNode = next.first;
                const int nDist = next.second;
 
                if (visited[nNode][0] > dist + nDist) {
                    visited[nNode][0] = dist + nDist;
                    pq.push({ nNode,visited[nNode][0],0 });
                }
            }
        }
    }
 
    int ans = 0;
 
    for (int i = 1; i <= N; i++) {
        if (visited[i][1] < visited[i][2] && visited[i][1] < visited[i][0]) {
            ans++;
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2493번 - 탑 (C++)  (0) 2023.01.12
[ 백준 ] 13975번 - 파일 합치기 3 (C++)  (0) 2023.01.11
[ 백준 ] 16562번 - 친구비 (C++)  (0) 2023.01.09
[ 백준 ] 14226번 - 이모티콘 (C++)  (0) 2023.01.08
[ 백준 ] 2470번 - 두 용액 (C++)  (0) 2023.01.07
반응형

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

 

23793번: 두 단계 최단 경로 1

서준이는 아빠로부터 생일선물로 세계 지도를 받아서 매우 기뻤다. 세계 지도에서 최단 경로를 찾는 프로그램을 개발해서 아빠께 감사의 마음을 전달하려고 한다. 세계 지도는 도시를 정점으

www.acmicpc.net

 

 

 

[ 문제풀이 ]

 

1. dijkstra 함수를 만들어서 A에서 B까지 C를 거치지 않았을 때의 거리를 return 합니다.

 

2. XY, YZ의 거리를 더해 XYZ의 거리를 출력하고, XZ의 Y를 거치지 않았을 때 거리를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
struct node {
    int to;
    int dist;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.dist < right.dist;
    }
};
 
int N, M;
int X, Y, Z;
vector<node> list[100001];
int visited[100001];
 
int dijkstra(int a, int b, int c)
{
    for (int i = 1; i <= N; i++) {
        visited[i] = 1987654321;
    }
    visited[a] = 0;
    int ret = 0;
 
    priority_queue<node, vector<node>, cmp> pq;
 
    pq.push({ a,0 });
 
    while (!pq.empty()) {
        const int cur = pq.top().to;
        const int dist = pq.top().dist;
        pq.pop();
 
        if (visited[cur] < dist) continue;
 
        if (cur == b) {
            return dist;
        }
 
        for (auto next : list[cur]) {
            const int nNode = next.to;
            const int nDist = next.dist;
 
            if (visited[nNode] > nDist + dist && nNode != c) {
                visited[nNode] = nDist + dist;
                pq.push({ nNode,visited[nNode] });
            }
        }
    }
 
    return -1;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
 
        list[u].push_back({ v, w });
    }
 
    scanf("%d %d %d", &X, &Y, &Z);
 
    int XY = dijkstra(X, Y, 0);
    int YZ = dijkstra(Y, Z, 0);
    int XZ = dijkstra(X, Z, Y);
 
    if (XY == -1 || YZ == -1) {
        printf("-1 ");
    }
    else {
        printf("%d ", XY + YZ);
    }
 
    printf("%d", XZ);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1194번 - 달이 차오른다, 가자. (C++)  (0) 2022.12.28
[ 백준 ] 2589번 - 보물섬 (C++)  (0) 2022.12.27
[ 백준 ] 1759번 - 암호 만들기 (C++)  (0) 2022.12.25
[ 백준 ] 19538번 - 루머 (C++)  (0) 2022.12.24
[ 백준 ] 1922번 - 네트워크 연결 (C++)  (0) 2022.12.23
반응형

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

 

22255번: 호석사우루스

(1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3) -> (3, 4) -> (4, 4) -> (5, 4) -> (5, 5) 8번 만에 갈 수 있고 이게 최소이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. node struct를 만들어 x좌표, y좌표, n번째 이동, 충격량을 저장합니다.

 

2. visited [ 101 ][ 101 ][ 3 ] 배열을 만들어 x좌표, y좌표, 3K + n번째 이동일 경우 충격량을 저장합니다.

 

3. dijkstra를 이용하여 시작점에서부터 도착점까지 충격량을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int Sx, Sy, Ex, Ey;
int arr[101][101];
int visited[101][101][3];
 
int dx[3][4] = {
    -1,1,0,0,
    -1,1,0,0,
    0,0,0,0
};
 
int dy[3][4] = {
    0,0,-1,1,
    0,0,0,0,
    -1,1,0,0,
};
 
struct node {
    int x;
    int y;
    int cnt;
    int dist;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.dist < right.dist;
    }
};
 
int main()
{
    scanf("%d %d", &N, &M);
    scanf("%d %d %d %d", &Sx, &Sy, &Ex, &Ey);
 
    for (int i = 0; i < 3; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= M; k++) {
                visited[j][k][i] = 987654321;
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    priority_queue<node, vector<node>, cmp> pq;
 
    pq.push({ Sx,Sy,1,0 });
    visited[Sx][Sy][1] = 0;
 
    while (!pq.empty()) {
        const int x = pq.top().x;
        const int y = pq.top().y;
        const int cnt = pq.top().cnt % 3;
        const int dist = pq.top().dist;
        pq.pop();
 
        if (y == Ey && x == Ex) {
            printf("%d", dist);
            return 0;
        }
        
        if (cnt == 0) {
            for (int i = 0; i < 4; i++) {
                const int yy = y + dy[cnt][i];
                const int xx = x + dx[cnt][i];
 
                if (yy > 0 && xx <= N && xx > 0 && yy <= M) {
                    if (visited[xx][yy][1] > dist + arr[xx][yy] && arr[xx][yy] != -1) {
                        visited[xx][yy][1] = dist + arr[xx][yy];
                        pq.push({ xx,yy,1,dist + arr[xx][yy] });
                    }
                }
            }
        }
        else if (cnt == 1) {
            for (int i = 0; i < 2; i++) {
                const int yy = y + dy[cnt][i];
                const int xx = x + dx[cnt][i];
 
                if (yy > 0 && xx <= N && xx > 0 && yy <= M) {
                    if (visited[xx][yy][2] > dist + arr[xx][yy] && arr[xx][yy] != -1) {
                        visited[xx][yy][2] = dist + arr[xx][yy];
                        pq.push({ xx,yy,2,dist + arr[xx][yy] });
                    }
                }
            }
        }
        else {
            for (int i = 0; i < 2; i++) {
                const int yy = y + dy[cnt][i];
                const int xx = x + dx[cnt][i];
 
                if (yy > 0 && xx <= N && xx > 0 && yy <= M) {
                    if (visited[xx][yy][0] > dist + arr[xx][yy] && arr[xx][yy] != -1) {
                        visited[xx][yy][0] = dist + arr[xx][yy];
                        pq.push({ xx,yy,0,dist + arr[xx][yy] });
                    }
                }
            }
        }
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 12738번 - 가장 긴 증가하는 부분 수열 3 (C++)  (0) 2022.12.21
[ 백준 ] 1818번 - 책정리 (C++)  (0) 2022.12.20
[ 백준 ] 6593번 - 상범 빌딩 (C++)  (0) 2022.12.18
[ 백준 ] 12014번 - 주식 (C++)  (0) 2022.12.17
[ 백준 ] 1365번 - 꼬인 전깃줄 (C++)  (0) 2022.12.16
반응형

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

 

2665번: 미로만들기

첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dijkstra를 이용하여 흰 방을 지날 때의 가중치는 1, 검은 방을 지날 때는 가중치 10000을 주어서 도착점에 도착했을 때 이동 거리를 10000으로 나눈 값을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int n;
char arr[51][51];
int visited[50][50];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct node {
    int y;
    int x;
    int dist;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.dist < right.dist;
    }
};
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%s", arr[i]);
        for (int j = 0; j < n; j++) {
            visited[i][j] = 987654321;
        }
    }
 
    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 dist = pq.top().dist;
        pq.pop();
 
        if (y == n - 1 && x == n - 1) {
            printf("%d", dist / 10000);
        }
 
        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) {
                if (arr[yy][xx] == '1') {    //흰 방
                    if (visited[yy][xx] > dist + 1) {
                        visited[yy][xx] = dist + 1;
                        pq.push({ yy,xx,dist + 1 });
                    }
                }
                else {        //검은 방
                    if (visited[yy][xx] > dist + 10000) {
                        visited[yy][xx] = dist + 10000;
                        pq.push({ yy,xx,dist + 10000 });
                    }
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2812번 - 크게 만들기 (C++)  (0) 2022.12.14
[ 백준 ] 9019번 - DSLR (C++)  (0) 2022.12.13
[ 백준 ] 1726번 - 로봇 (C++)  (0) 2022.12.11
[ 백준 ] 24042번 - 횡단보도 (C++)  (0) 2022.12.10
[ 백준 ] 1600번 - 말이 되고픈 원숭이 (C++)  (0) 2022.12.09
반응형

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

 

24042번: 횡단보도

당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 $N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 그래프를 입력받으면서 몇 분에 어떤 횡단보도를 건널 수 있는지 list에 저장합니다.

 

2. 데이크스트라를 이용하여 1번 지역부터 돌면서 다음에 갈 수 있는 지역의 신호가 파란불로 바뀌는 시점이 현재 시점보다 앞이면 거리 ndist = cnt + M - cnt % M + next.second + 1, 뒤라면 ndist = cnt - cnt % M + next.second + 1로 설정하여 pq에 넣어줍니다.

 

3. 현재 지역이 N지역이라면 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
#include<iostream>
#include<queue>
#include<vector>
#define ll long long
 
using namespace std;
 
struct node {
    int cur;
    ll cnt;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.cnt < right.cnt;
    }
};
 
int N, M;
ll visited[100001];
vector<pair<int, ll>> list[700001];
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        visited[i] = 1844674407370955161;
    }
 
    for (ll i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        list[a].emplace_back(b, i);
        list[b].emplace_back(a, i);
    }
 
    priority_queue<node, vector<node>, cmp> pq;
 
    pq.push({ 1,0 });
 
    while (!pq.empty()) {
        const int cur = pq.top().cur;
        const ll cnt = pq.top().cnt;
        pq.pop();
 
        if (cur == N) {
            printf("%lld", cnt);
            return 0;
        }
 
        for (const auto& next : list[cur]) {
            if ((cnt % M) - 1 > next.second) {    //현재보다 앞의 상태
                ll ndist = cnt + M - cnt % M + next.second + 1;
                if (visited[next.first] > ndist) {
                    visited[next.first] = ndist;
                    pq.push({ next.first, ndist });
                }
            }
            else if ((cnt % M) - 1 < next.second) {    //현재보다 뒤의 상태
                ll ndist = cnt - cnt % M + next.second + 1;
                if (visited[next.first] > ndist) {
                    visited[next.first] = ndist;
                    pq.push({ next.first, ndist });
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2665번 - 미로만들기 (C++)  (0) 2022.12.12
[ 백준 ] 1726번 - 로봇 (C++)  (0) 2022.12.11
[ 백준 ] 1600번 - 말이 되고픈 원숭이 (C++)  (0) 2022.12.09
[ 백준 ] 16393번 - Lost Map (C++)  (0) 2022.12.08
[ 백준 ] 1016번 - 제곱 ㄴㄴ 수 (C++)  (0) 2022.12.07
반응형

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

 

6087번: 레이저 통신

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 맵을 입력받고, 문의 위치를 vector에 저장합니다.

 

2. visited [ y ][ x ][ dir ] 배열을 만들어 방문 여부를 저장합니다.

 

3. pos struct를 만들어 y좌표, x좌표, 빛의 방향, 거울의 개수를 저장합니다.

 

4. dijkstra를 이용하여 거울의 개수가 적은 순으로 priority_queue에서 뽑고, '.'을 만나면 pq에 넣습니다.

 

5. vector에 저장된 문의 좌표와 현재 좌표가 일치하면 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
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
int W, H;
char arr[101][101];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int visited[101][101][4];
vector<pair<int, int>> laser;
 
struct pos {
    int y;
    int x;
    int cnt;
    int dir;
};
 
struct cmp {
    bool operator()(pos right, pos left) {
        return left.cnt < right.cnt;
    }
};
 
int main()
{
    scanf("%d %d", &W, &H);
 
    for (int i = 0; i < H; i++) {
        scanf("%s", arr[i]);
    }
 
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (arr[i][j] == 'C') {
                laser.emplace_back(i, j);
            }
        }
    }
 
    priority_queue<pos, vector<pos>, cmp> pq;
    for (int i = 0; i < 4; i++) {
        pq.push({ laser[0].first, laser[0].second, 0, i });
    }
 
    while (!pq.empty()) {
        const int y = pq.top().y;
        const int x = pq.top().x;
        const int cnt = pq.top().cnt;
        const int dir = pq.top().dir;
        pq.pop();
 
        if (visited[y][x][dir] == 1) continue;
        visited[y][x][dir] = 1;
 
        if (y == laser[1].first && x == laser[1].second) {
            printf("%d", cnt);
            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 < H && xx >= 0 && xx < W) {
                if (arr[yy][xx] == '*') continue;
                if (visited[yy][xx][dir] != 1) {
                    if (i != dir) {
                        pq.push({ yy,xx,cnt + 1,i });
                    }
                    else {
                        pq.push({ yy,xx,cnt,i });
                    }
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 15591번 - MooTube (Silver) (C++)  (0) 2022.11.26
[ 백준 ] 4991번 - 로봇 청소기 (C++)  (0) 2022.11.25
[ 백준 ] 4485번 - 녹색 옷 입은 애가 젤다지? (C++)  (0) 2022.11.23
[ 백준 ] 2151번 - 거울 설치 (C++)  (0) 2022.11.22
[ 백준 ] 17386번 - 선분 교차 1 (C++)  (0) 2022.11.21
반응형

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

 

4485번: 녹색 옷 입은 애가 젤다지?

젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. N을 입력받고 visited 배열을 초기화해줍니다.

 

2. pos struct를 만들어 y좌표, x좌표, 현재까지 잃은 루피 cur을 저장합니다.

 

3. dijkstra를 통해 가장 적게 루피를 잃고 나오는 경우의 값을 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
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
 
using namespace std;
 
int N;
int arr[130][130];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int visited[130][130];
 
struct pos {
    int y;
    int x;
    int cur;
};
 
struct cmp {
    bool operator()(pos right, pos left) {
        return left.cur < right.cur;
    }
};
 
int main()
{
    int cnt = 1;
 
    while (1) {
        scanf("%d", &N);
        memset(visited, 0, sizeof(visited));
 
        if (N == 0) break;
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                scanf("%d", &arr[i][j]);
            }
        }
 
        int ans = 0;
 
        priority_queue<pos, vector<pos>, cmp> pq;
        pq.push({ 0,0,arr[0][0] });
 
        while (!pq.empty()) {
            int y = pq.top().y;
            int x = pq.top().x;
            int cur = pq.top().cur;
            pq.pop();
 
            if (visited[y][x] == 1) continue;
            visited[y][x] = 1;
 
            if (y == N - 1 && x == N - 1) {
                ans = cur;
                break;
            }
 
            for (int i = 0; i < 4; i++) {
                int yy = y + dy[i];
                int xx = x + dx[i];
 
                if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                    if (visited[yy][xx] != 1) {
                        pq.push({ yy,xx,cur + arr[yy][xx] });
                    }
                }
            }
        }
 
        printf("Problem %d: %d\n", cnt, ans);
        cnt++;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 4991번 - 로봇 청소기 (C++)  (0) 2022.11.25
[ 백준 ] 6087번 - 레이저 통신 (C++)  (0) 2022.11.24
[ 백준 ] 2151번 - 거울 설치 (C++)  (0) 2022.11.22
[ 백준 ] 17386번 - 선분 교차 1 (C++)  (0) 2022.11.21
[ 백준 ] 1774번 - 우주신과의 교감 (C++)  (0) 2022.11.20

+ Recent posts

티스토리툴바