day2

2021년 12월 20일

 

bfs

 

 

1. 코틀린 queue

Queue는 인터페이스이고 구현클래스인 LinkedList를 사용한다.

 

import java.util.*

 

fun main() {

    // 큐 선언하기

    var queue: Queue<Int> = LinkedList<Int>()

}

 

add

poll : retrive and remove , or null

peek : retrieve, but does not remove, null

remove : retrive and remove

 

          Summary of Queue methods

                Throws exception.      Returns special value

Insert          add(e)                      offer(e)

Remove.      remove()                 poll()

Examine      element()                 peek()

 

 

2. bfs 만들어보기

 

    1
  /    |
  2   3
 / |  /  |
 4 5 6  7

package bfs

import java.util.*

var graph = Array(8){ mutableListOf<Int>()}
fun bfs(start:Int){
    var queue:Queue<Int> = LinkedList();
    var visited = MutableList(8){false}

    queue.add(start);

    while(queue.peek() != null){
        var temp = queue.poll();
        println(temp);
        visited[temp] = true
        for(i in graph[temp]){
            if(!visited[i]){
                queue.add(i);
            }
        }
    }
}

fun main(){
    println("helloooo")
    graph[1].add(2)
    graph[1].add(3)

    graph[2].add(1)
    graph[2].add(4)
    graph[2].add(5)

    graph[3].add(1)
    graph[3].add(6)
    graph[3].add(7)

    graph[4].add(2)

    graph[5].add(2)

    graph[6].add(3)
    
    graph[7].add(3)

    bfs(1)
}

 

 

3. bfs 의 depth 파악

package bfs

import java.util.*

var graph = Array(8){ mutableListOf<Int>()}

fun bfs(start:Int){
    var queue:Queue<Int> = LinkedList();
    var visited = MutableList(8){false}

    var level = 0;

    queue.add(start);

    //!queue.isEmpty() 도 가능
    while(queue.peek() != null){
        var levelSize:Int = queue.size
        
        while (levelSize>0){
            levelSize--
            var temp = queue.poll();
            println("level : $level , temp : $temp");
            visited[temp] = true
            for(i in graph[temp]){
                if(!visited[i]){
                    queue.add(i);
                }
            }
        }

        level++;
    }
}

fun main(){
    println("helloooo")
    graph[1].add(2)
    graph[1].add(3)

    graph[2].add(1)
    graph[2].add(4)
    graph[2].add(5)

    graph[3].add(1)
    graph[3].add(6)
    graph[3].add(7)

    graph[4].add(2)

    graph[5].add(2)

    graph[6].add(3)
    graph[7].add(3)

    bfs(1)
}