본문 바로가기

그래프 탐색

 (41)
[Python] 32229번 B끼B끼 A끼A끼 수열 찾기 https://www.acmicpc.net/problem/32229 24/09/14  맷코컵 때 검수했던 문제 중 하나이다. 지문을 해석하는 재미가 있는 문제다. 그것과는 별개로, 제목이 별로다. 문제 접근 방식:  일단, 문제 해석을 하면 이 문제의 80%는 해결한 것과 다름이 없다.  먼저, 집합 $S$의 정의를 유의 깊게 보자. 문제에서 주어지는 입력은 $A, B, N$이다. $S$는 순서쌍 $(x, y)$들의 모임인데, 작은 것이 $x$이고 큰 것이 $y$이다.($x  또한, 이 둘의 차이는 $A$또는 $B$이며, $x$는 최소 $1$, $y$는 최대 $N$의 값을 가질 수 있다.  이제 수열 $P$의 정의를 유의 깊게 보자. 수열 $P$에는 $1$부터 $N$까지의 모든 수가 최소 하나씩 있고 $..
[Python] 15681번 트리와 쿼리 https://www.acmicpc.net/problem/15681 24/03/29  트리 DP를 연습할 수 있는 아주 좋은 문제다. 이전에 해결했던 문제를 복습하는 겸, 글로 작성해본다.  문제 접근 방식:  나이브하게 각 쿼리마다 위의 값을 일일히 구해서 내보내려고 한다면, 최악의 경우 $\mathcal{O}(QN)$이 소요된다. 각 쿼리마다 DFS를 한 번 진행할 것이고, 트리에서의 DFS는 $\mathcal{O}(N)$의 시간 복잡도가 소요되기 때문이다. 따라서, 한 번의 DFS를 진행하여, 그 결과를 저장해야한다. 즉, DP를 진행하는데, DFS를 진행하며 DP를 진행하면 된다. 탑다운 DP의 구현 방식과 비슷한데, 트리 DP는 서브 트리 별로 문제를 분할하는 것이 핵심이다. DP 점화식을 다음..
[Python] 11668번 파이프 청소 https://www.acmicpc.net/problem/11668 24/05/12  기하학 + 그래프 이론 관련 문제이다. 좋은 문제인 것 같아서 풀이를 남겨보려고 한다. 문제 접근 방식:  문제에서 요구하고 있는 바를 정리해보자. 1. 파이프는 수원지와 도시를 잇는다.2. 두 파이프는 서로 교차할 수 있으며, 한 교차점에는 세 파이프가 동시에 교차하지 않는다.3. 교차점에는 이물질이 끼는데, 한 파이프에 로봇을 넣으면 그 파이프의 교차점을 모두 청소해 줌.4. 로봇이 충돌하는 일을 방지하기 위해 교차점에는 오직 하나의 파이프에만 로봇이 있어야 함.5. 어떤 파이프의 부분 집합을 잡아서 동시에 로봇을 투입했을 때, 두 로봇이 충돌하는 일이 없으면서 모든 교차점을 청소할 수 있는지를 판단해야 함.6. 두..
[Python] 19240번 장난감 동맹군 https://www.acmicpc.net/problem/19240 19240번: 장난감 동맹군 당신은 N개의 동물 장난감을 이용하여 모의 전쟁 놀이를 하려고 한다. 장난감은 편의상 1부터 N까지 번호가 붙어있고, 당신은 이를 두 개의 동맹군으로 나누고 싶다. 다만 특정 장난감끼리 사 www.acmicpc.net 24/03/16 이분 그래프임을 알아낸다면 쉽게 해결할 수 있는 문제이다. 문제 접근 방식: 장난감을 그래프의 노드, 동맹이 될 수 없는 장난감의 쌍을 두 노드를 이은 간선이라고 간주한다면, 동맹이 될 수 없는 장난감 쌍 끼리는 서로 다른 동맹군이어야 한다는 조건은 이분 그래프의 조건을 만족한다. 따라서 주어진 그래프가 이분 그래프의 조건을 만족함을 알아내기만 하면 충분하다. 이는 DFS로 구현..
[Python] 4803번 트리 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 24/03/24 여러 방법으로 풀 수 있는 좋은 문제다. 나의 경우는 BFS로 먼저 접근했고, 이후 유니온 파인드로 다시 풀었다. 첫 번째 문제 접근 방식: BFS로 접근했다. 그러면 사이클을 어떻게 판단해야 할 지가 문제인데, 사이클 판단을 굳이 할 이유가 없었다. 왜냐하면 결국 우리는 트리의 개수를 세야 하고, 트리는 간선의 개수가 $N-1$개이면 노드의 개수가 $N$개임을 ..
[Python] 12887번 경로 게임 https://www.acmicpc.net/problem/12887 12887번: 경로 게임 첫째 줄에 바꿀 수 있는 하얀색 칸의 개수의 최댓값을 출력한다. www.acmicpc.net 24/03/20 BFS응용 혹은 그리디로 풀 수 있는 간단한 문제이다. 문제 접근 방식: 접근 방식은 굉장히 간단하다. 왼쪽-오른쪽 경로 중 최단 거리의 경로를 찾고, 그 경로를 제외하고 다 색칠하면 최대한 많은 하얀색 칸을 칠할 수 있을 것이라는 아이디어이다. 따라서, 현재 흰색 칸이 몇 개 있는지 구하고, BFS를 통해 최단 거리를 구한 뒤, 흰색 칸에서 최단 거리만큼을 빼주었다. 최단 거리 상의 경로는 항상 흰색 칸 일 것이며, 이를 제외한 흰색 칸을 모두 칠해야 하기 때문이다. 이를 그대로 구현하면 된다. 혹은, ..
[Python] 2206번 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 24/03/19 BFS 응용 문제로, 클래스에 있는 아주 교육적인 문제다. 한번 더 생각해야 되는 좋은 문제다. 문제 접근 방식: 기본적으로 최단 거리를 구해야 되는 문제이기 때문에 BFS를 사용해야겠다는 감은 올 것이다. 그러면 어떻게 BFS를 구현할 것이냐가 문제인데, 벽을 최대 한 칸까지 뚫을 수 있다는 점이 핵심이다. 따라서 벽을 뚫는 행위를 어떻게 구현할 것인가가..
[Python] 1325번 효율적인 해킹 https://www.acmicpc.net/problem/1325 max_hacked: ans = [] ans.append(start) max_hacked = hacked elif hacked == max_hacked: ans.append(start) print(*ans) main()

티스토리툴바