본문 바로가기

그래프 탐색

 (41)
[Python] 25512번 트리를 간단하게 색칠하는 최소 비용 https://www.acmicpc.net/problem/25512 25512번: 트리를 간단하게 색칠하는 최소 비용 0번 정점을 black, 1번 정점을 white, 2번 정점을 white, 3번 정점을 black, 4번 정점을 black, 5번 정점을 black, 6번 정점을 black, 7번 정점을 white로 색칠하는 비용 310이 정답이다. www.acmicpc.net 24/02/08 간단한 그래프 탐색 문제로, 트리의 성질을 이용한 교육적인 좋은 문제다. 문제 접근 방식: 트리를 색칠할 수 있는 최소 비용을 문제에서는 요구하고 있고, 인접한 노드마다 항상 다른 색깔로 칠해야 한다는 제약 조건이 걸려있다. 요지는, 트리는 이분 그래프라는 점이다. 트리는 이분 그래프이기 때문에, 루트를 중심으로 ..
[Python] 14395번 4연산 https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 24/01/12 단순한 BFS문제다. 문제 접근 방식: BFS문제다. 다만 $10^9$짜리 배열을 만들어서 방문 처리를 하기가 곤란했기 때문에, 방문 처리는 딕셔너리로 해결했다. 키-값 쌍이 존재하는 경우에는 방문 처리가 되어있다고 간주하고, 키는 정수, 값은 그때의 방법을 담은 문자열로 구현했다. 숫자 범위가 큶에도 BFS가 잘 작동하고 바꿀 수 없는 경우를 빠르게 판단할 수 있는 이유를..
[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] 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 짜리 문제 치고는 아이디어가 매우 좋았던 문제이다. 문제 접근 방식: 문제 정보를 보면, 트리가 주어져 있는데 각 노드별로 색깔 정보가 주어진다고 했다. 한 노드를 색칠하면, 그 노드를 포함한 서브트리는 모두 같은 색으로 색칠된다고 한다. 이때, 모든 정점을 원하는 색으로 칠하고자 할 때 구하는 최소 색칠 횟수를 구하는 것이 우리의 목적이다. 맨 처음 떠올렸던 방..

티스토리툴바