본문 바로가기

STUDY

 (129)
[C++/LeetCode] Network Delay Time Daily LeetCoding Challenge May, Day 14 문제: 최장 거리 판별하기 아이디어: Dijkstra 신호가 전달되는 시간은 가장 긴 시간에 의해 영향 받는다. 따라서 시작 노드부터 다른 노드까지의 최단 거리를 구하고, 그 중 가중치가 가장 큰 값이 바로 Delay Time이 된다. 완성 submission: 120ms / 39.8MB class Solution { public: void dikjstra(vector graph[], vector &dist, int start) { // 우선 순위 큐 사용 priority_queue q; // 시작 노드를 넣고 이때의 가중치는 0이다. 시작 노드의 거리는 0으로 초기화 q.push({0, start}); dist[start] = 0; ..
[C++/3665] 최종 순위 - using 위상 정렬 (topology sort) 문제 아이디어: 위상 정렬 문제에서는 "순위"를 나열해야 하기 때문에 방향 그래프라는 것을 쉽게 알 수 있다. 이를 순위에 맞게 나열하는 것은 방향 그래프를 정렬하는 것과 같으므로 위상 정렬을 사용할 수 있다. 이때 사이클이 없는 위상 정렬은 항상 노드가 N개 일때 queue를 N번 돌기 때문에, 사이클이 생긴다면 N보다 작은 횟수로 종료하게 된다. 왜냐하면 진입 차수가 0이 되는 노드가 없어서 더 이상 탐색을 진행할 수 없기 때문이다. 따라서 이 경우 쉽게 "IMPOSSIBLE" 인 경우를 알 수 있다. 데이터의 일관성이 없는 경우 "?"를 출력하라고 하였는데 이는 같은 등수인 노드가 여러개인 경우이다. 이 오류는 queue에 들어간 node의 갯수가 몇개인지에 따라 알 수 있다. 즉 2개 이상의 no..
[C++/16236] 아기 상어 - using BFS 문제 아이디어: BFS 가장 가까운 물고기부터 먹어야 하기 때문에 물고기까지의 최단 거리중 가장 짧은 물고기를 먹을 수 있는지 아닌지 체크하면서 물고기를 차례대로 확인하면 된다. 구현 // 46: 아기 상어 (삼성 기출) #include #include #include #include using namespace std; // 북 서 남 동 int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; // n(공간의 크기) int n; int weight = 2; // 거리 테이블 int dist[20][20]; void BFS(vector &v, int i, int j) { queue q; dist[i][j] = 0; q.push({i, j}); while (!q.e..
[C++/7576] 토마토 - using BFS 문제 아이디어: BFS 진짜 전형적인 BFS 응용 문제이다. 토마토가 익는 시간을 함께 queue에 넣어서 저장한 다음, 익는 시간이 특정 시간을 지나고 나면 하루가 지난 것으로 판별해야 한다. 또한 맨 처음에 queue에 넣는 좌표는 토마토가 있는 좌표를 모두 넣는다. 이때 시간대는 모두 0으로 초기화 한다. 토마토가 이동할 수 있는 동서남북 4 방향에 대해서 토마토가 없는 경우에 값을 바꾸고 queue에 넣어준다. 이때는 (이전시간 + 1)로 설정하여서 넣어준다. 구현 #include #include #include #include using namespace std; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int m, n; int graph[..
[C++/2887] 행성 터널 - using MST : Kruskal Algorithm 문제 아이디어: 최소 비용으로 그래프를 완성하는 전형적인 MST 문제이다. Kruskal 알고리즘을 사용하였다. 여기서 중요한 점은 간선 정보를 입력받은 후, 간선의 비용은 직접 abs와 min으로 직접 구해야한다는 것이다. 풀이: #include #include #include #include using namespace std; int parent[100000]; int findParent(int x) { return (parent[x] == x ? x : parent[x] = findParent(parent[x])); } void unionParent(int a, int b) { a = findParent(a); b = findParent(b); if (a < b) parent[b] = a; els..
[C++/16234] 인구 이동 - using BFS 문제 아이디어: BFS 연합 정보를 기록하는 vector를 만들어서 인구 수 차이가 연합을 생성할 수 있다면 vector에 좌표를 추가하고 마지막에 인구 수를 나눠서 저장한다. // 동 서 남 북 int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int L, R; void process(vector &v, vector &unions, int x, int y, int index) { // 연결된 연합 도시 정보 vector united; united.push_back({x, y}); // BFS queue queue q; q.push({x, y}); unions[x][y] = index; int sum = v[x][y]; // 인구 수 총합 int count ..
[C++/3190] 뱀 - Implementation 문제 아이디어: 좌표를 저장하는 vector를 만들고, 사과가 없는 경우 꼬리를 자르기 위한 vector를 따로 만들어서 관리한다. #include #include #include using namespace std; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; int main() { // N(보드 크기), K(사과 수), L(뱀 회전 수) int N, K, L; int result = 0; cin>>N; vector v(N, vector(N, 0)); cin>>K; for(int i = 0;i >a>>b; v[a - 1][b - 1] = 1; } vector snake; cin>>L; for(int i = ..
[C++/18405] 경쟁적 전염 - using BFS 문제 아이디어: BFS 바이러스의 위치 좌표를 queue에 넣어서 이를 확인하며 바이러스가 진행할 수 있는 칸의 값을 바꾸며 탐색을 진행한다. #include #include #include using namespace std; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int main() { // N(시험관 크기), K(바이러스 종류) int N, K; cin>>N>>K; vector v(200, vector(200, 0)); vector virus[1001]; for(int i = 0;i >temp; v[i][j] = temp; if (temp != 0) ..

티스토리툴바