백준/그래프 (22) 썸네일형 리스트형 백준 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차원 선.. [COCI] 백준 3055 - 탈출 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제를 잘 이해해야 한다. 이동과 범람이 동시에 일어난다고 되어있다. 주어진 조건대로 이동을 잘 시뮬레이션하기 위해서는 이동을 먼저 한 다음 범람을 일으켜야 한다. 이 순서로 BFS를 진행해서 이동한 위치에 범람이 될 예정인지 아닌지는 신경쓰지 않고 큐에 넣는다. 그다음 범람을 수행한다. 그렇게 이동이 1회 끝난 뒤 다음 큐에서 꺼낼 때 범람된 상태면 해당 노드를 탈락시키고 다음 노드를 꺼내서 확인하면 된다... 이전 1 2 3 4 5 다음
