글 읽기 - 완벽한 코드, 그렇지 못한 결과

blucky8649 3달 전 0

1. BFS와 인접행렬을 이용하여 모든 경로의 최단거리를 구해준다.

2. 먼지를 방문하는 모든 경우의 수를 Check 하여 총 이동거리의 최솟값을 구해준다.

3. 그러고 틀린다.

질문 게시판에 있는 모든 테케는 맞고 있는데요, 20퍼에서 광탈됩니다. 제가 쓴 로직은 맞는 것 같으나 어디에서 나사가 빠진건지 모르겠네요..

import java.lang.Integer.min
import java.util.*

private lateinit var isVisited : Array<Boolean>
var answer = Integer.MAX_VALUE

fun main(args: Array<String>) = with(System.`in`.bufferedReader()){
    while (true) {
        answer = Integer.MAX_VALUE
        val dust = Array<Dot>(11) {Dot(0, 0)}
        var dust_idx = 1
        val(C, R) = readLine().split(" ").map { it.toInt() }
        if (R + C == 0) break
        val map : Array<Array<Char>> = Array(R){Array(C){' '}}
        var start : Dot = Dot(0, 0)
        for (i in 0 until R) {
            val str = readLine()
            for (j in 0 until C) {
                map[i][j] = str[j]
                if (map[i][j] == '*') dust[dust_idx++] = (Dot(j, i))
                else if (map[i][j] == 'o') dust[0] = Dot(j, i)
            }
        }
        val list = Array(dust_idx) {Array<Int>(dust_idx) {0} }

        /** BFS를 사용하여 모든 경로의 최단거리를 구한다. **/
        for (i in 0 until dust_idx) {
            for (j in i + 1 until dust_idx) {
                val weight = BFS(R, C, dust[i], dust[j], map)
                if (weight== -1) { println(-1) ; return }
                list[i][j] = weight
                list[j][i] = weight
            }
        }
        isVisited = Array(dust_idx) {false}
        DFS(0, 0, list, dust_idx, 0)
        println(answer)
    }
}

/**
 * @param cur : 현재 위치
 * @param depth : 백트래킹 깊이
 * @param list : 인접리스트
 * @param size : 먼지의 개수
 * @param sum : 총 쓸고나간 거리
 */
fun DFS(cur : Int, depth : Int, list : Array<Array<Int>>, size : Int, sum : Int) {
    if (depth == size - 1) {
        answer = min(answer, sum)
        return
    }
    for (i in 1 until size ) {
        if (isVisited[i]) continue
        isVisited[i] = true
        DFS(i, depth + 1, list, size, sum + list[cur][i])
        isVisited[i] = false
    }
}
fun BFS(R : Int, C : Int, start : Dot, end : Dot, map : Array<Array<Char>>) : Int {
    val dy = arrayOf(-1, 0, 1, 0)
    val dx = arrayOf(0, 1, 0, -1)
    val isVisited = Array(R) {Array<Boolean> (C) {false} }
    val q : Queue<Dot> = LinkedList<Dot>()
    isVisited[start.y][start.x] = true
    q.offer(Dot(start.x, start.y, start.moved))

    while (!q.isEmpty()) {
        val cur = q.poll()

        if (cur.x == end.x && cur.y == end.y) return cur.moved
        for (i in 0 .. 3) {
            val nx = cur.x + dx[i]
            val ny = cur.y + dy[i]
            if (nx in 0 until C && ny in 0 until R && !isVisited[ny][nx] && map[ny][nx] != 'x') {
                q.offer(Dot(nx, ny, cur.moved + 1))
                isVisited[ny][nx] = true
            }
        }
    }
    return -1
}
data class Dot (var x : Int, var y : Int){
    var moved : Int = 0
    constructor(x : Int, y : Int, _moved : Int) : this(x, y){
        moved = _moved
    }
}
data class Node(val end : Int, val weight : Int)

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

문제

문제

출처

ICPC

완벽한 코드, 그렇지 못한 결과

blucky8649 3달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말