2017/06/15 썸네일형 리스트형 BOJ)12922 블럭 퍼즐 문제: icpc.me/12922 1x1x2 블럭이 정사각형 그리드에서 이동할 때 게임승리를 불가능하게 뚫어야하는 구멍의 수를 출력하는 문제이다. 문제에서 블럭의 이동경로를 살펴보면 시작점에서 부터 4방향으로 3칸 떨어진 지점에만 서있을 수 있다. 이를 이용하여 모든 정점에서 3칸 떨어진 지점으로 그래프를 구성해주는데 이 때 간선의 capacity는 지나가는 경로에 뚫어야하는 구멍 수가 되야되고 해당 정점에 구멍을 뚫는 경우는 정점을 분할하여 사이에 capacity를 1로 주는걸로 그래프를 모델링 해주면 src에서 sink로의 mincut을 구해주면 답을 구해낼 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142.. 더보기 BOJ)12963 달리기 문제: icpc.me/12963 N개의 정점과 M개의 간선으로 이루어진 그래프에서 0번정점에서 N-1번 정점으로 이동 가능한 사람의 최대 수를 구하는 문제이다. 얼핏보면 그냥 0번 정점에서 N-1번 정점으로의 maximum flow를 구하는 문제로 볼 수 있겠지만 한가지 문제가 있다. 간선의 capacity가 너무 커지기 때문에 modulo작업이 필수가 되는데 이와 같은 환경에서 maximum flow를 잘 처리해줄 수가 없기 때문이다. 따라서 우리는 조금 그리디하게 접근을 해야한다. 그래프에서 가장 큰 간선의 가중치는 나머지 모든 간선의 가중치의 합보다 크기 때문에 그 간선으로 이동가능한 경우가 그리디하게 최대가 된다. 그렇기 때문에 그 간선을 연결해보고 0에서 N-1 정점으로 이동가능하면 그 가중치만.. 더보기 이전 1 다음