글 읽기 - 3%에서 틀립니다 문제가 뭘까요??

codingbrucelee 1년 전 0

문제 예시와 반례가 다 맞는데 왜 3%에서 틀리는지 모르겠습니다..

import java.util.*

class Graph(size: Int) {
    var nodes: Array<Node> = Array(size + 1) { num ->
        Node(num)
    }
    val map = hashMapOf<Int, Int>()

    init {
        // map의 value값을 0으로 다 초기화해주기
        repeat(size) {
            map[it + 1] = 0
        }
    }

    data class Node(
        var num: Int = 0,
        var adjacent: LinkedList<Node> = LinkedList(),
        var marked: Boolean = false
    )

    fun addEdge(index1: Int, index2: Int) {
        val n1 = nodes[index1]
        val n2 = nodes[index2]
        if (!n1.adjacent.contains(n2)) n1.adjacent.add(n2)
        if (!n2.adjacent.contains(n1)) n2.adjacent.add(n1)
    }

    fun dfs(r: Node) {
        r.marked = true
        map[r.num] = r.num
        for (n in r.adjacent) {
            if (!n.marked) dfs(n)
        }
    }

}

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    // N : 정점 수
    // M : 간선 수
    // R : 시작 정점
    val (N, M, R) = br.readLine().split(" ").map { it.toInt() }

    // 그래프 만들기
    val graph = Graph(N)

    // 간선 연결하기
    repeat(M) {
        val (U, V) = br.readLine().split(" ").map { it.toInt() }
        graph.addEdge(U, V)
    }
    br.close()

    // 연결된 정점들을 오름차순으로 정렬하기
    graph.nodes.forEach { it.adjacent.sortBy { node -> node.num } }

    graph.dfs(graph.nodes[R])

    graph.map.forEach {
        bw.write("${it.value}\n")
    }

    bw.flush()
    bw.close()

}

chldn323 1년 전 2

방문한 순서를 출력해야 하지만 map의 value에 정점의 번호를 다시 넣고 있습니다.

코드 내용대로면 value에는 몇 번째 방문인지 넣어야 할 거 같네요.

또 n1의 adjacent에 n2, n2의 adjacent에 n1을 넣으면서 서로를 참조하고 있는데 각각의 adjacent를 출력했을 때 stack overflow가 발생합니다. n1-n2-n1-n2....

list를 사용할 거면 정점 객체가 아니라 정점의 번호만 넣어도 됩니다.

불러올 때도 graph.nodes[a].adjacent[b]가 c이면 a정점의 b번째 노드는 c라는 뜻이므로 graph.nodes[c]를 호출하면 됩니다.

반례도 추가합니다.

input:
5 2 2
1 2
2 3

answer:
2
1
3
0
0

output:
1
2
3
0
0

codingbrucelee 1년 전 0

아 이해했습니다! 답변 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

3%에서 틀립니다 문제가 뭘까요??

codingbrucelee 1년 전 0

chldn323 1년 전 2

codingbrucelee 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말