반응형
알고리즘 종류
다익스트라
우선순위 큐
사고 과정
다익스트라를 2차원 배열에 사용하여 해결했습니다.
값을 저장할 dp 2차원 배열을 만들어 줍니다.
시작점에서 출발하여, 아래 2가지 조건으로 비교합니다.
1. 쓰레기를 지나는 경우 비교
2. 쓰레기를 지나는 경우가 같으면, 쓰레기 주변을 지나는 경우 비교
목표 지점에 도착하면, 종료합니다.
구현(C++)
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
|
#include <iostream>
#include <vector>
#include <queue>
#define MAX 987654321
using namespace std;
struct State{
int y;
int x;
int pass; // 쓰레기를 지나간다.
int around; // 쓰레기 주변을 지나간다.
};
struct Tmp{
int pass=MAX;
int around=MAX;
};
struct cmp{
bool operator()(State a, State b){
if(a.pass != b.pass) return a.pass > b.pass; // 쓰레기 적게 지나가는 거 먼저
return a.around > b.around; // 쓰레기 지나가기가 같을 경우, 주변을 적게 지나가는 거 먼저
}
};
int h, w;
int sy, sx;
char mat[51][51];
Tmp dp[51][51];
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
bool isValid(int y, int x){
return (y>=0 && y<h) && (x>=0 && x<w);
}
// 쓰레기 주변 표시
void around_garbage(){
for(int i=0; i<h; i++){
for(int j=0; j<w; j++){
if(mat[i][j] == 'g'){
for(int d=0; d<4; d++){
int ny = i + dir[d][0];
int nx = j + dir[d][1];
if(isValid(ny, nx) && mat[ny][nx] == '.'){
mat[ny][nx] = '#';
}
}
}
}
}
}
void solution(){
around_garbage();
priority_queue<State, vector<State>, cmp> pq;
pq.push({sy, sx, 0, 0});
dp[sy][sx].pass = 0;
dp[sy][sx].around = 0;
while(true){
int y = pq.top().y;
int x = pq.top().x;
int p = pq.top().pass;
int a = pq.top().around;
pq.pop();
for(int d=0; d<4; d++){
int ny = y + dir[d][0];
int nx = x + dir[d][1];
int np = p;
int na = a;
// 목표에 도착
if(mat[ny][nx] == 'F'){
cout << np << " " << na << endl;
return;
}
if(!isValid(ny, nx)) continue;
if(mat[ny][nx] == 'g') np += 1;
else if(mat[ny][nx] == '#') na += 1;
// 쓰레기 지나는 경우 비교
if(dp[ny][nx].pass > np){
dp[ny][nx].pass = np;
dp[ny][nx].around = na;
pq.push({ny, nx, dp[ny][nx].pass, dp[ny][nx].around});
}
// 쓰레기 지나는 경우가 같으면, 쓰레기 주변을 지나는 경우 비교
else if(dp[ny][nx].pass == np){
if(dp[ny][nx].around > na){
dp[ny][nx].around = na;
pq.push({ny, nx, dp[ny][nx].pass, dp[ny][nx].around});
}
}
}
}
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> h >> w;
for(int i=0; i<h; i++){
for(int j=0; j<w; j++){
cin >> mat[i][j];
if(mat[i][j] == 'S'){
sy = i;
sx = j;
}
}
}
solution();
}
|
cs |
시행착오
반응형
'코딩 공부 > 백준' 카테고리의 다른 글
[백준][C++] 12100 2048 (Easy) (0) | 2021.04.10 |
---|---|
[백준][C++] 13460 구슬 탈출 2 (0) | 2021.04.10 |
[백준][C++] 17780 새로운 게임 (0) | 2021.04.09 |
[백준][C++] 14464 소가 길을 건너간 이유 4 (0) | 2021.04.05 |
[백준][C++] 1826 연료 채우기 (0) | 2021.04.05 |