글 읽기 - BFS 질문 있습니다.

tigger97 3년 전 0

24~28번째 줄을 지우고, 주석처리 된 부분의 주석을 없애면 왜 안되는지 궁금합니다.

주석처리된 부분도 다음 노드를 검사하는 작업인데 왜 이렇게 하면 틀렸다고 나오나요? ( 예제까지는 맞다고 나오는데 7%에서 바로 틀립니다.)

즉 다음 노드를 검사하는 부분이 32~35번째 줄에 들어가면 안되고, 23~27번째 줄에 들어가야 하는 이유가 궁금합니다.

//Kotlin입니다.
import java.util.*

fun main(){
    val br = System.`in`.bufferedReader()
    val (a, b) = br.readLine().split(' ').map { it.toInt() }
    val (n, m) = br.readLine().split(' ').map { it.toInt() }
    data class Node(val curNum : Int, var routeDep : Int)
    val arr = Array(10001){ Stack<Int>() }
    val q : Queue<Node> = LinkedList<Node>()
    val visited = Array(10001){false}
    for(i in 0 until m){
        val (x, y) = br.readLine().split(' ').map { it.toInt() }
        arr[x].add(y)
        arr[y].add(x)
    }
    q.add(Node(a, 0))
    visited[a] = true
    var printed = false
    while (q.isNotEmpty()){
        val temp = q.poll()
        val number = temp.curNum
        val routeDepth = temp.routeDep
        if(number == b){
            println(routeDepth)
            printed = true
            break
        }
        for(i in arr[number].indices){
            if(!visited[arr[number][i]]){
                visited[arr[number][i]] = true
                q.add(Node(arr[number][i], routeDepth+1))
//                if(arr[number][i] == b){
//                    println(routeDepth+1)
//                    printed = true
//                }
            }
        }
    }
    if(!printed) println(-1)
}

hun2two 2년 전 0

문제 풀면서 동일현상을 만났습니다.

○ 원인
너비우선탐색(bfs)으로 문제풀이 시 a==b이고, a→b로 가는 간선정보가 없는 경우
치환횟수=-1이 아닌 0이 되어야 함.

결함이 많은 문제인 것 같습니다.

1. 문제만 읽고서 양방향 그래프 라는 것을 알기 어려움

2. a==b인 케이스가 있을 수 있다는 것도 다익스트라가 아닌 너비우선탐색(bfs)로 풀다보니 알게 됨.

다익스트라로 풀이하면 나 자신의 거리정보를 0으로 초기화하고 시작하므로, 이런 문제를 만날 수 없음.

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

문제

문제

출처

ICPC

BFS 질문 있습니다.

tigger97 3년 전 0

hun2two 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말