-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
BFS와 다이나믹 테이블을 섞어서 풀었는데 그럼 이건 DP로 풀었다고 볼 수 없는건가요??
21.07.18 18:44 작성 조회수 134
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중
#include <iostream>
#include <queue>
using namespace std;
int map[21][21];
int dy[21][21];
int row[2] = {1,0};
int col[2] = {0,1};
int main() {
ios_base::sync_with_stdio(false);
int N;
queue<pair<int,int>> q;
cin >> N;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
cin >> map[i][j];
if(i == 1 && j == 1){
dy[i][j] = map[i][j];
}else{
dy[i][j] = 2147000000;
}
}
}
q.push(make_pair(1,1));
while(!q.empty()){
pair<int, int> x = q.front();
q.pop();
for(int i = 0; i < 2; i++){
int _x = x.first + row[i];
int _y = x.second + col[i];
int energy = dy[x.first][x.second] + map[_x][_y];
if(energy < dy[_x][_y]) {
dy[_x][_y] = energy;
q.push(make_pair(_x, _y));
}
}
}
cout << dy[N][N];
return 0;
}
하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
답변을 작성해보세요.
0
0
0
GAMEGAME
질문자2021.07.18
선생님 풀이와 다른점은
1. 출발점만 초기화 시켰다는 것
2.위쪽과 왼쪽에서 올 수 있는 경우 일단 더해보고 에너지가 더 작은 값을 dy테이블에 할당시켰다는 것입니다.
일단 dynamic테이블에 저장하면서 사용했긴 했는데.. 선생님 풀이를 보니 그냥 단순 BFS로 풀었다봐도 무방한 것 같긴 한데. 결과적으로 이런 풀이는 DP로 풀었다고 볼 수 없는거죠?
답변 3