반응형 백준34 [ 알고리즘 ] 코딩 - 백준 1647 - 도시분할계획.java 문제 링크 www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net * 백준 - (자바)도시분할계획 - MST(최소 스패닝 트리) * 한 마을을 2개의 구역으로 나눈다. N개의 집과 M개의 길이 있다. 길은 양방향. 각 분리된 마을은 마을 * 안에서 집들이 서로 연결이 되어있어야 한다. 필요없는 길을 모두 없애고 남은 최소의 길의 유지비를 구하자. * 정점10만개. 길 100만개.. * 문제만 보고 마을을 나누고~.. 2021. 1. 8. [ 알고리즘 ] 코딩 - 백준 - 15683 - 감시.java www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net * 사용한 로직! * 1. 순열로 CCTV별 감시 방향을 정해준다 * 1-1. 감시 방향을 정할 때 CCTV마다 규칙이 있으니 주의해서 설정! * 2. 정해진 방향을 기준으로 감시 영역을 표시한다. * 3. 남은 사각지대의 영역을 카운트 해준다. * 처음에는 CCTV Type마다 따로 저장하기 위해 ArrayList 배열을 사용했다. private static void selectCCTVdir(int.. 2020. 12. 15. [ 알고리즘 ] 코딩 - 백준 17472 - 다리만들기 2 .java 백준 17472 - 다리만들기 2 * 자바로 구현. * 지도 NxM * 섬은 상하좌우로 붙어있는 덩어리. * 다리를 연결해서 모든 섬을 연결하고자 한다. * 다리는 직선만 가능. 바다에만 설치가능. 다리길이는 2이상. * 1. 섬에 번호붙이기 (BFS, DFS) - BFS 이용 * 2. 모든 지도의 좌표를 돌며 각 섬마다 설치가능한 다리 놓기( 완전탐색 ) * 3. MST로 최소 다리 비용 찾기. (크루스칼, 프림) - 크루스칼 이용 ** 테스트케이스는 모두 맞는데 1%에서 틀렸습니다!!!! 해서 당황했다... ** 모든 섬이 연결이 되어있는지 확인을 안해서 틀렸다.. public class BOJ_17472_Make_Bridge2 { // 섬과 이어진 정보를 담는 클래스 static cla.. 2020. 9. 7. [ 알고리즘 ] 코딩 백준 16236 - 아기상어.java 백준 16236 - 아기상어 * 자바로 구현 * NxN크기 물고기 M마리 상어 1마리. * 한칸에는 물고기 1마리 * 아기상어 초기크기 2. 상하좌우로 한칸씩 이동 * 상어보다 큰 물고기의 칸은 지나갈 수 없음. * 같은 크기의 물고기는 먹지는 못하지만 지나갈 수는 있음. * 더 이상 먹을 수 있는 물고기가 공간에 없으면 엄마 상어 호출. ( 탈출조건 ) * 먹을 수 있는 물고기가 1마리. 그 물고기 먹으러 이동 * 1마리 이상이면 가장 가까운 물고기를 먹으러 간다. * - 거리 : 물고기가 있는 칸 까지 지나야하는 칸의 개수 * - 가까운 물고기가 많다면 가장 위에 물고기. 그런 물고기가 많으면 * - 가장 왼쪽부터 먹는다. * 상어 크기가 2인경우 물고기를 2마리 먹으면 3으로 커진다. * 3인경우에.. 2020. 9. 7. [ 알고리즘 ] 코딩 백준 17471 - 게리맨더링.java 백준 17471 - 게리맨더링 * 자바로 구현 * 한 도시가 N개의 구역으로 나뉘어있음. * 1~N번 구역을 두개의 선거구로 나누어야한다. * 이때 선거구에 포함된 구역은 모두 연결이 되어있어야한다. * 두 선거구에 포함된 인구 차이가 최소인 경우를 찾아 출력. * 선택한 구역과 선택하지않은 구역이 연결되어 있는지 확인하는 과정이 필요. * 여기서는 BFS를 두 번해서 풀이. public class BOJ_17471_Gerry_Mandering { // N : 구역수, area_population : 각 구역 인구수, resMin : 최소값. private static int N, area_population[], resMin; private static boolean selected_area[]; //.. 2020. 9. 7. 이전 1 2 3 4 5 6 7 다음 반응형
