[백준] - 그림 (BFS)

1.시작하는 칸을 큐에 넣고 표시남김

2.큐에서 원소 꺼내서 인접한 칸 3번에 대해 3번 진행

3. 해당칸을 이전에 방문했다면 아무것도 하지 않고, 방문했다는 표시 남기고 큐에 삽입

4. 큐가 빌때까지 2번을 반복

 

boj 1926 그림1.시작하는 칸을 큐에 넣고 표시남김

 

2.큐에서 원소 꺼내서 인접한 칸 3번에 대해 3번 진행

 

3. 해당칸을 이전에 방문했다면 아무것도 하지 않고, 방문했다는 표시 남기고 큐에 삽입

 

4. 큐가 빌때까지 2번을 반복

 

 

 

boj 1926 그림

https://www.acmicpc.net/problem/1926

fun main() = with(Scanner(System.`in`)) {
    val x = nextInt()
    val y = nextInt()
    val array: Array<Array<Int>> = Array(x) { Array(y) { 0 } }
    val isVisited: Array<Array<Boolean>> = Array(x) { Array(y) { false } }
    val dx = arrayOf(1, 0, -1, 0)
    val dy = arrayOf(0, 1, 0, -1)

    for (i in 0 until x) {
        for (j in 0 until y) {
            array[i][j] = nextInt()
        }
    }


    var result = 0
    var imageCount = 0
    for (i in 0 until x) {
        for (j in 0 until y) {
            if(isVisited[i][j] || array[i][j] == 0) continue
            val queue: Queue<Pair<Int, Int>> = LinkedList()
            isVisited[i][j] = true
            queue.add(i to j)
            imageCount ++

            var area = 0
            while (queue.isNotEmpty()){
                area++
                val pair = queue.poll()!!
                for(i in 0 until 4){
                    val nx = pair.first + dx[i]
                    val ny = pair.second + dy[i]
                    if(nx < 0 || nx >= x || ny < 0 || ny >= y) continue
                    if(isVisited[nx][ny] || array[nx][ny] == 0) continue
                    isVisited[nx][ny] = true
                    queue.add(nx to ny)
                }
            }
            result = max(result, area)
        }
    }
    println(imageCount)
    println(result)

}

 

 

 

 

https://www.youtube.com/watch?v=ftOmGdm95XI