플로이드 와샬 알고리즘을 이용해서 풀었다. 자세한 방법은 아래의 블로그에서 공부해보면 좋을 것 같다. [알고리즘] 플로이드 와샬 (Floyd Warshall) 목차 플로이드 와샬이란? 다익스트라 알고리즘은 하나의 노드에서 출발했을 때 다른 모든 노드로의 최단 경로를 구하는 알고리즘이다. 하지만 플로이드 와샬 알고리즘은 모든 노드에서 모든 노 propercoding.tistory.com 플로이드 와샬 알고리즘은 A 노드에서 B 노드로 가는 가장 최소한의 길이를 구하는 방법에 사용되는데 거쳐가는 노드를 이용해서 최소한의 길이를 구하는 방법이다. 이 플로이드 와샬 알고리즘의 개념은 어떤 식으로 문제에 대입해서 결과를 도출해내는 것일까? 만약에 A와 B의 관계를 알고 싶다. 하지만 A,C의 관계 정보 C, B의..
프로그래머스
#include #include #include #include using namespace std; int solution(vector clothes) { int answer = 1; map collector; for (vector cloth : clothes) { collector[cloth[1]]++; } for (auto &value : collector){ answer *= value.second + 1; } return answer - 1; } 사실 쉬운 문제인데, 어떻게 풀어야할지 헷갈렸었다. 그런 문제는 보면 조합으로 모든 경우의 수를 찾아봐야하나? 이런 생각도 들고 그랬지만 특정 케이스를 찾는 것이 아닌, 경우의 수만 구하면 되기 때문에 의상 수에 +1을 해서 다 곱하고 -1을 하면 아무..
#include #include #include #include using namespace std; int solution(int n, vector edge) { int answer = 0; vector graph(20001); vector visited(20001, 0); queue queue; vector counts(20001, 0); for (vector line : edge){ graph[line[0]].push_back(line[1]); graph[line[1]].push_back(line[0]); } queue.push(1); visited[1] = 1; int prev = 1; int next = 0; while (queue.size() != 0){ int num = qu..
