Algorithm/BOJ172 [BOJ]9370번: 미확인 도착지 www.acmicpc.net/problem/9370 문제를 잘 읽어보셔야 합니다. 출발지 -> 후보지로 가는 최단 경로 중에 주어진 경로 g,h가 포함된 후보지를 고르는 문제입니다. 저는 문제 잘못 읽어서 가장 짧은 후보지 고르는 줄 알고 헤맸습니다. 출발지 s, 후보지 c, 주어진 경로 g,h라고 한다면 1. 출발지에서 다익스트라를 돌립니다. 2. 주어진 경로 g, h에서 다익스트라를 돌립니다. 그리고 두 조건 중 하나를 만족하면 정답입니다. 1. 출발지 → 후보지 거리 == 출발지 → g 거리 + g 거리 → h 거리 + h 거리 →후보지 거리 2. 출발지 → 후보지 거리 == 출발지 → h 거리 + h 거리 → g 거리 + g 거리 →후보지 거리 정답 후보는 최단 경로에 g,h 경로가 포함되어 있음.. 2021. 2. 8. [BOJ]2146번: 다리 만들기(py) www.acmicpc.net/problem/2146 BFS 문제입니다. N제한이 100이므로 BFS로 전체 그래프를 한 번 탐색하는데 O(100*100)이 걸립니다. 그러므로 BFS를 딱 한 번만 돌아서 모든 섬간의 최소 거리를 구해줘야합니다. (시간초과 X) 1. 섬을 컴포넌트 별로 나눕니다. 2. 컴포넌트 별로 나눈 모든 섬들의 좌표를 큐에 넣습니다. 3. 섬 = '방문한 칸', 바다 = '방문하지 않은 칸'이라는 의미로 BFS를 돕니다. 4. 서로 다른 컴포넌트인 두 섬이 BFS로 영역을 확장하다 만나면 그 둘이 지나온 거리를 더하면 정답입니다. 무슨 말인지 이해가 잘 안가신다면 아래 코드를 참고하시면 됩니다. 코드: github.com/cotchan/algorithm/blob/main/python.. 2021. 2. 5. [BOJ]17142번: 연구소3(py) www.acmicpc.net/problem/17142 시뮬레이션 문제입니다. n개의 바이러스 위치 중에 m개를 뽑아서 최소를 찾는 문제이므로 조합(combination)을 통해 해결할 수 있습니다. 한 가지 주의 사항은 바이러스의 종류와 무관하게 빈 칸(0)만 채우면 됩니다. 그러므로 탐색을 종료 조건은 BFS로 채운 빈 칸의 숫자가 주어진 입력의 0칸 갯수와 동일하면 됩니다. 코드: github.com/cotchan/algorithm/blob/main/python/BOJ/BOJ17142.py 2021. 2. 3. [BOJ]1956번: 운동 www.acmicpc.net/problem/1956 플로이드 알고리즘을 통해 해결할 수 있습니다. 코드: github.com/cottory/algorithm/blob/master/JAVA/BOJ1956.java 2020. 11. 10. 이전 1 ··· 13 14 15 16 17 18 19 ··· 43 다음
