연결성분 그래프에서 최대로 연결된 부분 그래프 어떻게 구할까 방법은 간단하다. 정점을 차례대로 DFS/BFS 를 실행한다. -> 이때 방문되면 서로 연결되어 있음 해당 visited 배열에 boolean 값 대신, 각각의 부분그래프를 나타낼 요소를 넣는다. visted 배열을 돌려가며 가장 빈도수가 높은 숫자의 요소들을 출력한다. * 아래 연결성분 찾는 메서드는 그래프의 간선이 1-2-3 4-5 이렇게 순차적으로 되어있다고 가정한것. - dfs 메서드를 포함한 graph 클래스 (인접리스트로 구현) class Graph{ private static int vn; //정점개수 private static int[] visited; //방문여부 private static ArrayList graph = new..
BOJ 2667 단지번호붙이기
2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 이 문제는 한칸의 위, 아래, 좌 , 우 에 1 표시가 되어있다면 (집이 있다면) 집이 연결되었다고 표현하고, 이렇게 연결된 집들을 '단지'라고 일컫는다. 따라서 과 같이 생긴 그래프가 있을때 와 같이 단지가 형성 되는 것이다. ..
단순히 DFS와 BFS를 구현하는 문제이다. 근데 이 문제의 핵심은 " 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고," 이다. 이를 간단히 하기 위해서는 인접행렬로 그래프를 구현하면 된다 . 인접행렬로 그래프를 구현하고, 간선을 탐색할 경우 당연히 인덱스 차례대로 방문하기 때문에 "정점번호가 작은 것을 먼저 방문하고"가 자연스럽게 충족된다. 반면에 인접리스트로 구현할 경우, 간선 노드들이 정렬이 되어있지 않으므로 정렬을 해주어야 한다. 나는 인접 리스트 버전과 인접 행렬버전 모두를 구현했다. 먼저 인접행렬버전을 보자. 인접행렬은 당연히 (n+1)*(n+1) 의 크기로 구현을 해주고, BFS를 위해 큐도 구현해주어야 한다. 또한 visited 배열 (방문을 표시하는 배열..
BOJ 12865 평범한 배낭
이 문제는 완전 전형적인 Knapsack 문제이다! 배낭의 무게가 w로 한정적일때, 가치가 모두 다른 보석들을 얼마만큼 넣어야 최적해인지 찾아야한다. 그렇다면 아래 그림을 통해 knapsack 문제를 더 살펴보자! 1) 현재 보석의 무게 > 배낭의 무게 이 경우는 해당 보석을 넣을 수 없으므로, 이전에 구해놓은 최적해 (이전 보석-현 배낭무게의 최적해)를 똑같이 복사한다. 2) 현재 보석의 무게 w) max(vali+p[i-1][w-wi] , p[i-1][w] else i는 현재 보석, w는 현재 배낭의 무게 wi는 현재 보석의 무게, vali 는 현재 보석의 가치이다. 구현에서 더 추가되는 부분은, p 라는 2차원 배열이다. 2차원 배열을 선언하는 이유는 "해당 무게의 최적해" 들을 보석의 개수 별로 ..