백준/그래프 (24) 썸네일형 리스트형 백준 30689 - 미로 보수 https://www.acmicpc.net/problem/30689 이 문제는 단순히 "사이클로 들어가는" 노드 중에서 최소 비용을 가진 노드만 택하면 틀렸습니다를 받는다. 문제에 주어진 그래프는 함수형 그래프인데, 이런 경우가 흔히 발생할 수 있기 때문이다. 단순한 사이클 찾기를 통해 그룹을 묶는다면, 그림과 같이 문제 조건에서 고려할 수 있는 유의미한 사이클 외에 1, 2번 노드에서 비용을 고르는 경우가 생길 수 있다. 따라서 문제를 해결하기 위해서는 유효한 사이클만 검출하도록 할 필요가 있다. 그러기 위해서는 그래프의 모든 노드에서 엣지를 따라가되, 이미 방문했지만 종결되지는 않은 노드로 다시 방문하게 되는 순간, 해당 노드부터 시작하는 "유의미한 사이클"을 추적하여 최소 비용을 찾도록 하면 된.. 백준 27915 - 금광 https://www.acmicpc.net/problem/27915 문제에서 가장 중요한 점은 한 기업은 최대 2개의 노드만 소유할 수 있다는 것이다. 왜냐하면 3개 이상의 노드를 점유한다고 했을 때 각 노드가 홀수의 거리를 유지한다고 해도 양 끝의 노드의 거리가 짝수가 되기 때문이다. 따라서 각 기업은 무조건 홀수 레벨에서 짝수 레벨로만 연결할 수 있고, 이는 색 $R, B$로 구성된 이분그래프로 표현할 수 있다. 이렇게 이분그래프를 만들었을 때 $max(|R|, |B|)$가 정답이 된다. 정답 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162.. 백준 2224 - 명제 증명 https://www.acmicpc.net/problem/2224 주어지는 명제는 알파벳만 주어진다. 이때 알파벳을 아스키코드로 생각하면 명제의 범위를 대략 140 이내로 한정할 수 있으며 그렇게 되면 테이블이 dp[140][140]인 플로이드 워셜 알고리즘으로 해결할 수 있음을 알 수 있다. 주어진 입력을 인접 행렬로 표현해주고 플로이드 워셜을 수행한 후 전건과 후건이 연결된 것을 찾아 출력해주면 된다. 다만 a => a와 같이 자기와 같은 것은 친다고 하지 않으니 이를 유의하며 찾도록 한다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 .. 백준 16681 - 등산 https://www.acmicpc.net/problem/16681 힌트 더보기 집 -> 어떤 지점 방향으로는 올라가고 어떤 지점 -> 고려대학교 방향으로는 내려간다... 여기서 어떤 아이디어를 떠올릴 수 있겠는가? 풀이 더보기 어떤 지점 $X$를 기준으로 내려가야 되는 경로와 올라가는 경로가 다르다. 이를 살펴보면 $X$에서 고려대학교까지 내려가는 것은 고려대학교에서 $X$까지 올라가는 것과 같다. 따라서 다음과 같은 아이디어를 생각할 수 있다. 1. 집에서 올라가는 최단 경로 $sp_{1, x}$들을 계산한다. 2. 고려대학교에서 올라가는 최단 경로 $sp_{2, x}$들을 계산한다. 3. 어떤 지점 i에서 $sp_{1, i}$ 와 $sp_{2, i}$가 존재하면 i를 기준으로 문제 조건에 맞는 등산.. 백준 1525 - 퍼즐 https://www.acmicpc.net/problem/1525 힌트 더보기 필요한 것: string 가능한 경우의 수: 9! 풀이 더보기 한 군데가 비어있는 퍼즐을 오름차순으로 배치하는 최소 횟수를 찾는 문제다. 비어있는 위치를 9라고 하면 1 2 3 4 5 6 7 8 9 의 형태로 퍼즐을 만드는 문제로 바꿀 수 있다. 그리고 이를 일렬로 나열하면 일직선 퍼즐을 123456789로 만드는 문제로 바꿀 수 있다. 퍼즐의 각 위치에서 이동할 수 있는 곳에 에지를 연결하면서 그래프 모델링을 하자. 그러면 현재 퍼즐의 상태가 주어졌을 때 숫자가 9인 노드는 연결된 노드의 숫자와 swap 할 수 있다는 의미가 된다. 123456789를 기준으로 9는 6, 8과 swap이 가능하다. 즉 9가 위치한 노드와 연결.. 이전 1 2 3 4 5 다음
