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 <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 987654321
struct Pos{
int y,x,cost,dir;
};
struct cmp{
bool operator()(const Pos &a, const Pos &b){
return a.cost> b.cost;
}
};
int answer = 987654321;
int n;
//0:동 1:남 2:서 3:북
int dy[4]={0,1,0,-1};
int dx[4]={1,0,-1,0};
int cost[26][26][4];
int Board[26][26];
void bfs(){
priority_queue<Pos,vector<Pos>,cmp> pq;
pq.push({ 0, 0, 0, -1});
while(!pq.empty()){
Pos now=pq.top();
pq.pop();
for(int i=0;i<4;i++){
int ny=now.y+dy[i];
int nx=now.x+dx[i];
int ncost=now.cost;
int dir=now.dir;
if(ny<0 || ny>=n || nx<0 || nx>=n)
continue;
if(Board[ny][nx])
continue;
ncost+=100;
if(dir%2 != i%2 && dir!= -1)
ncost+=500;
if(ncost<cost[ny][nx][i]){
cost[ny][nx][i]=ncost;
pq.push({ny,nx,ncost,i});
}
}
}
answer = *min_element(cost[n - 1][n - 1], cost[n - 1][n - 1] + 4);
}
int solution(vector<vector<int>> board) {
n=board.size();
for(int i=0;i<n;i++){
for(int j=0; j<n; j++ ){
Board[i][j]=board[i][j];
}
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
for (int k = 0; k < 4; ++k)
cost[i][j][k] = INF;
for (int i = 0; i < 4; ++i)
cost[0][0][i] = 0;
bfs();
return answer;
}
|
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
|
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 987654321
struct Pos{
int y,x,cost,dir;
};
struct cmp{
bool operator()(const Pos &a, const Pos &b){
return a.cost> b.cost;
}
};
int answer = 987654321;
int n;
//0:동 1:남 2:서 3:북
int dy[4]={0,1,0,-1};
int dx[4]={1,0,-1,0};
int cost[26][26][4];
int Board[26][26];
void dfs(int y, int x ,int curCost,int dir){
for(int i=0;i<4;i++){
int ny=y+dy[i];
int nx=x+dx[i];
int ncost=curCost;
if(ny<0 || ny>=n || nx<0 || nx>=n)
continue;
if(Board[ny][nx])
continue;
ncost+=100;
if(dir%2 != i%2 && dir!= -1)
ncost+=500;
if(ncost<cost[ny][nx][i]){
cost[ny][nx][i]=ncost;
dfs(ny,nx,ncost,i);
}
}
}
int solution(vector<vector<int>> board) {
n=board.size();
for(int i=0;i<n;i++){
for(int j=0; j<n; j++ ){
Board[i][j]=board[i][j];
}
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
for (int k = 0; k < 4; ++k)
cost[i][j][k] = INF;
for (int i = 0; i < 4; ++i)
cost[0][0][i] = 0;
dfs(0,0,0,-1);
answer = *min_element(cost[n - 1][n - 1], cost[n - 1][n - 1] + 4);
return answer;
}
|
cs |
출처:https://school.programmers.co.kr/learn/courses/30/lessons/67259
다익스트라 문제 오랜만에 풀어봐서 잘못 접근했었네요.
dp문제로 처음에 시간초과가 뜬걸 주의해서 다익스트라로 해결할 수 있는 문제였습니다.
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[c++] 스타 수열 (0) | 2022.10.09 |
---|---|
[c++] 무지의 먹방 라이브 (0) | 2022.10.08 |
[c++] N으로 표현 (1) | 2022.10.04 |
[c++] 아이템줍기 (BFS) (1) | 2022.09.29 |
[c++] 1차 비밀지도 (구현) (0) | 2022.09.28 |