너비우선탐색

그래프 탐색에서 탐색 시작점의 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 시작점으로 다시 인접한 정점들을 방문하는 방식
최단경로로 경로를 찾을 수 있음. 단 모든 간선들의 가중치가 동일하여야 함.

기본구조

private fun bfs(graph:Array<ArrayList<Int>>): {
	// que, 방문여부 생성
    val que = LinkedList<Int>()
    val visited = BooleanArray(graph.size){false}

	// 초기 방문 추가
    que.offer(1)
    visited[1] = true

    while (que.isNotEmpty()) { // 큐가 빌때까지 반복
    	val now = que.poll() // 방문
		
        if (now == target) // 목표 확인
        	// do somthing
        
        for (moved in graph[now]) { // 인접리스트 순회
            if (!visited[moved]) { // 방문하지 않았다면 que에 추가
                que.offer(moved)
                visited[moved] = true
            }
        }
    }
}

index 확인

if (idx in visited.indices) { // in indices 를 이용하여 인덱스 범위 내인지 확인 가능
	//do somthing
}

이동 순회

listOf(
	{ x: State -> State(x.pos * 2, x.time) },
    { x: State -> State(x.pos + 1, x.time + 1) },
    { x: State -> State(x.pos - 1, x.time + 1) },
    ).forEach {
    	val moved = it(now)

		if (moved.pos in visited.indices) {
        	if (!visited[moved.pos]) {
            	que.offer(moved)
                visited[moved.pos] = true
                }
            }
        }

listof 를 이용하여 리스트를 생성한후 forEach로 순회

data class

data class Point(val x:Int, val y:Int)

que 데이터를 넣을때 데이터 클래스를 생성해서 사용