본문 바로가기

Problem solving70

최단 경로 알고리즘 (BFS, 다익스트라, 벨만 포드, 플로이드 워셜) 최단 경로 문제를 풀 때, 어떤 알고리즘을 선택해야하는지 정리하기 위한 글이다. BFS 2차원 배열에서 최단 경로를 구해야하는 문제를 볼때마다 BFS를 사용해서 문제를 풀었다. 항상 최단 경로 문제를 풀 때마다 이를 활용해서 문제를 풀다가 정답을 구할 수 없는 경우가 발생했다. 바로, 가중치가 있는 경우이다. 위와 같은 그래프가 있을 때, a에서 b로 가는 최단 거리를 구하려고 한다. BFS방식을 사용한다면 a와 연결된 b, d노드로 가게 될 것이고, b노드를 발견한 즉시 탐색을 종료하게 된다. a → b 경로는 12의 거리가 소요되고, a → d → c → b 경로는 9의 거리가 소요되지만 먼저 방문한 노드가 우선시 되는 것이다. 위의 이유로 일찍 만난 노드가 가장 우선시 되어 종료될 수 있는 경우 가.. 2023. 7. 21.
[BOJ] 11779. 최소비용 구하기2 (C++) 문제 n개의 도시와 한 도시에서 출발하여 다른 도시에 도착하는 m개의 버스가 있다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용과 경로 출력 생각할 것 다익스트라 알고리즘 특정 출발지에서 특정 목적지까지의 최소비용을 구해야함 가중치가 있음! ⇒ 다익스트라 사용 최소비용은 구했지만 경로는 어떻게 알 수 있을까? 다음 도시로 가기 전에 현재 도시를 저장한 뒤 역추적하기! priority_queue에서 pair의 second를 오름차순으로 정렬하는 방법 struct cmp { bool operator()(pair &p1, pair &p2) { return p1.second > p2.second; } }; priority_queue pq; 코드 #include #include #include #incl.. 2023. 7. 20.
[LeetCode] 2360. Longest Cycle in a Graph (C++) 문제 방향이 있는 그래프가 주어질 때, 각 노드는 최대 한 개의 나가는 방향의 엣지를 가진다. 엣지들의 길이가 주어졌을 때 길이가 가장 긴 사이클을 구하기. 엣지가 없는경우는 -1의 값을 가진다. 사이클이 없는 경우에는 -1를 리턴 생각할 것 출발 지점과 도착지점이 같은 경우가 사이클에 해당 DFS를 사용해 위 조건을 만족했을 때를 찾기 코드 class Solution { public: int answer = -1; void dfs(int start, int next, int len, vector visited, vector edges){ visited[next] = true; if(start == next) { answer = max(answer, len); } if(edges[next] != -1){.. 2023. 7. 11.
[Programmers] 아이템 줍기 (C++) 문제 직사각형들을 겹친 후 둘레를 따라 이동한다. 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리는? 생각할 것 겹친 사각형들의 테두리를 구해야 할 것이다 안쪽을 모두 1로 채운 뒤에 안쪽을 다시 비워서 테두리를 찾는다 테두리가 인접한 경우 배열만 보고 테두리를 판단할 수 없다 모든 좌표값을 2배로 늘린다. 물론 배열의 크기도 2배로! BFS로 최단 경로를 탐색한 뒤 경로를 다시 2로 나누어준다. 코드 #include #include #include #include using namespace std; int solution(vector rectangle, int characterX, int characterY, int itemX, int itemY) { int answer = 0; // 사각.. 2023. 7. 6.