백준/그래프 (23) 썸네일형 리스트형 백준 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가 위치한 노드와 연결.. 백준 1325 - 효율적인 해킹 https://www.acmicpc.net/problem/1325 A가 B를 신뢰한다는 것은 B가 A를 해킹할 수 있다는 뜻이며 B -> A 방향의 엣지가 주어지는 것으로 이해할 수 있다. 이 문제는 노드가 최대 10000개이며 우리는 감각적으로 PS를 할 때 1초에 1억 번(최근엔 2~3억) 번의 연산을 할 수 있음을 알고 있다. 즉 모든 노드에 대해 일일이 DFS/BFS를 수행하면 노드 한 개가 자기 자신을 포함하여 최대 10000개의 노드를 탐색하므로 $10^{4} \times 10^{4} = 10^{8}$번의 연산을 해야 하고 이는 5초라는 주어진 시간에 걸맞은 풀이가 된다. 각 노드마다 BFS혹은 DFS를 이용하여 최대로 해킹 가능한 컴퓨터가 몇 대인지 세주면 된다. 이렇게 구한 값은 2차원 선.. 이전 1 2 3 4 5 다음
