BFS(너비 우선 탐색)

너비 우선 탐색

너비우선탐색이란 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. –위키피디아 출처
깊이우선탐색은 스택을 이용하지만 너비우선탐색은 큐를 이용한다.
말은 간단하다.
DFS_BFS

한번살펴보자
1에서 시작을 한다면 인접한 정점으로 이동한다.
1에서 인접한 정점은 2와3이다. 그래서 1->2, 1->3으로 이동한다.
그리고 2의 인접한 정점은 4밖에 없다. 2->4
다음은 3의 인접한 정점은 5,6,7 이다 3->5, 3->6, 3->7
이렇게 이동한다.

코드를 보자.

static int[][] BFS = {
        {0,0,0,0,0,0,0,0},
        {0,0,1,1,0,0,0,0},
        {0,1,0,0,1,0,0,0},
        {0,1,0,0,0,1,1,1},
        {0,0,1,0,0,0,0,0},
        {0,0,0,1,0,0,0,0},
        {0,0,0,1,0,0,0,0},
        {0,0,0,1,0,0,0,0},
};
static int rear = 0, front = 0; // 전단과 후단을 나타내는 변수
static int  queue[] = new int[10] , search[] = new int[10]; //큐와 방문한 정점을 체크하고 위함

큐를 사용하기 때문에 큐에다 넣을 배열을 만든다.
큐에 넣을때는 rear을 사용 빼야할때는 front를 사용한다.

public static void BFS(int s){
    search[s] = 1;
    queue[rear++] = s;
    //큐에서 다 빼낼때까지
    while (front < rear){
        s = queue[front++];
        for(int i = 1; i <=7; i++){
            if(BFS[s][i] == 1 && search[i] != 1){
                search[i] = 1;
                System.out.println(s + "에서 " + i + "로 이동!");
                queue[rear++] = i;
            }
        }
    }
}

이것도 마찬가지로 정점을 방문하지 않고 인접행렬일때만 이동한다.
방문할때 방문했다고 체크해주고 큐에 쌓는다. 그리고 방문이 끝났다면 다시 큐에서 꺼내 꺼낸 값의 정점들을 찾는다.
그럼 결과는 다음과 같을 것이다.

1에서 2로 이동!
1에서 3로 이동!
2에서 4로 이동!
3에서 5로 이동!
3에서 6로 이동!
3에서 7로 이동!

DFS(깊이 우선 탐색)

깊이 우선 탐색

깊이우선탐색이란 트리 및 그래프 등을 탐색하는 알고리즘이다.
특정 노드를 출발하여 깊게 들어 갈 수 있을때 까지 들어가고 들어 갈 곳이 없다면 다시 나오는 알고리즘이다.
깊게 들어간다해서 깊이 우선 탐색, 스택을 이용하여 구현한다.

DFS_BFS

위에 노드를 한번 보자.
만약 루트가 1이라면 1->22->4로 4에선 더이상 갈곳이 없어 다시 나온다. 그럼 다시 3->5 5역시 갈곳이 없기에 나온다.
3->6 6도 마찬가지다. 3->7로 가고 끝난다.

그전에 알아두어야 할 것이 있는데 바로 인접행렬이다.
인접행렬이란 그래프 이론에서 인접행렬은 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정사각행렬이다. -위키피디아 출처
바로 저거다.
예를들어

1 2 3 4 5 6 7
1 0 1 1 0 0 0 0
2 1 0 0 1 0 0 0
3 1 0 0 0 1 1 1
4 0 1 0 0 0 0 0
5 0 0 1 0 0 0 0
6 0 0 1 0 0 0 0
7 0 0 1 0 0 0 0

이런 형태가 되는게 인접행렬이다.
(1,2)(2,1) (1,3)(3,1) … 이런 것들이 한쌍이 되는거다.

그럼 코드를 보자.

static int[] search = new int[10];
static int[][] DFS = {
        {0,0,0,0,0,0,0,0},
        {0,0,1,1,0,0,0,0},
        {0,1,0,0,1,0,0,0},
        {0,1,0,0,0,1,1,1},
        {0,0,1,0,0,0,0,0},
        {0,0,0,1,0,0,0,0},
        {0,0,0,1,0,0,0,0},
        {0,0,0,1,0,0,0,0},
};

search는 방문한경우 다시 방문하는 걸 막기위함이다.

public static void DFS(int v) {
    //정점을 방문했다고 표시
    search[v] = 1;
    for (int i = 1; i <= 7; i++) {
        //정점을 방문하지 않고 인접행렬이라면
        if (search[i] != 1 && DFS[v][i] == 1 ) {
            System.out.println(v + "에서 " + i + "로 이동!");
            DFS(i);
        }
    }
}

함수를 호출하면 방문했다고 표시를 하고 정점을 조사해야 된다.
그리고 방문하지 않고 인접행렬이라면 이동하면 된다.
재귀로 만든 이유는 스택구조로 만들기 위해서다.
만약 더이상갈점이 없다면 다시 돌아가야하기 때문이다.
그럼 결과는 다음과 같이 나올 것이다.

1에서 2로 이동!
2에서 4로 이동!
1에서 3로 이동!
3에서 5로 이동!
3에서 6로 이동!
3에서 7로 이동!

삽입정렬

삽입정렬

  • 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
  1. 시작은 두번째 리스트 부터 한다. 이유는 첫번째 리스트는 하나이기 때문에 정렬이 되어있다고 본다.

  2. 두번째는 temp 에 넣어두고 첫번째와 비교한다. 비교시 temp 가 작다면 첫 번째 리스트를 두번째로 이동한다. temp 는 첫번째에 삽입한다.

  3. 이번엔 세번째 리스트를 temp에 넣어둔다. temp보다 큰값이 나올때까지 이동시킨다.

temp = 2

6 2 7 8 1

  • 6과 temp 와 비교한다.
  • temp 가 작기때문에 6을 이동시킨다.
  • 6이 첫번째 이므로 temp를 첫번째 자리에 둔다.
  • 그럼 2 6 7 8 1로 정렬되었다
  • 다시 7을 temp에 넣는다. temp보다 큰값이 없기때문에 이동하지 않는다. 8도 마찬가지
  • 1을 temp 에 넣는다.
  • 8과 비교해서 temp가 작으므로 8을 다섯번째로 이동한다.
  • 7도 이동한다.
  • 6도 이동한다.
  • 2도 이동한다.
  • 1을 삽입한다.
public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int temp = arr[i];
        int j;
        for (j = i - 1; (j >= 0) && (temp < arr[j]); j--) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = temp;
    }
}