급하게임개발

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

이 문제는 위상정렬 알고리즘을 사용하는 문제이다
https://terms.naver.com/entry.naver?docId=3579618&cid=59086&categoryId=59093

해당 게시물을 참조하면 이해가 쉬울 것이다
즉 순서에 맞춰서 나열 하면 되는게 위상 정렬 이다

이 문제에서는 어떠한 노드 가 나로 올수 있는 점입차수 라는것을 들고 있어야 한다 점입차수가 0이면 먼저 뽑아도 무방한 노드라고 보면 된다 즉 우리는 이문제를 풀때 점입차수를 비교해가며 큐에 넣어서 pop 하면 되는 문제이다

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	int inCount[100001] = { 0, };
	vector<vector<int>> v(n + 1);
	for (int i = 0; i < m; i++) {
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		v[tmp1].push_back(tmp2);
		inCount[tmp2]++;
	}
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (inCount[i] == 0)
			q.push(i);
	}

	while (!q.empty()) {
		cout << q.front() << " ";
		int idx = q.front();
		for (int i = 0; i < v[idx].size(); i++) {
			inCount[v[idx][i]] -= 1;
			if (inCount[v[idx][i]]<=0)
				q.push(v[idx][i]);
		}
		q.pop();
	}
}

일단 전체 코드는 이렇게 된다
입력 받을 때 어떠한 노드를 입력 받고 이노드가 갈수 있는 노드도 Vector에 넣어 놓느다 그후  연결 된 노드의 점입  차수를 1증가 시킨다  이렇게 입력 을 받은 후
우리는 해당 vector를 순회하면 서 일단 점입차수가 0인걸 queue에다가 넣는다
그후 while문으로 큐를 순회하면서 점입차수가 0인 걸 팝해주면 나와 연결된 노드들의 점입 차수를 1감소시켜준다 그렇게 점입차수가 0인 노드들을 지속적으로 queue에 넣었다 팝해주면 해당 문제는 풀린다

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

이 문제는 솔직히 설명이 겁나 불친절하다 

정확히 이문제는 핵심이 나를 기준으로 나보다 크기가 작고 같은 거리에 있는 물고기 들은 위에에서 왼쪽부터 오른쪽 까지 검사하고 내려와서 왼쪽부터 오른쪽 까지 검사하면서 이 순으로 탐색을 하는 거였다.
단 위에를 듣고 BFS  이동방향을 1,0 ->0,-1 ->0,1 ->-1,0 이렇게 만 하면 안풀린다

while (!bfsQ.empty()) {
		
				otherX = bfsQ.front().second.first;
				otherY = bfsQ.front().second.second;
				otherCost = bfsQ.front().first;
				if (CanEat(otherX, otherY) && otherCost<=cost) {
					if (otherX < startX) {
						startX = otherX;
						startY = otherY;
						otherCost = cost;
					}
					else if (otherX == startX && startY>otherY ) {
						startX = otherX;
						startY = otherY;
						otherCost = cost;
					}
				}

핵심은 이부분이다 내가 물고기를 먹을 수있는 지역으로 갔을 때 현재 큐에  들어와 있는 것중 나보다 거리가 작거나 같고 행의 값이  위에 있거나 혹은 행이 같다면 열값이 더 먼저인 애를 찾아서 거기를 가야한다 이에 의해 필자는 행을 검사에서 위에있으면 해당 행으로 탐색지점을 바꿔줬고 같다면 열값이 더 작은 쪽으로 옮겨줬다

#include <iostream>
#include <queue>
using namespace std;
int n;
int arr[20][20] = { 0, };
bool isVisited[20][20];
int fishSize = 2;
int eatFish = 0;
int cnt = 0;
queue<pair<int,pair<int, int>>>  bfsQ;

bool CanEat(int x, int y) {
	if (arr[x][y]>0&&arr[x][y] < fishSize) {
		return true;
	}
	return false;
}
bool canGo(int x, int y) {
	if (x >= 0 && x < n && y >= 0 && y < n && !isVisited[x][y] && (CanEat(x, y) || arr[x][y] == 0 || arr[x][y]==fishSize))
		return true;
	else
		return false;
}

void Bfs(int x, int y) {
	bfsQ.push({ cnt,{x,y} });
	arr[x][y] = 0;
	int startX, startY, cost;
	int otherX, otherY, otherCost;
	while (!bfsQ.empty()) {
		startX = bfsQ.front().second.first;
		startY = bfsQ.front().second.second;
		cost = bfsQ.front().first;
		bfsQ.pop();
		if (CanEat(startX, startY)) {
			cnt += cost;
			while (!bfsQ.empty()) {
		
				otherX = bfsQ.front().second.first;
				otherY = bfsQ.front().second.second;
				otherCost = bfsQ.front().first;
				if (CanEat(otherX, otherY) && otherCost<=cost) {
					if (otherX < startX) {
						startX = otherX;
						startY = otherY;
						otherCost = cost;
					}
					else if (otherX == startX && startY>otherY ) {
						startX = otherX;
						startY = otherY;
						otherCost = cost;
					}
				}

				bfsQ.pop();
				
			}
			bfsQ.push({ 0, {startX, startY}});
			eatFish += 1;
			if (eatFish == fishSize) {
				fishSize += 1;
				eatFish = 0;
			}
			arr[startX][startY] = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					isVisited[i][j] = false;
				}
			}
			isVisited[startX][startY] = true;
			cost = 0;
		}

		if (canGo(startX-1,startY)) {
			bfsQ.push({ cost + 1,{startX -1,startY}});
			isVisited[startX - 1][startY] = 1;
		}
		if (canGo(startX, startY-1)) {
			bfsQ.push({ cost + 1,{startX ,startY - 1} });
			isVisited[startX][startY-1] = 1;
		}
		if (canGo(startX , startY+1)) {
			bfsQ.push({ cost + 1,{startX ,startY + 1} });
			isVisited[startX][startY + 1] = 1;
		}
		if (canGo(startX+1 , startY)) {
			bfsQ.push({ cost + 1,{startX + 1,startY} });
			isVisited[startX + 1][startY] = 1;
		}
	}

}
int main() {
	cin >> n;
	int startIdxCol, startIdxRow;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 9) {
				startIdxCol = i;
				startIdxRow = j;
			}
		}
	}

	Bfs(startIdxCol, startIdxRow);
	cout << cnt;
}

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

이 문제의 경우 최소 신장트리를 만들어 내는 문제이다 모든 정점들을 이었을 때 각 간선들의 최소가 되는 트리를 최소 신장트리라고 한다  이문제의 경우 내가 트리의 크루스칼 알고리즘을 이용해서 풀었다

크루스칼 알고리즘은 
1. 각 경로들의 cost 값으로 오름차순 정렬 한다
2. 각 경로들의 vertex 간 비교해서 각 vertex들이 이어진 경로의 root와 비교해서 서로 다르면 잇고 아니면 연결하지 않는다
3. 2의 과정을 반복한 후 Cost의 값을  도출한다

#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 가중치 start end순
vector<pair<int, pair<int, int>>> inputData;
int parent[10001] = { 0, };

int findParent(int x) {
	if (parent[x] == x)
		return x;
	else return parent[x] = findParent(parent[x]);
}

bool sameParent(int x, int y) {
	x = findParent(x);
	y = findParent(y);
	if (x == y)
		return true;
	else
		return false;
}
void uni(int  x, int y) {
	x = findParent(x);
	y = findParent(y);
	parent[y] = x;
}
int main() {
	int  v, e,cost;
	cost = 0;
	cin >> v >> e;
	int tmp1, tmp2, tmp3;
	for (int i = 0; i < e; i++) {
		cin >> tmp1 >> tmp2 >> tmp3;
		inputData.push_back({ tmp3,{tmp1,tmp2} });
	}

	sort(inputData.begin(), inputData.end());
	for (int i = 1; i <= v; i++) {
		parent[i] = i;
	}

	for (int i = 0; i<inputData.size(); i++) {
		if (!sameParent(inputData[i].second.first, inputData[i].second.second)) {
			uni(inputData[i].second.first, inputData[i].second.second);
			cost += inputData[i].first;
		}
	}
	cout << cost;
}

https://school.programmers.co.kr/learn/courses/30/lessons/250136

이 문제는 간단한 문제인줄 알고 건드렸다가 2시간을 날릴 정도로 고생한 문제이다 
일단 이 문제의경우 딱 봤을 때 BFS를 사용하는거는 확실 해 보이지만 매번 시추할 때 마다 BFS를 돌리면 효율성 검사에서 점수가 떨어지게 된다 이에 이문제는 BFS를 이용해서 뽑아낸 데이터를 어떤 자료 구조에 넣어 사용하는 지가 매우 중요한 문제이다

#include <string>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
int directionX[4] = { 1, 0, -1, 0 };
int directionY[4] = { 0, 1, 0, -1 };
int isVisited[501][501] = { 0, };
map<int, int> sizeOfOil;
int sizeOfLandX;
int sizeOfLandY;
int areaNum = 1;
vector<vector<int>> oilMap;
void BFS(int startX, int startY ) {
    int tmp = 0;
    queue<pair<int, int>> q;
    q.push({ startX, startY });
    oilMap[startX][startY] = areaNum;
    isVisited[startX][startY] = 1;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        tmp++;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nextX = x + directionX[i];
            int nextY = y + directionY[i];
            if (nextX >= 0 && nextX < sizeOfLandX && nextY >= 0 && nextY < sizeOfLandY && isVisited[nextX][nextY] == false && oilMap[nextX][nextY]>0) {
                oilMap[nextX][nextY] = areaNum;
                isVisited[nextX][nextY] = 1;
                q.push({ nextX,nextY });
            }
        }
    }
    sizeOfOil[areaNum] = tmp;
    areaNum++;
   
}
int solution(vector<vector<int>> land) {
    int answer = 0;
    oilMap = land;
    sizeOfLandX = land.size(); //열의 길이
    sizeOfLandY = land[0].size(); //행의 길이

    for (int i = 0; i < sizeOfLandX; i++) {
        for (int j = 0; j < sizeOfLandY; j++) {
            if (isVisited[i][j] == false && land[i][j] == 1) {
                BFS(i, j);
            }
        }
    }

    for (int j = 0; j < sizeOfLandY; j++) {
        set<int> oilSet;
        int sumOfOil=0;
        for (int i = 0; i < sizeOfLandX; i++) {
            oilSet.insert(oilMap[i][j]);
        }
        set<int>::iterator iter;
        for (auto it : oilSet) {
            sumOfOil += sizeOfOil[it];
        }
        answer = max(answer, sumOfOil);
    }

    return answer;
}

일단 이 문제의 경우 내가 블로그에 기존에 올렸던 BFS보다 간단 하다 원래는 Direction을 일일히 내가 정해줬었는데 이를 배열에 넣어 간단하게 보이게 했다. 코드 가독성이 올라가니 확실히 디버깅 효율이 올라갔다

자 일단 이문제의 핵심로직은 BFS로 구해놓은 영역의 유전의 크기를 영역별로 들고 있어야 한다 이를 위해 위 코드에

void BFS(int startX, int startY ) {
    int tmp = 0;
    queue<pair<int, int>> q;
    q.push({ startX, startY });
    oilMap[startX][startY] = areaNum;
    isVisited[startX][startY] = 1;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        tmp++;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nextX = x + directionX[i];
            int nextY = y + directionY[i];
            if (nextX >= 0 && nextX < sizeOfLandX && nextY >= 0 && nextY < sizeOfLandY && isVisited[nextX][nextY] == false && oilMap[nextX][nextY]>0) {
                oilMap[nextX][nextY] = areaNum;
                isVisited[nextX][nextY] = 1;
                q.push({ nextX,nextY });
            }
        }
    }
    sizeOfOil[areaNum] = tmp;
    areaNum++;
   
}

BFS 부분에서sizeOfOil에 저장해 주었다 여기서 sizeOfOil은 맵 자료형이다 맵자료형은 map<int,int>이렇게 사용했을 때 맨앞에 오는 값은 Key로서 두번쨰 오는 값은 value로 써 작용합니다.
즉 map<key, value> 의 형태로 각각의 해당하는 자료형을 넣어주면 됩니다 .

이 문제에서는 Map의 저장해놓은 데이터를 순환하여 찾아와야 하기 때문에

for (auto iter = m.begin() ; iter !=  m.end(); iter++)
{
	cout << iter->first << " " << iter->second << endl;
}
cout << endl;

의 형태와

for (auto iter : m) {
	cout << iter.first << " " << iter.second << endl;
}

의 형태의 두가지 형태로 map을 순환 할 수 있습니다.
이에 필자는 두번째 형태로 사용하였습니다. 

이렇게 Map형태로 저장해놓은 데이터에서 우리는 land 배열에 새로줄에서 만나는 areaNum들을 set에 넣어줍니다.
Set은 마찬가지로 중복되는 자료를 넣으면 넣지 않기 때문에 areaNum을 최대 1번씩만 넣을 수 있습니다
이에 set.insert를 이용해서 각 세로줄에 있는 유전의 areaNum을 넣습니다.

그후 이를 순회하면서 areaNum을 통해 세로줄에 있는 해당 유전에 크기를 더하여 최대값을 출력합니다

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

이 문제의 경우 전형적인 BFS 문제이다

자기와 연결되어 있는 루트를 BFS로 계속 따라가며 이어져있는 모든 점에 대해 표시만 해주면 되는 쉬운 문제다

#include <iostream>
#include <queue>
#include <vector>

using namespace std;
int N;
int arr[100][100];
int ans[100][100];
void solution(int vertex) {
	queue<pair<int, int>> bfsq;
	for (int i = 0; i < N; i++) {
		if (arr[vertex][i] == 1) {
			bfsq.push({ vertex, i });
			ans[vertex][i] = 1;
			while (!bfsq.empty()) {
				int start = bfsq.front().first;
				int end = bfsq.front().second;
				bfsq.pop();
				for (int j = 0; j < N; j++) {
					if (arr[end][j] == 1 &&ans[vertex][j]==0) {
						bfsq.push({ end,j });
						ans[vertex][j] = 1;
					}
				}
				
			}
		}
		
	}

}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = 0; i < N; i++) {
		solution(i);
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << ans[i][j]<<" ";
		}
		cout << endl;
	}
}

solution 함수를 설명을 하자면 solution  함수를 실행하면 매게변수로 vertex 즉 시작점이 넘어간다

그 후 arr를 참고하여 나와 연결되어있는 애들을 차례로 큐에 넣어준 후 차례로 pop시키며 그 애들과 연결된 애들을
계속 push한다 함과 동시에 ans배열에 값을 1로 바꿔준다.

예를들어 input으로

7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0

이렇게 들어 갔다고 치자 solution(1)을 실행시키면

현재 큐에 나와 연결되어 있는 0,4가 큐에 들어간다.

그후 0,4가 pop 되며 4와 연결되어 있는 4,5와 4,6이 들어간다

이와 동시에 ans[0][5]와 ans[0][6]의 값을 1로 바꿔준다.

그후 다시 4,5를 pop하면서

5,1을 큐에 넣어준다 그후 ans[0][1]을 1로 바꿔준다

그후 4,6을 pop한다

그후 6,7을 푸쉬하면서 ans[0][7]을 1로 바꿔준다

이러한 방식을 반복하면서 진행이된다. 

그럼 이런식으로 해당 Vertex와 연결되어 있는 부분을 나타내주는 배열이 만들어진다

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

이 문제의 경우 생각해줘야할 게 많았다 일반 Bfs지만 문제를 잘 읽지 않으면 틀린다

이문제에서 간과하면 안될 조건이 있다.

1. 시작점에 사다리와 뱀이 여러개 놓일 수는 없지만 도착점은 상관없다.

2. 뱀과 사다리를 만나면 무조건 이동한다 이다 즉 발판을 밟지 못한다.

이 위를 생각하고 풀어야 빠른시간안에 풀 수 있었다 필자는 이 부분을 캐치하지 못 해 오랜시간이 걸렸다.

#include <iostream>
#include <queue>
using namespace std;
int arr[101];
int visited[101];
int radder[101];
queue<int> bfsq;
int solution() {
	bfsq.push(1);
	while (!bfsq.empty()) {
		int start = bfsq.front();
		bfsq.pop();
		if ((start + 6 <= 100) && !visited[start + 6]) {
			if (radder[start + 6] > 0) {
				if (visited[radder[start + 6]] == 0) {
					visited[radder[start + 6]] = visited[start] + 1;
					bfsq.push(radder[start + 6]);
				}
			}
			else if (radder[start + 6] == 0) {
				visited[start + 6] = visited[start] + 1;
				bfsq.push(start + 6);
			}
			if (start + 6 == 100)
				return visited[start + 6];
		}
		if ((start + 5 <= 100) && !visited[start + 5]) {
			if (radder[start + 5] > 0) {
				if (visited[radder[start + 5]] == 0) {
					visited[radder[start + 5]] = visited[start] + 1;
					bfsq.push(radder[start + 5]);
				}
			}
			else if (radder[start + 5] == 0) {
				visited[start + 5] = visited[start] + 1;
				bfsq.push(start + 5);
			}
			if (start + 5 == 100)
				return visited[start + 5];
		}
		if ((start + 4 <= 100) && !visited[start + 4]) {
			if (radder[start + 4] > 0) {
				if (visited[radder[start + 4]] == 0) {
					visited[radder[start + 4]] = visited[start] + 1;
					bfsq.push(radder[start + 4]);
				}
			}
			else if (radder[start + 4] == 0) {
				visited[start + 4] = visited[start] + 1;
				bfsq.push(start + 4);
			}
			if (start + 4 == 100)
				return visited[start + 4];
		}
		if ((start + 3 <= 100) && !visited[start + 3]) {
			if (radder[start + 3] > 0) {
				if (visited[radder[start + 3]] == 0) {
					visited[radder[start + 3]] = visited[start] + 1;
					bfsq.push(radder[start + 3]);
				}
			}
			else if (radder[start + 3] == 0) {
				visited[start + 3] = visited[start] + 1;
				bfsq.push(start + 3);
			}
			if (start + 3 == 100)
				return visited[start + 3];
		}
		if ((start + 2 <= 100) && !visited[start + 2]) {
			if (radder[start + 2] > 0) {
				if (visited[radder[start + 2]] == 0) {
					visited[radder[start + 2]] = visited[start] + 1;
					bfsq.push(radder[start + 2]);
				}
			}
			else if (radder[start + 2] == 0) {
				visited[start + 2] = visited[start] + 1;
				bfsq.push(start + 2);
			}
			if (start + 2 == 100)
				return visited[start + 2];
		}
		if ((start + 1 <= 100) && !visited[start + 1]) {
			if (radder[start + 1] > 0) {
				if (visited[radder[start + 1]] == 0) {
					visited[radder[start + 1]] = visited[start] + 1;
					bfsq.push(radder[start + 1]);
				}
			}
			else if (radder[start + 1] == 0) {
				visited[start + 1] = visited[start] + 1;
				bfsq.push(start+1);
			}
			if (start + 1 == 100)
				return visited[start + 1];
		}
	}
}
int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N+M; i++) {
		int from, to;
		cin >> from>> to;
		radder[from] = to;
	}

	cout << solution();
}

코드가 길지만  사실 실제로 보면 얼마 안되는 양이다.

일단 주목해야할 부분은

		if ((start + 6 <= 100) && !visited[start + 6]) {
			if (radder[start + 6] > 0) {
				if (visited[radder[start + 6]] == 0) {
					visited[radder[start + 6]] = visited[start] + 1;
					bfsq.push(radder[start + 6]);
				}
			}
			else if (radder[start + 6] == 0) {
				visited[start + 6] = visited[start] + 1;
				bfsq.push(start + 6);
			}
			if (start + 6 == 100)
				return visited[start + 6];
		}

이 부분이다 이부분의 경우느 일단 우리가 방문할려는 지점이 방문되었는지 또한 우리가 방문할 발판이 100을 넘었는지를 검사한다. 넘으면 실행 하지 않는다 그후 사다리나 뱀이 있다면 그 발판을 밟지 않고 이어져있는 발판을 밟는다 그 후 이를 bfs에 넣는다. 만약 사다리나 뱀이없으면 해당 발판을 밟는다. 이게 풀이 로직이었다. 

코테에서 항상 중요한 점은 빠른시간안에 반례체킹을 하는 것인거 같다.

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

이 문제의 경우 쉬운 전형적인 bfs문제이다. 모든 정점을 시작점으로 bfs를 돌린다 그 후 정점을 시작점으로 돌리는 케이스마다의 각 정점의 layer의 합을 저장한 후 이를 비교하여 최솟값을 갖는 정점의 값을 출력해 주면 되는 문제였다

bfs의 기본적이 풀이 로직은 이 블로그의 다른글들에 있다. 코드는 아래와 같다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, M;
vector<int> bfsv[101];
int arr[101] = { 0, };
int main() {
	queue<pair<int, int>> bfsq;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int temp1, temp2;
		cin >> temp1 >> temp2;
		bfsv[temp1].push_back(temp2);
		bfsv[temp2].push_back(temp1);
	}
	for (int i = 1; i <= N; i++) {
		int start = i;
		bfsq.push({ start,0 });
		bool isVisited[101] = { 0, };
		while (!bfsq.empty()) {
			int front = bfsq.front().first;
			int second = bfsq.front().second;
			arr[front] += second;
			isVisited[front] = true;
			bfsq.pop();
			for (int j = 0; j < bfsv[front].size(); j++) {
				if (!isVisited[bfsv[front][j]]) {
					bfsq.push({ bfsv[front][j], second + 1 });
					isVisited[bfsv[front][j]] = true;
				}
			}
		}
	}
	int min=5001;
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		if (min > arr[i]) {
			ans = i;
			min = arr[i];
		}
	}
	cout << ans;
}

이 문제의 경우 나에게 여러가지 에러를 보여줌으로 여러가지 함수를 사용할 때 주의 할점을 알려줬다. 일단  이 문제의 코드는 이렇게 된다

#include <iostream>
#include <queue>
#include <vector>
#define INT_MAX 2147483647
using namespace std;
vector<int> distanceV(20002); //시작점 부터 다른 정점까지의 거리를 저장
vector<bool> visited;
void djikstra(int start, vector<pair<int, int>> dijkstraGraph[]) {
	priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 거리, 노드 인덱스
	pq.push(make_pair(0, start));
	distanceV[start] = 0;

	while (!pq.empty()) {
		int distanceOfTo = pq.top().first;
		int toVertex = pq.top().second;
		pq.pop();

		if (distanceOfTo > distanceV[toVertex]) {
			continue;
		}

		for (int i = 0; i < (int)dijkstraGraph[toVertex].size(); i++) {
			int cost = distanceOfTo + dijkstraGraph[toVertex][i].second;
			int nextIndex = dijkstraGraph[toVertex][i].first;
			if (cost < distanceV[nextIndex]) {
				distanceV[nextIndex] = cost;
				pq.push(make_pair(cost, nextIndex));
			}

		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int vertex, edge, start;  //vertex는 정점 edge는 간선 start는 시작점을 입력 받는다.
	cin >> vertex >> edge >> start;
	vector<pair<int, int>> dijkstraGraph[20002];//다익스트라 알고리즘의 비용을 저장할 우선순위 큐
	for (int i = 1; i <= edge; i++) {
		int from, to, cost;  //from은 간선사이의 시작점,to는 도착점 , cost는 간선의 비용을 의미
		cin >> from >> to >> cost;
		dijkstraGraph[from].push_back(make_pair(to,cost));
	}
	distanceV.assign(20002, INT_MAX);
	djikstra(start, dijkstraGraph);
	for (int i = 1; i <= vertex; i++) {
		if (distanceV[i] == INT_MAX) {
			cout << "INF"<<endl;
		}
		else {
			cout << distanceV[i] << endl;
		}
	}
}

이 문제의 경우 일단 간선의 방향이 단 방향이다. 일단 이문제의 예시 input에 대한 과정의 그림을 첨부하겠다

이 그림 에서 원으로 되어 있는 그래프는 위에 dijkstra함수에 pq를 그린것이다. 밑에 배열은 distanceV를 그린것이다.

일단 처음 풀이에서

distanceV.assign(20002, INT_MAX);

이 코드를 통해 배열에 큰 값을 다 넣어주었다 이에 처음 벡터에는 INF값만 가득하다 그후 1,0 즉 시작점 1에서 도착지 1로가는 거리는 자기자신이므로 0을 넣어준다 그후 2,2순으로 pq순에서 팝되는 값과 나와 연결되어 있는 다음 인덱스의 값을 더해서 distanceV에 거리를 갱신해 준다. 즉 1이 팝되었을때는 2,3의 거릿값이 갱신된다. 이후 2가팝되었을 때는 3과 4에 연결되어있으므로 시작점부터 자기자신까지의 거리와 나랑 연결되어 있는 노드의 값을 더해서 만약 원래 그 노드까지의 거리보다 나를 통해 가는 거리가 짧으면 그 노드쪽의 값을 갱신해주고 아니면 넘어간다 이런식으로 계속 나까지의 거리와 다음 노드까지의 거리를 계속 갱신해주면서 최소 거리를 구하면 된다.