방학에 못풀어서 넘어간 문제다다익스트라로 풀면 되는데 K개의 도로를 포장한다는게 굉장히 걸린다 다익스트라를 돌리면서 dp를 사용하여 풀 수 있다.d[here][cnt] 테이블을 잡고 here까지 오는데 cnt개의 도로를 포장했을 때로 생각하면 된다 기존 다익스트라 +만약 cnt d[here][cnt] 라면 도로를 포장해준다 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include #include #include #include #include using namespace std;int n, m, k;vector Graph;int d[10010][..
영우는 바쁘다. 기숙사 청소를 해야하는지 알려줘야 한다BFS 그냥 돌리면 시간초과가 난다..!그냥 돌리면 방문한 곳을 다음에 다시 또 방문하게된다! 방법은 바로 이전에 방문한 곳을 체크해 두고 방문 안했을 경우에만 큐에 넣는다! 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include #include #include #include using namespace std;int arr[333][333];bool check[333][333][2];int n, m, k, t;int dx[8] = { -1,-2,-2,-1,1,2,2,1 };in..
시작점에서 끝점까지 가는데 가장 긴 경로를 출력하고 그때 지나가는 길의 수출력하는 문제다..! 가장 긴 경로 구하는건 쉬웠는데 지나온 길 찾는게 어려워따 ㅎㅎ백준의 도움을 받아따 ㅎㅎ 문제는 위상정렬을 이용해서 풀었다! 위상정렬로 가장 긴 경로는 d[next] = max(d[next] , d[here]+cost)로 구할 수 있다 그리고 지나온 경로는 역으로 그래프를 만들어서 방문한 점중에 가장 긴 경로와 지나온 거리가 같다면 카운트를 올리는 식으로 했다! DAG에서 가장 긴 경로 구하는 문제로 기억해둬야지 ㅎㅎ 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657..
정점 N개, 간선 N-1개 트리가 주어지고 루트를 알려준다.그리고 루트에서 리프노드로 가면 탈출 가능할 때리프노드에 탈출을 막는 사람을 몇명 둬야하는지 찾는 문제이다. 탈출을 막는 사람과 탈출 하려는 사람의 속도는 같다. 처음에 시도한 방법은 dfs를 돌려서 리프노드에 도착했을 때 루트와 가장 가까운 두갈래 이상의 길을 찾아서 그 정점에 거리를 넣었다.그리고 마지막에 정점을 다 보며 거리가 들어있으면 루트에서 그 정점까지 거라와 들어있는 거리를 비교해서 수를 세는 것이였는데바로 망했다 ㅎㅎ 7퍼에서 틀린다. 생각해보니 예외가있따 ㅎㅎ 문제를 푸는 방법을 봤따 ㅎㅎ푸는 방법은1. 각 정점에서 루트까지 거리와 가장 가까운 리프까지 거리를 구한다2. 모든 정점을 돌아보며 3. 루트가 아니고 && 리프까지 거리..