풀이 > distance 배열을 만들어서 노드의 레벨을 저장해두고, 다음 번 방문시 기존 레벨이 저장되어있으면 레벨 값을 바꾸지 않는다.
코드
import java.util.*;
/**
* 그래프에서 노드간 최소단거리 탐색 / 노드별 레벨 구하기
* 간선에 가중치 없음 (크루스칼 아님)
*
* 출발은 항상 1번
* 출발지 1번을 제외한 나머지 노드로 가는 최소값을 가진 배열 return
*
*/
public class graphSrch {
public void solution(int[] n, int[][] edges) {
boolean[] ck = new boolean[n.length];
List[] link = new List[n.length];
int[] distance = new int[n.length];
Stack<Integer> st = new Stack<Integer>();
Queue<Integer> q = new LinkedList<>();
int cur = 0;
int end = 0;
int cnt = 0; //레벨
//거리 초기화
for(int i =1; i<distance.length; i++){
distance[i] = n.length;
}
for (int i = 1; i < link.length; i++) {
link[i] = new ArrayList<Integer>();
}
//간선 연결 작업
for (int i = 0; i < edges.length; i++) {
link[edges[i][0]].add(edges[i][1]);
link[edges[i][1]].add(edges[i][0]);
}
//BFS 풀이
ck = new boolean[n.length];
cnt = 0;
//end = i;
//출발은 항상 1
q.add(n[1]);
while(!q.isEmpty()){
cur = q.peek();
q.poll();
if(cnt<distance[cur]){
distance[cur] = cnt;
}
//노드 방문하지 않은 경우
if(!ck[cur]){
//방문 체크
System.out.println("방문노드 : "+cur+" 현재 level :"+cnt);
ck[cur] = true;
//방문지점에서 갈 수 있는 다음 level add
for(int j=0; j<link[cur].size(); j++){
cnt = distance[cur];
if(!ck[(int)link[cur].get(j)]){
//다음 방문할 노드기 떄문에, 거리는 현재 거리+1, 다음 방문지가 현재 거리보다 큰 경우만 변경함
if((cnt+1)<distance[(int)link[cur].get(j)]){
distance[(int)link[cur].get(j)] = cnt+1;
}
System.out.println("next = "+link[cur].get(j));
q.add((int)link[cur].get(j));
}
}
cnt++; // 레벨 증가
}
}
System.out.println(end+"방문 최솟값 : "+cnt);
for(int i=1; i<distance.length; i++){
System.out.println(i +" = "+ distance[i]);
}
}
public static void main(String[] args) {
graphSrch tc = new graphSrch();
int[] n = {0,1,2,3,4,5,6};
// int[][] edges = {{1,3},{1,4},{2,1},{2,5},{3,4},{4,5},{4,6},{6,5},{6,2}};
int[][] edges = {{1,2},{1,4},{1,6},{2,4},{2,5},{4,5},{5,6},{5,2},{6,3}};
tc.solution(n,edges);
}
}
- 6줄 요약 - 크루스칼 알고리즘은 최소비용 신장트리를 만드는 알고리즘이다. 알고리즘은 다음과 같다.
1) 간선 가중치 중 가장 작은 값을 선택한다. 2) 간선을 연결하여 순환(Cycle)이 생기지 않는다면 연결 후 1)로 이동. 3) 연결 시 순환(Cycle)이 생기면 연결하지 않고 1)로 이동. (순환이 여부는 Union Find 알고리즘을 활용하여 알아냅니다!) 최소비용 신장트리의 간선의 수는 "노드의 수 - 1"
시작 합시다!
1. Kruskal 알고리즘이란?
Kruskal 알고리즘이란 모든 노드를 싸이클이 없도록 연결하는 트리를 만들기 위해 사용되는 알고리즘 입니다.
즉, 최소비용 신장트리를 찾는 알고리즘 이죠.
각 노드를 연결하는 간선에는 가중치가 있고, 해당 가중치 중 가장 적은 비용으로 모두 연결해야 할때 이 알고리즘을 사용합니다.
아래 예시를 보면서 이해를 해보져
그림 1. 크루스칼 알고리즘 예제
먼저 그림 1과 같이 5개의 노드가 있고, 연결 된 간선에는 가중치가 포함되어있을때,
크루스칼 알고리즘을 이용해서 가장 적은 비용으로 최소신장 트리를 만드는 방법을 알아보겠습니다.
크루스칼 알고리즘 적용 방식은 아래 3가지 입니다.
1) 간선 가중치 중 가장 작은 값을 선택한다. 2) 간선을 연결하여 순환(Cycle)이 생기지 않는다면 연결 후 1)로 이동. 3) 연결 시 순환(Cycle)이 생기면 연결하지 않고 1)로 이동. (순환이 여부는 Union Find 알고리즘을 활용하여 알아냅니다!)
간단하죠?
그림 1 예제를 통해 진행하겠습니다.
2. 예제를 통해 크루스칼 이론 학습하기
그림 1 그래프를 최소 비용으로 연결한다면 아래 그림 2와 같이 연결 될 것 입니다.
그림 2. 예상 결과 값
그럼 이렇게 연결이 되는지 확인해봅시다.
보기 편하도록 아래 그림 3과 같이 정리하고 시작할게요
그림 3. 최소비용 신장트리 만들기
최소비용 신장트리 만들기 시작!
2-1. 우선 첫번째로 가장 작은 가중치를 갖는 간선 '2<->5'를 선택 후 연결합니다.
그림 4. 최소비용 신장트리 만들기(1)
2-2. 이제 계속 반복 합니다. 다음 가장 작은 가중치 '4 <-> 5'를 선택하고 연결 합니다.
그림 5. 최소비용 신장트리 만들기(2)
2-3. 다음 작은 가중치 '1 <-> 3'을 선택하고 연결합니다.
그림 6. 최소비용 신장트리 만들기(3)
2-4 다음 작은 가중치 '2 <-> 4'를 선택합니다.
그런데! 2와 4를 연결하면 2 - 4 - 5 노드에 순환이 생기기 때문에 넘어가고 그 다음 작은 값 '1 <-> 2'를 선택 합니다.
그림 7. 최소비용 신장트리 만들기(4)
2-5 이제 어떤 간선을 선택해도 Cycle이 생성됩니다. 그렇기 때문에 최소비용 신장트리가 완성되었기에 종료!
그림 8. 최소비용 신장트리 만들기 (완성)
맨 처음 예상했던 결과값이랑 동일한 것을 확인할 수 있습니다.
그럼 바로 코드 구현으로 들어가 보져
3. 코드 구현하기
사실 크루스칼 알로리즘은
Union Find 알고리즘에 * 1. 간선의 최솟값을 찾기 => Arrays.sort (정렬 이용) * 2. 정렬된 배열 순서대로, 간선을 연결할 때 Cycle이 생기지 않으면 연결하도록 하기
를 추가하면 Kruskal 알고리즘이 됩니다. (아래 예제는 최소 비용 신장트리의 간선의 합을 구하는 코드 입니다.)
//부모 노드를 찾을 수 있는 함수
public int getParent(int parent[],int x) {
if(parent[x] == x) return x;
return parent[x] = getParent(parent,parent[x]);
}
//노드 연결해서 부모 값 작은걸로 변경하기
public int[] changeParent(int parent[], int a, int b) {
a = getParent(parent, a);
b = getParent(parent, b);
if(a<b) parent[b] = a;
else parent[a] = b;
return parent;
}
//부모 값이 동일한지 확인
public boolean findParent(int parent[], int a, int b) {
a = getParent(parent, a);
b = getParent(parent, b);
if (a==b) return true;
return false;
}
public int solution(int n, int[][] costs) {
int answer = 0;
int[] parent = new int[n]; //1,2,3,4,5,6
for(int i=0; i<n; i++) {parent[i] = i;}
//간선 정렬
Arrays.sort(costs, new Comparator<int[]>() {
@Override
public int compare(int[] arg0, int[] arg1) {
//오름차순 정렬
return arg0[2]-arg1[2];
}
});
//간선 오름차순으로 정렬되었기 때문에 Cycle이 아니라면 하나씩 더해주면 됨.
//0->1= 1 , 0->2 =2, 2->3 = 1 인경우 배열에 3의정보는 주지 않기때문에 costs.length 기준으로 하는것임
for(int i=0; i<costs.length; i++) {
//Cycle이 아닌경우 간선 가중치 더하기
if(!findParent(parent,costs[i][0],costs[i][1])) {
//연결하기
System.out.print(costs[i][2]+" ");
answer += costs[i][2];
changeParent(parent,costs[i][0],costs[i][1]);
}
}
System.out.println();
System.out.println(answer);
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
island_connection ic = new island_connection();
int n = 5;
int[][] costs = {{0,1,3},{0,2,4},{0,3,9},{1,3,3},{1,4,1},{2,3,5},{3,4,2}};
ic.solution(n, costs);
}
Union Find 알고리즘 개념을 이해해야 하기때문에 우선 Union Find 알고리즘을 우선 정리하겠습니다.
목차 - Union Find란? - Union Find 동작 방식 분석 - 코드 작성
1. Union Find란?
Union 이란 합집합이라는 뜻을 가지고 있습니다. 그래서 Union Find 알고리즘이란 합집합을 찾는 알고리즘 이라고 이해하면 될 것 같습니다.
주로 그래프 내에서 집합,순환을 찾기 위해 사용합니다.
1-1 .먼저, 집합을 찾는 경우 입니다.
7개의 노드의 연결을 보여주는 그림을 봅시다.
그림 1. Union Find 알고리즘
이 경우 위 사진과 같이 2가지 그룹으로 나누어지는데, 이렇게 2가지를 찾아낼때 Union Find 알고리즘을 사용합니다.
2-2. 그리고 두번째로 순환 구조를 찾을때 사용합니다.
그림 2. 그래프에서 순환 찾기
위 그림처럼 왼쪽 그래프처럼 연결되어 있는 상태에서 3번 노드와 5번 노드를 연결한다면, 그림 2의 오른쪽 그림처럼 3,4,5는 순환이 되게 됩니다. 그리고 Union Find로 이런 순환을 찾아낼 수 있죠.
크루스칼 알고리즘의 경우 최소 비용으로 그래프를 연결해야 하기 때문에, 순환이 되면 안되는 조건이 있습니다. 이때 Union Find 알고리즘을 이용하는 것이죠!
2. Union Find 동작 방식 분석
UnionFind 알고리즘을 간단하게 정리하면 "각각의 노드의 부모가 동일하면 합집합, 그렇지 않으면 다른 집합" 이라고 판단하는 것 입니다.
알고리즘 구성은 아래와 같습니다.
1. 노드를 탐색하여 연결되어 있으면 부모 노드를 얻어온다. 2. 부모의 노드가 다르다면 둘 중 큰 번호의 부모 노드를 작은 번호의 부모 노드로 변경
그렇기 때문에 노드들의 부모를 작성해 줄 배열이 하나 필요합니다. 예제는 아래 그림 3 처럼 노드의 수는 7개, 2개의 집합으로 구분 가능한 그래프를 가지고 진행하겠습니다.
그림 3. 예제 그래프
우선 아래 그림과 같이 노드가 7개니까 길이 7의 parent 배열을 생성하고, 각각의 부보는 자기를 가르키도록 초기화 합니다.
그림 4. parent 배열 생성 및 초기화
1부터 시작해서 7까지 탐색합니다.
2-1. 노드 1 탐색
1) 1의 노드는 2와 연결되어 있기 때문에 부모 노드를 얻어옵니다. 그리고 1과 2의 부모 노드는 다르기때문에 2의 부모 노드를 1로 변경 합니다.
2) 1의 노드는 4와 연결되어 있기 때문에 부모 노드를 얻어옵니다. 그리고 1과 4의 부모 노드는 다르기때문에 4의 부모 노드를 1로 변경 하며 1의 탐색은 종료합니다.
그림 5. 노드 1 탐색
2-2. 노드 2 탐색
다음 2 노드를 탐색합니다.
1) 2는 1과 연결되어있습니다. 2) 부모노드를 얻어옵니다. 3) 2개의 노드 모두 부모 노드가 1로 동일 하기때문에 넘어갑니다.
2-3. 노드 3 탐색
3 노드를 탐색합니다.
1) 3의 노드는 4와 연결되어 있습니다. 2) 부모노드를 얻어옵니다. 3) 3의 부모와 4의 부모는 다르기 때문에 작은 노드로 변경합니다. 4) 그런데 3의 부모는 3, 4의 부모는 1이기 때문에 3의 부모 노드를 1로 변경합니다.
그림 6. 노드 3 탐색
2-4. 노드 4 탐색
노드 4는 1, 3 노드와 연결되어 있습니다. 부모의 노드를 얻어오는데, 둘 다 부모의 노드가 동일함으로 넘어갑니다.
2-5. 노드 5 탐색
노드 5는 6과 연결되어 있습니다. 둘의 부모 노드가 다르기때문에 6의 부모 노드를 5로 변경합니다.
그림 7. 노드 5 탐색
2-6 노드 6 탐색
노드 6은 5와 연결되어있지만 부모 노드가 동일함으로 넘어갑니다. 그리고 노드 7과도 연결되어있습니다. 노드 6과 7의 부모는 다르기때문에 노드 7의 부모를 6의 부모 노드인 5로 변경합니다.
그림 8. 노드 6 탐색
2-7. 마지막 노드 7 탐색
노드 7은 6과 연결되어있지만, 둘의 부모노드가 동일하기 때문에 넘어갑니다.
이렇게 프로그램은 종료되고 부모 노드는 아래와 같이 정리 됩니다.
그림 9. 종류 후 parent 표 상태
이렇게 종료가 된후 부모노드가 1인 그룹과 부모노드가 5인 그룹 이렇게 2개로 구성되어 있음을 알 수 있습니다.
이것이 Union Find 알고리즘 동작 방법입니다.
3. 코드 작성
코드로 작성하면 아래와 같습니다.
//부모노드 찾기
public int getParent(int parent[],int search) {
if(parent[search] == search) return search;
else
return parent[search] = getParent(parent, parent[search]);
}
//합친 후 부모 노드 작은걸로 바꾸어주기
public int[] changeParent(int parent[], int a, int b) {
a = getParent(parent, a);
b = getParent(parent, b);
if(a<b) parent[b] = a;
else parent[a] = b;
return parent;
}
//부모 노드 찾기
public boolean findParent(int parent[], int a, int b) {
a = getParent(parent,a);
b = getParent(parent,b);
if(a==b) return true;
else return false;
}
public static void main(String[] args) {
UnionFind f = new UnionFind();
int n = 8;
int[][] graph = {{1,2},{1,4},{4,3},{5,6},{6,7}};
int[] parent = new int[n];
for(int i=1; i<n; i++) { parent[i] = i;}
//부모 노드 바꾸기
for(int i=0; i<graph.length; i++) {
f.changeParent(parent, graph[i][0], graph[i][1]);
}
//부모 노드 출력
for(int i=1; i<n; i++)
System.out.print(parent[i] +" ");
}
풀이 방법은 0,0 부터 탐색한다. 1. 0,0부터 시작해서 상하좌우로 움직이며 1인 곳만 탐색 2. 0을 만나면 끝내기 (DFS인데 Stack을 이용 안한 이유는 재귀함수를 이용할 경우 재귀함수 불릴때마다 메모리에 스택으로 쌓이고 처리하기 때문에 따로 Stack 만들진 않았다.)
3. 자바 코드
package java_BFS_DFS_basic;
import java.util.ArrayList;
/*
* DFS를 이용하여
* (NxN)인접행렬 넓이 구하기
* */
public class adjMatrics_DFS {
private static int[] X = {-1,0,1,0}; // X축의 상하좌우 이동을 위한 배열
private static int[] Y = {0,1,0,-1}; // Y축의 상하좌우 이동을 위한 배열 (x,y 짝만 맞추어주면 상하좌우든 하좌우상 이든 순서 상관x)
private static int[][] map;
private static int cnt=1;
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<Integer> arr = new ArrayList<Integer>(); //각 영역의 넓이를 저장할 ArrayList 생성
adjMatrics_DFS b = new adjMatrics_DFS();
int[][] map = {{1,1,1,0,1},
{1,1,0,0,1},
{1,0,1,1,0},
{0,0,1,1,1},
{0,0,1,1,1}};
boolean[][] check = new boolean[map.length][map[0].length]; //방문한 곳을 체크하기 위한 배열 행렬 생성
for(int i=0; i<map.length; i++) {
//System.out.println("다음 찾기 시작");
//(0,0) 부터 탐색 시작 후 1을 만나면 넓이 구하기 시작
for(int j=0; j<map[i].length; j++) {
if(map[i][j] == 1) {
b.dfs(i,j,check,map);
arr.add(cnt);
cnt = 1;
}
// 아닌경우 continue
else
continue;
}
}
// System.out.println("프로그램 종료");
System.out.println("arr : "+ arr);
}
public void dfs(int x, int y, boolean[][] ck,int[][] map) {
System.out.println(x+","+y);
ck[x][y] = true;
map[x][y] = 0;
for(int i=0; i<4; i++) {
int nextX = x + X[i];
int nextY = y + Y[i];
//상,하,좌,우 이동 중 범위가 넘어서는 경우 continue
if(nextX <0 || nextY<0 || nextX>=ck.length || nextY>=ck.length) {continue;}
//방문한곳은 continue
if(ck[nextX][nextY]){continue;}
//0은 벽이라서 이동할 경로가 벽이면 continue
if(map[nextX][nextY] == 0) {ck[nextX][nextY] = true; continue;}
dfs(nextX,nextY,ck,map);
cnt++;
}
//System.out.println("END");
//System.out.println();
}
}
출력 결과 : arr : [6, 2, 8]
DFS / BFS 이론은 알겠는데, 문제를 풀다보면 어떻게 구현하지? 라는 생각이 많이 든다. 그래서 다음글엔 DFS / BFS를 어떻게 구현할지 정리해 본다.
