본문 바로가기

그래프 이론

 (49)
[Python] 8845번 Gra https://www.acmicpc.net/problem/8845 8845번: Gra Dla każdej konfiguracji początkowej w osobnej linii wypisz "W", jeśli Hektor wygra grę przy danym ustawieniu, "P" w przeciwnym przypadku. www.acmicpc.net 23/05/31 스프라그-그런디 정리가 적용되는 게임은 DAG(Directed Acyclic Graph)로 모델링 될 수 있다는 사실을 알고 있다면 쉽게 풀 수 있는 문제이다. 비슷한 문제들로 다음과 같은 문제들을 추천하니, 풀어본다면 좋은 연습이 될 것이다. https://www.acmicpc.net/problem/10363 10363번: Circ..
[Python] 27306번 DAGame https://www.acmicpc.net/problem/27306 27306번: DAGame 첫 번째 줄에 노드의 개수를 나타내는 정수 $N$ ($2 \le N \leq 500$), 간선의 개수를 나타내는 정수 $M$ ($1 \leq M \leq 100\,000$)이 주어진다. 두 번째 줄 부터 $M$개의 줄에 서로 다른 두 정수 $p$, $q$ ($1 \leq p$ www.acmicpc.net 23/05/03 스프라그-그런디 정리에 대한 이해도가 있어야 해결할 수 있는 문제다. 몇몇 사람들은 스프라그-그런디 정리의 문제를 풀 때 결과만 외우고 그냥 XOR계산만 적용해서 문제를 푸는 경우가 좀 있다고 생각한다. 나도 스프라그-그런디 정리를 적용한 문제를 처음 풀었을 때, 이해 없이 결과만 받아들이고 문..
[Python] 1389번 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 22/12/05 플로이드-워셜이나 BFS응용으로 풀 수 있는 문제로, BFS응용풀이에 대한 아이디어는 14217번과 같은 아이디어를 공유하고 있다. 2022.11.29 - [백준 문제 풀이] - [Python] 14217번 그래프 탐색 [Python] 14217번 그래프 탐색 https://www.acmicpc.net/problem/14217 142..
[Python] 16928번 뱀과 사다리 게임 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 22/11/30 클래스에 못 푼 문제가 있길래 푼 문제이다. 전형적인 BFS문제이지만, 약간의 변형이 필요한 문제로, 그 상황만 잘 처리를 해준다면 쉽게 AC를 받을 수 있는 문제이다. 문제 접근 방식: 처음에 이 문제를 보고 뱀과 사다리를 타는 것이 의무적으로 타는 것이 아닌, 선택적으로 탈 수 있는 것인 줄 알고 의문의 WA를 많이 받았었다. 예를..
[Python] 14217번 그래프 탐색 https://www.acmicpc.net/problem/14217 14217번: 그래프 탐색 남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 잇는 도로들을 새로 만들거나, 안전상의 문제로 도로를 없애기도 할 계획이다. 도로 정비 계획은 두 도시와, 만들건지, 없앨건지에 www.acmicpc.net 22/11/18 BFS문제로, 문제에서 주어지는 그대로 구현한다면 시간초과를 받을 수도 있는 문제다. 이를 유의하며 살짝 아이디어를 가져와야되는 문제다. 문제 접근 방식: 먼저 쿼리의 개수가 최대 $500$개이고, 도시(노드)의 개수가 총 $500$개라는 사실을 주목해보자. 때문에 문제에서 주어진 그대로 임의의 도시($k$번 노드)에서 수도 도시($1$번 노드)로 가는 최단 시간을 구하기 위..
[Python] 17394번 핑거 스냅 https://www.acmicpc.net/problem/17394 17394번: 핑거 스냅 [어벤져스] 시리즈를 보지 않은 사람이라도 ‘인피니티 건틀렛’이 무엇인지는 다들 알 것이다. 그래도 모르는 사람들을 위해 설명을 하자면, 인피니티 스톤이 모두 모인 인피니티 건틀렛을 끼 www.acmicpc.net 22/11/18 BFS와 에라토스테네스의 체를 섞은 독특한 문제로, 두 알고리즘을 모두 알고 있다면 어렵지 않게 해결할 수 있는 문제이다. 특히, 이 문제는 1697번 숨바꼭질 문제와 같은 방식으로 방문처리를 하기 때문에 1697번을 해결했었다면 이 문제 또한 쉽게 해결할 수 있을 것이다. 문제 접근 방식: 먼저 목표 범위인 $A$와 $B$의 범위를 보면 $2 \leq A \leq B \leq 100,..
[Python] 23747번 와드 https://www.acmicpc.net/problem/23747 23747번: 와드 와드를 설치하지는 않았지만, 한별이의 최종 위치의 위, 아래, 왼쪽, 오른쪽 칸은 시야로 확보하고 있다. 지나온 경로를 모두 시야로 확보하지는 않는다. www.acmicpc.net 22/11/21 BFS문제에 시뮬레이션을 곁들인 문제로, 문제에서 주어지는 상황을 그대로 시뮬레이션하여 쉽게 해결할 수 있는 문제이다. 다만, 파이썬으로 해결하려고 한다면 시간초과에 유의해서 접근해야 풀 수 있는 문제이다. 문제 접근 방식: 먼저, 문제에서 주어진 정보대로 그래프의 크기, 그래프, 한별이의 현재 위치, 여행 기록을 모두 입력으로 받았다. 이후, 한별이의 여행기록을 for문으로 하나하나 돌리며 시뮬레이션을 해보는데, 와드를 놓..
[Python] 4179번 불! https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 22/11/24 2022.11.29 - [백준 문제 풀이] - [Python] 5427번 불 [Python] 5427번 불 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 lighter.tistory..

티스토리툴바