본문 바로가기

그래프 이론

 (49)
[Python] 31217번 Y https://www.acmicpc.net/problem/31217 31217번: Y 첫 번째 줄에 정점의 개수 $n$과 간선의 개수 $m$이 공백으로 분리되어 주어집니다. ($1 \le n \le 10^5$, $0 \le m \le \min(\frac{n(n-1)}{2},2\times 10^5)$) 두 번째 줄부터 $m$개의 줄에 $i$번째 간선이 연결하는 정 www.acmicpc.net 24/01/09 간단한 차 수열+조합론 문제이다. 좋은 문제라고 생각된다. 문제 접근 방식: Y 그래프의 중심이 되는 루트를 각각의 정점마다 생각해보자. 즉, 우리는 $1, 2, \cdots, N$번 정점까지 있을 때, $i$번 정점이 Y 그래프의 루트가 되는 경우를 $1$번 정점부터 $N$번 정점까지 모두 더하여 최..
[Python] 14502번 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 24/01/06 BFS와 브루트포스 연습 문제로, 구현하는 중간에 조금 꼬여서 살짝 해멨던 문제이다. 문제 접근 방식: 문제 자체는 단순하다. 벽을 $3$개 세워야만 하고, 그렇게 벽을 세운 뒤에는 BFS를 돌리면 된다. 즉, $64\times 64\times 64 \approx 260,000$번 정도의 BFS를 수행하면 된다. BFS를 진행할 때에는 바이러스가 있는 부분을 큐에 넣고 BFS를 진행하면 된다...
[Python] 17370번 육각형 우리 속의 개미 https://www.acmicpc.net/problem/17370 17370번: 육각형 우리 속의 개미 무한히 많은 정육각형이 서로 맞닿아 놓인 형태의 개미 우리가 있다. 다음 그림과 같은 형태이고, 하얀색 변으로만 개미가 다닐 수 있다. 개미 우리의 모습 곤충 관찰이 취미인 유이는 세 정육각 www.acmicpc.net 23/09/25 육각형을 어떻게 적절하게 잘 변형시키는 가가 관건인 문제다. 문제 접근 방식: 문제를 처음 보고 규칙성이 있는 DP문제인 줄 알고 한참 동안 점화식을 찾아 해맸다. 이후 규칙성이 없음을 깨닫고 백트래킹으로 접근했다. 이 문제의 핵심은 육각형을 어떻게 적절하게 잘 변형 시킬 수 있는가 이다. 일반적인 2차원 격자로는 상하좌우로 움직이기 때문에 120도 만큼을 돌아가는 것..
[Python] 11967번 불켜기 https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 23/12/30 BFS 응용 문제로, 생각했던 풀이 방법보다 더 쉬운 방법이 있어서 글을 써본다. 초반 문제 접근 방식: 초반에 접근했던 문제 방식은 BFS를 한 번만 돌도록 하는 방식이었다. 문제를 보면, 특정 방에서 다른 방들의 스위치를 킬 수 있다고 했다. 그리고 스위치가 켜져 있는 방만 출입할 수 있다고 했고, 방에서 방으로 움직일 때에..
[Python] 15573번 채굴 https://www.acmicpc.net/problem/15573 15573번: 채굴 첫째 줄에 N, M, K가 주어진다. (1 ≤ N, M ≤ 1000, 1 ≤ K ≤ N × M) 둘째 줄부터 맨 위의 광물들부터 순서대로 N줄 동안 M개의 광물의 강도 Si, j가 주어진다.(i = 1, 2, ..., www.acmicpc.net 23/12/31 2023년 마지막 날에 해결한 문제로, BFS와 이분 탐색을 섞은 파라메트릭 문제이다. 파라메트릭 서치 연습으로 아주 적절한 문제인 듯 하다. 문제 접근 방식: 문제에서 요구하는 것은 최솟값을 요구하고 있고, 이 값은 특정 값 이상을 넘어가는 최솟값이므로 파라메트릭 서치를 통해 구현할 수 있다. 채굴기의 성능 $D$와 광산의 모습을 입력으로 받아서 BFS를 통..
[Python] 8286번 Road Network 2 https://www.acmicpc.net/problem/8286 8286번: Road Network 2 If no road network plan satisfying the conditions from the input exists, the first and only line of output should contain a single word BRAK - i.e., none in Polish. In the opposite case each of the lines in the output should contain a description of one bi www.acmicpc.net 23/09/23 차수열(Degree Sequence)의 개념을 익힐 수 있는 문제다. 여담으로 대회 개최를 준비하던 중..
[Python] 23352번 방탈출 https://www.acmicpc.net/problem/23352 23352번: 방탈출 첫줄에 지도의 세로 크기 $N$($1 \le N \le 50$), 가로 크기 $M$($1 \le M \le 50$)이 공백을 두고 주어진다. 둘째 줄부터 $N$줄에 걸쳐 각 방들의 정보 $A$($0 \le A \le 9$)가 공백을 두고 주어진다. www.acmicpc.net 23/09/08 BFS와 브루트포스를 합친 문제로, 처음에 비효율적인 접근 방식으로 접근해서 삽질한 문제다. 문제 접근 방식: 기본적인 접근 방식은 BFS이다. 처음에는 시작점과 끝점의 모든 조합마다 BFS를 돌리는 방식을 택했다. 시간초과가 나서 보니, 경로에는 같은 점을 포함할 수도 있다는 말에 코드를 고치고 파이파이로 제출했더니 또 시간초..
[Python] 24230번 트리 색칠하기 https://www.acmicpc.net/problem/24230 24230번: 트리 색칠하기 정점이 $N$개인 트리가 있다. 정점에는 1부터 $N$까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해 www.acmicpc.net 23/05/29 골드 5 짜리 문제 치고는 아이디어가 매우 좋았던 문제이다. 문제 접근 방식: 문제 정보를 보면, 트리가 주어져 있는데 각 노드별로 색깔 정보가 주어진다고 했다. 한 노드를 색칠하면, 그 노드를 포함한 서브트리는 모두 같은 색으로 색칠된다고 한다. 이때, 모든 정점을 원하는 색으로 칠하고자 할 때 구하는 최소 색칠 횟수를 구하는 것이 우리의 목적이다. 맨 처음 떠올렸던 방..

티스토리툴바