[백준 2267] 단지번호 붙이기

문제

아이디어

총 단지수 == Graph 갯수

단지 내 집의 수 == Graph 내 노드(Vertex) 수

 

출력으로 요구하는 값만 봐고 DFS & BFS가 떠올랐다.

 

총 단지수 => main 에서 DFS 호출 수
단지 내 집의 수 => 한 DFS 내 재귀 호출 수
그래프 연결작업 => 행렬 전체를 돌며 '오른쪽, 아래'로 연결된 [행번호,열번호] 양방향 연결 리스트 추가

약간 헷갈렸던 것이 단지 내 집의 수 (DFS내 재귀 호출 수 카운트) 하는 부분이었다.

 

DFS 코드

    // main에서 마지막 argument로 DFS 호출 횟수를 keep하는 변수를 넘겨서
    
    fun dfs (rowIndex: Int, colIndex: Int, callCount: Int) {
        //start vertex 는 0,0 가정 상관없음.
        visited[rowIndex][colIndex] = true
        //호출될 때마다 하나씩 증가시키려 했으나
        //기본적으로 argument들이 모두 value-type이라 값이 수정될 수 없다.
        callCount++
        adjacencyArray[rowIndex][colIndex].forEach{
            if (!visited[it[0]][it[1]]) {
                dfs(it[0],it[1], callCount++)
            }
        }
    }

3번째 argument 'callCount'는 기본적으로 value type이기 때문에 함수 내부에서 값을 변경할 수 없다.

따라서 잘못된 코드이다.

 

이 문제를 해결하기 위해 dfs 호출 횟수를 keep하는 멤버 변수를 Graph 클래스 내에 선언했다.

stackoverflow 에서는 전역 변수, 정적 변수 사용을 이야기하나 나는 이런 방식을 쓰지 않는다.

 

실수

"단지내 집의 수를 오름차순으로 정렬하여"

오름차순으로 정렬하지 않아 채점 6%에서 틀렸다고 나왔다.

테스트 케이스가 많이 주어지지 않거나 모의 채점 결과가 나오지 않는 코딩테스트를 볼 경우 이런 사소한 실수 때문에 점수를 획득하지 못할 수 있다.

문제를 꼼꼼히 읽자.

 

+

 

이렇게 행렬, 그래프가 2차원 배열 형태로 주어질 때는

언제나 Out Of Index 범위를 유의해야한다.

 

구현

[Graph.kt]

import java.util.*

class Graph (private val vertexNumber : Int, val matrix: Array<IntArray>){
//    정방행렬 matrix [5,25] 입력
//    return : Graph 수, Graph 내의 Vertex 수

//    key point : matrix -> adjacencyArray //

//    이미 검사했던 Graph section 을 어떻게 구분할까? (visited)
//    visited 검사 + 상하좌우 연결 (이미 검사한 곳은 연결도 skip)
//    상,하,좌,우 연결 (undirected connection) , 0인곳은 연결하지 않음
//    모든 Matrix 원소에 대해 visited[N][N] 을 두는 것 가능.
    val visited : Array<BooleanArray> = Array<BooleanArray>(vertexNumber){ BooleanArray((vertexNumber)) }

//    2차원 배열에 대해 모든 원소가 연결된 리스트(상하좌우 대상) 를 가짐. visited 는 기록
//    리스트 최대길이 4
    private val adjacencyArray : Array<Array<LinkedList<IntArray>>> = Array<Array<LinkedList<IntArray>>>(vertexNumber){
    Array<LinkedList<IntArray>>(vertexNumber){LinkedList<IntArray>()}
    }

    val graphNumber : LinkedList<Int> = LinkedList<Int>()
    var dfsCounter : Int = 0
//    out of index 조심.
    fun connectEdge() {
        // 상하좌우 다할 필요 없이 우하향만 검사해도됨. (어차피 0을 제외한 모든 원소를 다 우회하며 연결시도함)
        for(i in 0 until vertexNumber) {
            // 우방향 검사
            for(j in 0 until vertexNumber) {
                if(matrix[i][j] == 0) continue
//                숫자가 1이면 (집이 있음)
                else {
//                    우방향 검사 양방향으로 연결리스트에 추가
                    if (j < vertexNumber-1 && matrix[i][j+1] == 1) {
                        adjacencyArray[i][j].add(arrayOf(i,j+1).toIntArray())
                        adjacencyArray[i][j+1].add(arrayOf(i,j).toIntArray())
                    }
//                    하방향 검사 양방향으로 연결리스트에 추가
                    if (i < vertexNumber-1 && matrix[i+1][j] == 1) {
                        adjacencyArray[i][j].add(arrayOf(i+1,j).toIntArray())
                        adjacencyArray[i+1][j].add(arrayOf(i,j).toIntArray())
                    }
                }
            }
        }
    }

//    main 에서 dfs 수행전에 visited[][] 및 1값을 검사하고 ㄱㄱ 하면됨.

    fun dfs (rowIndex: Int, colIndex: Int) {
        //start vertex 는 0,0 가정 상관없음.
        visited[rowIndex][colIndex] = true
        dfsCounter++
        adjacencyArray[rowIndex][colIndex].forEach{
//            연결되있는 x,y 좌표에 대한 방문여부 검사.
            if (!visited[it[0]][it[1]]) {
                dfs(it[0],it[1])
            }
        }
    }


}

[main.kt]

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main(args: Array<String>) {
    val bufferedReader : BufferedReader = BufferedReader(InputStreamReader(System.`in`))
    var token = StringTokenizer(bufferedReader.readLine())
    val elementNumber : Int = token.nextToken().toInt()

//    내부적으로 다음 코드가 어떻게 돌아가는지
//    Initialization with Lambda 원리를 살펴보자.
    /*
    val matrix : Array<IntArray> = Array<IntArray>(elementNumber){
        token = StringTokenizer(bufferedReader.readLine(), "")
        IntArray(elementNumber) {
            token.nextToken().toInt()
        }
    }
    */
    val matrix : Array<IntArray> = Array<IntArray>(elementNumber){
        IntArray(elementNumber)
    }
//    matrix 초기화
    for(row in 0 until elementNumber) {
        val line = bufferedReader.readLine()
        for(col in 0 until elementNumber) {
            matrix[col][row] = line[col].toInt() - 48
        }
    }
    val graph = NumberingSection(elementNumber, matrix)
    graph.connectEdge()

    var graphNumber : Int = 0
    for(row in 0 until elementNumber) {
        for(col in 0 until elementNumber) {
//            방문하지 않았거나 0이면 그래프 탐색 skip
            if(!graph.visited[row][col] && graph.matrix[row][col] == 1) {
//              How to know dfs 호출횟수 == 방문한 노드 갯수
                graph.dfs(row, col)
//                dfs 내부적으로 호출횟수를 dfsCounter 로 센다.
                graph.graphNumber.add(graph.dfsCounter)
//                dfs 호출 횟수를 LinkedList 에 기록하고 0으로 초기화한다.
                graph.dfsCounter = 0
                graphNumber++
            }
        }
    }

    println(graphNumber)
    graph.graphNumber.sort()
    for(vertexNumber in graph.graphNumber) {
        println(vertexNumber)
    }
}

 

 

Reference

stackoverflow.com/questions/28470909/how-can-i-find-number-of-times-a-recursive-function-calls-itself

재귀함수 호출 횟수 카운트 방법을 static 변수 선언이라는 솔루션으로 제시하고있다.