본문 바로가기

알고리즘 관련/UVaOJ

UVaOJ)12797 Letters 문제:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4662 NxN의 맵이 주어질 때 1,1에서 n,n까지의 최단거리를 구하는 문제이다. 단 제약조건이 있는데 발판으로 주어지는 알파벳중에 대문자나 소문자 하나를 정해놓고 일관성있게 밟아야 한다. 알파벳이 최대 10개밖에 없기 때문에 상태에 대하여 비트마스킹을하여 넘겨주어 BFS를 1024번만 돌려주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #incl.. 더보기
UVaOJ)11765 Component Placement 문제: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2865 N개의 정점이 있을 때 N개의 정점이 상단에 연결되어야 하는지 하단에 연결되어야 하는지 여부를 구해주어야 하는 문제이다. 각각 상단에 연결되었을 때와 하단에 연결되었을 때의 비용이 주어지며 반드시 상단에 연결되어야 하는 경우, 반드시 하단에 연결되어야 하는 경우, 둘다 가능한 경우가 주어진다. 이 후 M개의 정보가 주어지는데 이 정보는 x 와 y 정점이 같은 곳(상단or 하단)에 연결되지 않았을 경우 생기는 추가비용이다. 이 때 모든 정점을 연결하였을 때 최소비용을 구하는 문제이다. 이 문제를 최소컷 문제로 변형해서 푼다고 생각을 하면 하나의.. 더보기
UVaOJ)12159 Gun Fight 문제:https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3311 N개의 power가 존재하는 점이 주어지고 진영을 가르는 직선을 결정하는 두 점이 주어진다. 두 점으로 부터 진영을 갈라서 수가 적은 진영이 수가 많은 진영을 이기도록 최대한 매칭할 수 있는 수를 출력하는 문제이다. ccw를 이요하여 모든 점의 진영을 구해준 뒤 진영이 적은 쪽에서 진영이 많은 쪽으로 두 점 사이의 거리가 R이하이고 Power가 0이상이고 진영이 적은 쪽의 power가 진영이 많은쪽의 power보다 많은 두 점을 서로 매칭시켜준 뒤 최대매칭을 구해주면 된다. 123456789101112131415161718192021222324.. 더보기
UVaOJ)12878 Flowery Trails 문제:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4743 그래프에서 0번 정점에서 n-1번 정점으로의 여러경로의 최단거리에 속한 간선들의 가중치의 합을 구하는 문제이다. 한 정점에서 한 정점으로의 최단거리가 유일하다면 경로의 가중치의 합을 구하는건 그렇게 어렵지 않게 풀 수 있다. 하지만 최단거리가 여러가지 경로가 있다면 다익스트라를 이용할 시 그걸 구하는 시간만해도 꽤 오랜 시간이 걸릴 수 있다. 처음 문제를 접근할 때 다익스트라를 돌리며 일일이 경로를 다 저장하여 역추적을 하여 tle를 받게되었다. 하지만 잘 생각해본다면 다익스트라(혹은 spfa) 두번의 전처리로 문제를 해.. 더보기
UVaOJ)10968 KuPellaKeS 문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1909 도시가 주어질 때 연결 된 도시의 개수가 홀수개인 도시들을 몇개의 다리를 파괴하여 전부 2이상의 짝수개의 정점만 연결되게 만들어주려고 할 때 제거해야하는 최소 간선의 개수를 출력하는 문제이다. 연결 된 도시의 간선이 홀수인 정점이 2개 이하라는 조건도 있다. 우선 연결 된 도시의 간선이 홀수개인 정점이 두개가 있다고 생각해보자. 그렇다면 우리는 두 도시에 연결 된 간선을 하나씩 지워줘야 한다. 이 때 하나씩 지우면 반대쪽 정점들의 간선의 개수가 홀수가 되기 때문에 또 지워줘야한다. 이렇게 서로 지우다가 한 간선에서 만나.. 더보기
UVaOJ)12645 Water Supply 문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4393 오염된 물을 정화하기 위해서 단방향 그래프에서 0번 정점에서 나오는 정화제를 x개의 간선을 추가하여 모든 정점에 뿌려야할 때 연결해야하는 간선 x개의 최솟값을 구하는 문제이다. 이 문제는 정점들을 scc로 묶어준다음 위상정렬을 통하여 해결가능하다. 즉 0번 정점을 포함한 scc를 제외한 indegree가 0인 scc의 개수를 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545.. 더보기
UVaOJ)11751 Installing Diagnostic Software 문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2851 확실한 번역은 모르겠지만 대략적인 설명은 간선이 주어질 때 해당 간선에 연결 된 두정점중 하나는 반드시 소프트웨어가 설치되어야 할 때 최소비용으로 소프트웨어를 설치하는 방법을 출력하는 문제이다. 소프트웨어 설치비용은 i번 정점의 경우 2^i의 비용이 소모된다. 즉 i번 정점에 소프트웨어를 설치하는건 0~i-1번 정점 모두에 소프트웨어를 설치하는것보다 비싸다 그렇기 때문에 최대한 작은 정점에 소프트웨어를 설치해야한다. 이를 위하여 간선에 연결 된 두 정점 중 작은 정점에 설치를 해야함은 자명하다. 그렇다면 이제 문제는 간.. 더보기
UVaOJ)12460 Careful teacher 문제: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3891 문제를 간략하게 설명하면 사전에 존재하는 단어들이 주어진 뒤 쿼리가 들어올 때 쿼리에서 들어오는 두 단어를 A와 B라고할 때 A를 B로 바꿀 수 있는지 여부를 물어보는 문제이다. 이 때 A를 B로 바꾸는 경우는 한글자 씩 바꿀 수 있으며 단, 한글자를 바꾼 단어도 사전에 존재하여야만 바꿀 수 있다. 이 문제는 사전에 존재하는 단어들을 정점으로 생각하고 1글자 다른 단어들을 간선으로 묶어주면 A와 B가 같은 컴포넌트에 존재하는지 여부를 묻는 문제로 변형된다. 이는 disjoint-set을 통하여 해결해줄 수 있다. N제한이 20000이지만 시간.. 더보기