Atom 에디터


github에서 만든 오픈소스 에디터




git-plus 패키지


git 명령어를 손쉽게 칠 수 있는 에디터 플러그인



git-plus 장점


git bash를 열고 매번 해당 프로젝트 폴더로 이동하여 명령어를 입력해야했지만,

git plus를 이용하면 ctrl + shift + h 단축키로 쉽게 git 명령어창을 띄우고,

자동완성 기능으로 원하는 명령어를 손쉽게 입력가능!


이전에 ecilpse에서 제공하는 git 플러그인을 이용하다가 git bash로 갈아 탔을 때도 신세계였지만,

atom 에디터에서 이용하는 git-plus는 단연 최고!



실제 사용 예시


1. git-plus 설치






2. ctrl + shift + h로 git console창 열기



*한번에 add, commit, push까지 가능



삽입정렬이란?


Key값과 정렬된 리스트가 주어졌을 때,

Key값을 정렬된 리스트의 알맞은 위치에 삽입하여 하나의 정렬된 리스트를 만드는 것



동작 원리


다음과 같이 숫자 4개가 주어지고 이를 삽입정렬을 이용해 정렬한다면



 5

 4

3 

 2


1. key값을 두번째 숫자 4로 지정


5

 4

3

 2



2. 키값과 그 앞에 있는 값을 비교 후 키값이 작으면 자리를 바꾼다.


4

 5

3

 2



3. 더 이상 비교할 값이 없으므로 정렬 1회전이 끝난 것



4. 세번째 값을 key값으로 지정


4

 5

3

 2



5. 앞의 값과 비교 및 위치 이동


4

 3

5

 2


3

 4

5 

 2



6. 이를 반복하면 모든 값이 정렬된다.


2

 3

4 

 5



예제코드)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.Scanner;
 
public class InsertionSort {
    
    /*
     * 삽입정렬
     * Key값과 정렬된 배열이 주어졌을 때,
     * Key값을 정렬된 배열의 알맞는 자리에 삽입하여 정렬하는 방법
     */
    
    public static void main(String[] args) {
        //값을 입력받고 출력하는 부
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] array = new int[n];
        for(int i=0;i<n;i++) {
            array[i] = scan.nextInt();
        }
        
        InsertSort(array);
        
        for(int i:array) System.out.print(i);
        
        scan.close();
    }
    
    public static void InsertSort(int[] array) {
        for(int i=1;i<array.length;i++) { //주어진 값들 중에서 2번째 값부터 Key값으로 선정
            int key = array[i];           //i번째 수를 Key값으로 설정
            int j = i-1;                   //Key값을 기준으로 왼쪽에 있는 수부터 비교
            while(j>=0 && array[j]>key) { //맨앞까지 비교했거나 key값이 왼쪽수보다 작으면 순회를 멈춤
                array[j+1] = array[j];    //비교한 값을 오른쪽으로 한칸 이동
                --j; 
            }
            array[j+1] = key;               //알맞는 key값의 위치에 저장
        }
    }
}
 
cs



시간 복잡도 분석


최선의 경우는 모든 수가 이미 정렬된 상태로 수가 들어올 때이다.

이때는 수의 개수인 n의 복잡도를 가진다.


하지만 최악의 경우인 반대 순서로 정렬되어 들어온 경우에는

Key값을 옮기고 그 안에서 전부다 값들을 비교해야 하기에 n제곱을 수행 복잡도를 가진다.



Refletion이란?


투영, 반사라는 사전적 의미

객체를 통해 클래스의 정보를 분석하는 기법을 말한다.


자바에서 동적으로 인스턴스를 생성하기 위해 java.lang.reflet api를 통해 제공하고 있다.

이를 이용하면 동적으로 클래스를 생성할 수 있을 뿐만 아니라, 클래스의 메소드를 실행할 수 있다.


예제코드)


다음과 같은 클래스가 있다고 가정


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class TargetClass {
    
    /*
    * reflection 되어질 객체
    */
 
    public void firstMethod() {
        System.out.println("첫번째 매소드");
    }
    
    public void secondMethod(String name) {
        System.out.println("두번째 메소드");
    }
    
    public void thirdMethod(int n) {
        for(int i=0;i<n;i++) {
            System.out.println("세번째 메소드");
        }
    }
}
cs



클래스의 이름을 입력하여 클래스를 찾고 클래스의 선언된 메소드들 찾기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.lang.reflect.Method;
 
public class ReflectionExample {
    public static void main(String[] args) {
        
        /*
         * 클래스의 선언된 메서드를 찾는 방법
         */
        
        try {
            Class targetClass = Class.forName("co.kr.javastudy.reflection.TargetClass");
//java.lang.Class의 forName()메소드를 통해 클래스를 찾음
            
Method methods[] = targetClass.getDeclaredMethods();
            //getDeclaredMethods()를 통해 해당 클래스의 메소드들을 찾음
for(int i=0;i<methods.length;i++) {
                System.out.println(methods[i].toString());
            }
        } catch (ClassNotFoundException e) {
            System.out.println("클래스를 찾을 수 없습니다.");
        }
    }
}

cs



클래스의 선언된 메소드들의 이름 출력


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.lang.reflect.Method;
 
public class ReflectionExample2 {
    public static void main(String[] args) {
        
        /*
         * 클래스의 선언된 메서드이름을 출력
         */
        
        try {
            Class targetClass = Class.forName("co.kr.javastudy.reflection.TargetClass"); 
            Method methods[] = targetClass.getDeclaredMethods(); 
          
            for(int i=0;i<methods.length;i++) {
                String findMethod = methods[i].getName(); //method의 이름 추출
                System.out.println(findMethod);
            }
        } catch (ClassNotFoundException e) {
            System.out.println("클래스를 찾을 수 없습니다.");
        }
    }
}
cs



찾은 메소드를 동적으로 호출


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
 
public class ReflectionExample3 {
    public static void main(String[] args) {
        
        /*
         * 이름을 지정해 특정 메소드를 실행시키는 방법
         */
        
        try {
            TargetClass target = new TargetClass(); //해당 클래스의 인스턴스 생성
            Class targetClass = Class.forName("co.kr.javastudy.reflection.TargetClass");
            Method methods[] = targetClass.getDeclaredMethods();
            
            for(int i=0;i<methods.length;i++) {
                String findMethod = methods[i].getName();
                if(findMethod.equals("secondMethod")) {
                    //secondMethod를 찾아서 실행
                    try {
                        methods[i].invoke(target,"리플렉션");
                        //invoke()를 통해 메소드 호출 가능
                        //첫번째 파라미터는 해당 메소드를 가진 인스턴스, 두번쨰 파라미터는 해당 메소드의 파라미터
                    } catch (IllegalAccessException | IllegalArgumentException | InvocationTargetException e) {
                        e.printStackTrace();
                    }
                }
            }
        } catch (ClassNotFoundException e) {
            System.out.println("클래스를 찾을 수 없습니다.");
        }
    }
}
cs



** 리플렉션을 통해 파라미터, 부모 클래스, 패키지, Modifier, Fields, Annotaion 등 다양한 정보를 알아낼 수 있다.

자세한 것은 java api문서를 참고하면 좋을 것 같다.

'Java' 카테고리의 다른 글

오버로딩 vs 오버라이딩  (0) 2017.05.16
JAVA 특징와 OOP  (0) 2017.05.12
[Collection] 동기화된 컬렉션  (0) 2017.03.10
[람다식]메소드와 생성자 참조  (0) 2017.03.08
[람다식] 클래스 멤버와 로컬변수의 사용  (0) 2017.02.24

깊이 우선 탐색


그래프 G와 시작점 S가 주어졌을 때 S에서 도달 가능한 모든 간선을 찾는 과정


동작원리


탐색 시작 위치의 vertex의 인접한 간선을 통해 다른 vertex로 이동한 후 인접한 간선이 없을 때까지

반복하여 내려간 후 다시 위로 올라가는 과정을 반복해서 탐색하는 것


아래로 깊이 내려가며 탐색하기에 깊이 우선 탐색이라고 불림



코드)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class DfsExample {
    
    /*
     * 인접행렬로 구현된 그래프의 깊이 우선 탐색
     */
    
    static int nV; //총 vertex 수
    static int nE; //총 edge 수
    static int[][] adMatrix; //인접행렬
    static boolean[] visit; //방문여부 체크
    
 
    //재귀호출을 이용한 dfs구현
    
    public static void dfs(int i) {
        visit[i] = true;
        for(int j=0;j<nV;j++) {
            if(adMatrix[j][i]==1 && !visit[j]) {
                System.out.println(i + "에서 " + j + "로 이동");
                dfs(j);
            }
        }    
    }
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        nV = scan.nextInt();
        nE = scan.nextInt();
        
        adMatrix = new int[nV][nV];
        visit = new boolean[nV];
        
        for(int i=0;i<nE;i++) {
            int vertex1, vertex2;
            vertex1 = scan.nextInt();
            vertex2 = scan.nextInt();
            adMatrix[vertex2][vertex1] = 1;
        }
        
    
        for(int i=0;i<nV;i++) {
            System.out.print(i + "-" );
            for(int j=0;j<nV;j++) {
                System.out.print(adMatrix[j][i]+ " ");
            }
            System.out.println();
        }
 
        
        dfs(0);
    }
}
cs


'자료구조' 카테고리의 다른 글

[Map] HashTable과 HashMap의 차이와 Properties  (0) 2017.03.10
[Map] HashMap  (0) 2017.03.10
[Set]HashSet의 특징  (1) 2017.03.09
[그래프]넓이 우선 탐색(BFS)  (0) 2017.03.07
[그래프] 인접리스트와 인접행렬을 이용한 구현  (0) 2017.02.26

동기화된 컬렉션


컬렉션 프레임워크의 대부분의 클래스들은 싱글 스레드 환경에서 사용할 수 있도록 설계되어있음

그렇기에 여러 스레드가 동시에 컬렉션에 접근한다면 의도하지 않게 데이터가 변경될 수 있는

불안정한 상태가 된다.



synchronizeList(List<T> list) - list를 동기화된 list로 리턴

synchronizeMap(Map<K, V> map) - map을 동기화된 map으로 리턴

synchronizeSet(Set<T> set) - set을 동기화된 set으로 리턴


ArrayList, HashSet, HashMap이 대표적으로 싱글스레드 기반으로 설계된 컬렉션 클래스인데,

이를 멀티 스레드 환경에서 쓸 수 있도록 컬렉션 프레임워크는 비동기화된 메소드를 동기화된

메소드로 래핑하는 synchronizeXXX( ) 메소를 제공한다.



예제코드


1
2
// 리스트를 동기화된 리스트로 변환
List<T> list = Collections.synchronizedList(new ArrayList<T>());
cs


1
2
// map를 동기화된 map으로 변환
Map<K,V> map = Collections.synchronizedMap(new HashMap<K,V>());
cs


1
2
// set를 동기화된 set으로 변환
Set<T> set = Collections.synchronizedSet(new HashSet<T>());
cs


'Java' 카테고리의 다른 글

JAVA 특징와 OOP  (0) 2017.05.12
[Reflect]Refletion의 정의와 동적 메소드 호출  (0) 2017.03.17
[람다식]메소드와 생성자 참조  (0) 2017.03.08
[람다식] 클래스 멤버와 로컬변수의 사용  (0) 2017.02.24
[람다식] 타켓타입과 함수적 인터페이스  (0) 2017.02.24

HashTable이란?


HashMap과 동일한 내부구조를 가지고 있는 Map 구현 클래스



HashMap vs HashTable


 

HashMap 

HashTable 

 동일한 키 기준

 hashCode( )와 equals( ) 

 hashCode( )와 equals( ) 

 동기화된 메소드

 없음

 동기화된 메소드로 구성


HashMap과 HashTable은 동일한 내부 구조를 가지고 있지만

HashTable의 경우는 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가

동시에 이 메소드를 실행할 수 없고, 하나의 스레드가 실행을 완료해야만 다른 스레드가 실행가능하다.

이는 멀티 스레드 환경에서 안전하게 객체를 추가, 삭제할 수 있다는 것을 의미한다.



Properties란?


Hashtable의 하위 클래스로 Hashtable의 모든 특징을 가지고 있다.

차이점은 Properties는 키와 값을 String으로 제한하였다는 것이다.


주로 애플리케이션의 옵션 정보, 데이터베이스 연결정보 그리고 국제화 정보가 저장된

프로퍼티(~.properties) 파일을 읽을 때 주로 사용




'자료구조' 카테고리의 다른 글

[그래프] 깊이 우선 탐색(DFS)  (0) 2017.03.10
[Map] HashMap  (0) 2017.03.10
[Set]HashSet의 특징  (1) 2017.03.09
[그래프]넓이 우선 탐색(BFS)  (0) 2017.03.07
[그래프] 인접리스트와 인접행렬을 이용한 구현  (0) 2017.02.26

HashMap이란?


Map 인터페이스를 구현한 대표적인 Map 컬렉션



Map이란?


Key와 value으로 구성된 Entry 객체를 저장하는 구조를 가짐(key, value 모두 객체)

키는 중복 저장될 수 없지만 값은 중복 저장 가능

HashMap, HashTable, LinkedHashMap, Properties, TreeMap 등이 있다.



HashMap 특징


HashSet과 마찬가지로 hashcode()와 equals()로 동일한 키 여부를 결정한다.





기본 사용법 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
package map.hashmap;
 
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
 
public class HashMapExample1 {
    public static void main(String[] args) {
        
        //Map 생성
        Map<String, Integer> map = new HashMap();
        
        
        //객체 저장
        map.put("원빈", 50);
        map.put("장동건", 70);
        map.put("하하", 40);
        
        System.out.println("총 Entity 수 : " + map.size());
        
        //객체 찾기
        System.out.println("하하 : " + map.get("하하"));
        System.out.println();
        
        //하나씩 처리 - ketset()이용
        Set<String> keySet = map.keySet();
        Iterator<String> keyIterator = keySet.iterator();
        while(keyIterator.hasNext()) {
            String key = keyIterator.next();
            Integer value = map.get(key);
            System.out.println(key + " : " + value );
        }
        System.out.println();
        
        //객체 삭제
        map.remove("장동건");
        System.out.println("총 Entry 수 : " + map.size());
        
        //하나씩 처리 - entryset() 이용
        Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
        Iterator<Map.Entry<String, Integer>> entryIterator = entrySet.iterator();
        
        while(entryIterator.hasNext()) {
            Map.Entry<String, Integer> entry = entryIterator.next();
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println(key + " : " + value );
        }
        System.out.println();
        
        //객체 전체 삭제
        map.clear();
        System.out.println("총 Entry 수 : " + map.size());
    }
}
 
cs



hashcode( )와 eqauls( ) 재정의를 통한 동일한 키 삽입 예제 코드


키로 사용할 객체(hashcode() eqauls() 재정의)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Member {
    private String name;
    private int age;
    
    /*
        get, set 메소드 생략
    */
 
    @Override
    public int hashCode() {
        return name.hashCode() + age; //이름과 나이가 같으면 동일한 해쉬코드
    }
 
    @Override
    public boolean equals(Object obj) {
        if(obj instanceof Member) {
            Member member = (Member) obj;
            return member.getName().equals(name) && (member.getAge() == age); //이름과 나이가 같으면 true
        } else {
            return false;
        }
    }
}
cs



이름과 나이가 같은 경우 동일한 키로 판단


1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.HashMap;
import java.util.Map;
import set.hashset.Member;
 
public class HashMapExample2 {
    public static void main(String[] args) {
        Map<Member, String> map = new HashMap();
        map.put(new Member("명수", 30), "골드"); //이름과 나이가 같은 Member 키로 저장
        map.put(new Member("명수", 30), "골드");
        
        System.out.println("총 Entry 수 : " + map.size()); //1개만 저장된다.
    }
}
cs


'자료구조' 카테고리의 다른 글

[그래프] 깊이 우선 탐색(DFS)  (0) 2017.03.10
[Map] HashTable과 HashMap의 차이와 Properties  (0) 2017.03.10
[Set]HashSet의 특징  (1) 2017.03.09
[그래프]넓이 우선 탐색(BFS)  (0) 2017.03.07
[그래프] 인접리스트와 인접행렬을 이용한 구현  (0) 2017.02.26

HashSet


Set 인터페이스의 구현 클래스

HashSet은 객체들을 순서없이 저장하고 동일한 객체를 중복 저장하지 않는다.



HashSet의 가장 큰 특징


HashSet이 판단하는 동일한 객체란 꼭 같은 인스턴스를 뜻하지 않는다.

HashSet은 객체를 저장하기전 먼저 객체의 hashCode() 메서드를 호출하여 해시코드를 얻고

이미 저장되어 있는 객체들의 해시코드와 비교한다. 만약 동일한 해쉬코드가 있다면 다시 equals() 메소드로

두 객체를 비교해 참이면 동일한 객체로 저장하고 중복 저장하지 않는다.




예시 코드


Member 클래스


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class Member {
    private String name;
    private int age;
    
    public Member(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    public String getName() {
        return name;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    public int getAge() {
        return age;
    }
 
    public void setAge(int age) {
        this.age = age;
    }
 
    //hashCode()와 eqauls() 재정의    
    
    @Override
    public int hashCode() {  
        return name.hashCode() + age;  //name과 age가 같으면 동일한 hashcode 리턴
    }
 
    @Override
    public boolean equals(Object obj) {
        if(obj instanceof Member) {
            Member member = (Member) obj;
            return member.getName().equals(name) && (member.getAge() == age); //name과 age가 같으면 true
        } else {
            return false;
        }
    }
}
cs



HashSet을 이용한 동일한 데이터를 가진 객체 저장


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.HashSet;
import java.util.Set;
 
public class HashSetExample {
    public static void main(String[] args) {
        Set<Member> set = new HashSet();
        
        set.add(new Member("홍길동", 30));
        set.add(new Member("홍길동", 30));
        //인스턴스는 다르지만 내부 데이터는 동일한 Memeber 인스턴스 2개
        //2개를 모두다 넣지만 하나만 저장된다. (hashcode값이 같고, eqauls() true가 리턴되기에)
        
        System.out.println("총 객체 수 : " + set.size()); // 총 객체 수 : 1    출력
    }
}
cs


'자료구조' 카테고리의 다른 글

[Map] HashTable과 HashMap의 차이와 Properties  (0) 2017.03.10
[Map] HashMap  (0) 2017.03.10
[그래프]넓이 우선 탐색(BFS)  (0) 2017.03.07
[그래프] 인접리스트와 인접행렬을 이용한 구현  (0) 2017.02.26
ArrayList와 LinkedList  (0) 2017.01.02

람다식 메소드 참조


메소드를 참조해서 매개 변수의 정보 및 리턴 타입을 알아내어,

람다식에서 불필요한 매개변수는 제거하는 것



사용법 예시)

두수를 입력받아 큰 값을 리턴하는 Math 클래스의 max메소드


1
2
3
4
5
6
7
8
//Math클래스의 max() 참조 방법
 
//람다식은 단순히 두 개의 값을 max메소드에 전달하는 역활만 함.
(x, y) -> Math.max(x, y)
 
 
//메소드 참조를 이용한 람다식 표현
Math :: max
cs



예제코드


1
2
3
4
5
6
7
8
9
10
11
12
public class Calculator {
    //정적 메소드
    public static int staticMethod(int x, int y) {
        return x + y;
    }
 
    //인스턴스 메소드    
    public int instanceMethod(int x, int y) {
        return x + y;
    }
}
 
cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class MethodReferencesExample {
    public static void main(String[] args) {
        IntBinaryOperator operator;
        
        //정적 메소드 참조
        operator = (x,y) -> Calculator.staticMethod(x, y);
        System.out.println("결과 1 : " + operator.applyAsInt(1,2));
        
        operator = Calculator :: staticMethod;
        System.out.println("결과 2 : " + operator.applyAsInt(3,4));
 
        //정적 메서드는 '클래스명 :: 정적메서드' 형태로 참조 가능
        
        //인스턴스 메서드 참조
        Calculator obj = new Calculator();
        operator = (x,y) -> obj.instanceMethod(x, y);
        System.out.println("결과 3 : " + operator.applyAsInt(5,6));
        
        operator = obj :: instanceMethod;
        System.out.println("결과 3 : " + operator.applyAsInt(7,8));
    }
}
cs




람다식 생성자 참조


생성자 참조도 같은 방법으로 가능하다.



예제코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.function.BiFunction;
import java.util.function.Function;
 
public class ConstructorReferenceExample {
    
    /*
     * 람다식에서의 생성자 참조 "클래스명 :: new"
     */
    
    public static void main(String[] args) {
        Function<String, Member> function1 = Member :: new;
        //매개변수 1개
        Member member1 = function1.apply("dong1");
        
        BiFunction<String, String, Member> function2 = Member :: new;
        //매개변수 2개
        Member member2 = function2.apply("길동", "dong1");
    }
}
cs



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Member {
    private String name;
    private String id;
    
    public Member() {
        System.out.println("기본 생성자");
    }
    
    public Member(String id) {//매개변수 1개
        System.out.println("Member(String id) 실행");
        this.id = id;
    }
    
    public Member(String name, String id) { //매개변수 2개
        System.out.println("Member(String name, String id) 실행");
        this.name = name;
        this.id = id;
    }
}
cs


'Java' 카테고리의 다른 글

[Reflect]Refletion의 정의와 동적 메소드 호출  (0) 2017.03.17
[Collection] 동기화된 컬렉션  (0) 2017.03.10
[람다식] 클래스 멤버와 로컬변수의 사용  (0) 2017.02.24
[람다식] 타켓타입과 함수적 인터페이스  (0) 2017.02.24
[람다식] 람다식 기본  (0) 2017.02.24

넓이 우선 탐색이란?


그래프 G와 시작점 S가 주어졌을 때 S에서 도달 가능한 모든 간선을 찾는 과정



동작 원리


먼저 거리가 1인 정점을 모든 찾은 후 2인 정점을 찾는 식으로 거리를 늘려가며 탐색

탐색을 하면서 시작점으로부터의 거리와 바로 직전 정점을 계산



직전정점 그래프(넓이 우선 탐색 트리)


시작점으로부터 각 정점에 들려야 하는 정점으로 만든 하위 그래프로 트리 형태

모든 정점이 연결되어 있고 nE(간선의 수) = nV(vertex의 수) - 1



예시)


주어진 그래프



1을 시작점으로한 넓이 우선 탐색 트리






코드 구현


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public class BfsExample {
    
    /*
     * 인접리스트로 구현된 그래프의 넓이우선 탐색
     */
    
    static int nV; //총 vertex 개수
    static int nE; //총 edge 개수
    static ArrayList<ArrayList<Integer>> adList = new <ArrayList<Integer>> ArrayList();
    //그래프 구현을 위한 인접리스트
 
    static int[] visit; //방문여부와 완료여부를 표시
    // 0 - 방문 안함,   1 - 방문했지만 아직 탐색 안됨 , 2 - 탐색완료
    static int[][] vertexInfo; //vertex의 위치 정보를 담는 2차원 배열
                               //i번쨰 vertex의 정보 - vertexInfo[i][0] = distance
                               //                   vertexInfo[i][1] = preVertex(상위 vertex)
    
    public static void bfs(int i) {
        visit = new int[nV];
        vertexInfo = new int[nV][2];
        Queue<Integer> q = new LinkedList();
 
        q.offer(i); //탐색 시작 위치의 vertex를 큐에 넣는다.
        visit[i] = 1;
        vertexInfo[0][i] = 0;
        while(!q.isEmpty()) { //Queue의 모든 작업이 없을때 까지
            int temp = q.poll(); //Queue에서 작업(탐색을 위한 데이터)을 가져온다.
            int tempDistance = vertexInfo[temp][0]; 
            for(int j:adList.get(temp)) { //인접리스트에서 temp번째 vertex가 가지고 있는 간선 수만큼 반복
                if(visit[j]==0) { //vertex에 한번도 방문 안했을떄
                    visit[j] = 1; //방문 체크를 한다.
                    vertexInfo[j][0] = tempDistance + 1;
                    vertexInfo[j][1] = temp; //상위 vertex 정보를 넣는다.
                    System.out.println(temp + "에서 " + j + "로 이동");
                    q.offer(j); //새로 찾은 vertex를 탐색하기 위해 Queue에 삽입
                }
            }
            visit[temp] = 2; //탐색 완료된 vertex 플래그
        }    
    }
 
    public static void main(String[] args) {
        
        //인접리스트를 이용한 그래프 구현
        Scanner scan = new Scanner(System.in);
 
        nV = scan.nextInt();
        nE = scan.nextInt();
 
 
        for(int i=0;i<nV;i++) adList.add(new<Integer> ArrayList());
        //adList에 담을 리스트(각 vertex마다 인접한 vertext를 표현한 리스트)
 
        for(int i=0;i<nE;i++) {
            int vertex1, vertex2;
            vertex1 = scan.nextInt();
            vertex2 = scan.nextInt();
 
            adList.get(vertex1).add(vertex2);
            adList.get(vertex2).add(vertex1);
        }
        
        //넓이우선 탐색시작
        bfs(1);
        
        int i = 0;
        for(int[] vertex:vertexInfo) {
            System.out.print(i++ + "-");
            System.out.print("distance" + vertex[0] + ", ");
            System.out.println("preVertex" + vertex[1]);
        }
    }
}
cs


'자료구조' 카테고리의 다른 글

[Map] HashMap  (0) 2017.03.10
[Set]HashSet의 특징  (1) 2017.03.09
[그래프] 인접리스트와 인접행렬을 이용한 구현  (0) 2017.02.26
ArrayList와 LinkedList  (0) 2017.01.02
Array 배열 for Java  (0) 2016.12.23

+ Recent posts

티스토리툴바