[동계 모각코 5차 회고]

동계 모각코 5차시 01.27 20:00~23:00 종료

#개인별 회고

김동훈 - 

파이썬으로 다익스트라 문제를 풀었는데, 자바로 할때보다 확실히 코드의 양이 줄었다.

첫 제출때 시간초과가 났는데, 조건문에서 = 를 써서 발생했었다.

N이 125밖에 되지 않아 테케가 널널하다고 생각했는데 힙큐에서 push 하는 연산시간도 while 문 안에 포함되어 생각보다 = 조건 하나가 중요했던 문제였다.

https://kmentor.tistory.com/category/2021-2022%EB%8F%99%EA%B3%84%20%EB%AA%A8%EA%B0%81%EC%BD%94

'2021-2022동계 모각코' 카테고리의 글 목록

임동윤 - 

달성 현황

1. 다익스트라 알고리즘 2문제 이상 풀기(최소 한문제 골드이상) -> 성공


다짐.

오래만에 다익스트라 알고리즘을 해결해 보았는데, 처음부터 개념을 다시익혀야 하는 경우가 생겼다. 더 많은 문제를 해결함으로써 알고리즘을 학습해야겠다.

https://blog.naver.com/dyyim4725

잡동탱~ : 네이버 블로그

배성현 - 

문제 : [https://www.acmicpc.net/problem/4485](https://www.acmicpc.net/problem/4485)

```cpp
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1} ;
int num;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while (1)
    {
        int n; cin >> n;
        if(n==0)
            break;
        int cost[125][125];
        int ans[125][125];
        priority_queue<pair<int,pair<int, int>>> pq;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n;j++){
                cin>>cost[i][j];
                ans[i][j] = 987654321;
            }
        }
        ans[0][0] = cost[0][0];
        pq.push({-ans[0][0], {0, 0}});
        while(!pq.empty()){
            int curCost = -pq.top().first;
            int x = pq.top().second.first;
            int y = pq.top().second.second;
            pq.pop();
            for (int i = 0; i < 4;i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(0<=nx&&nx<n&&0<=ny&&ny<n){
                    if(ans[nx][ny]>cost[nx][ny]+curCost){
                        ans[nx][ny] = cost[nx][ny] + curCost;
                        pq.push({-ans[nx][ny], {nx, ny}});
                    }
                }
            }
        }
        cout << "Problem " << ++num << ": " << ans[n - 1][n - 1]<<"\n";
    }
}
```

⇒ 다익스트라의 변형 문제로 처음에 js로 우선순위큐를 사용하지 않고 풀어서 시간 초과가 발생하였다. js에는 우선순위 큐가 내장함수로 존재하지 않아 c++로 같은 로직을 사용하여 제출하였다.