글 읽기 - IP Address Summarization 데이터 확인 부탁드립니다.

bupjae 6년 전 1

이 문제를 시도한 사람이 저 혼자밖에 없어서 상당히 조심스럽습니다만

제출한 답안이 틀렸습니다 판정을 받아서 틀린 원인을 열심히 찾아보려 했지만 찾을 수 없었습니다.

계속 찾아보던 중에 문제의 공식 출처 https://code.google.com/codeja... 를 찾았습니다.

이 곳에서 연습을 위해 입력 데이터를 공개해 놓고, 출력 결과를 제출하면 맞았는지 검증을 해 주고 있습니다. 여기서 주어진 입력 데이터로 디버그를 해 볼려고 했습니다만, 출력 결과가 올바르다는 응답을 받았습니다.

제 답안은 IP address의 각 bit로 분기하는 trie 자료구조를 사용했습니다.

삽입할 때는 한 네트워크를 완전히 포함할 수 있는 네트워크가 이미 있으면 그 데이터는 삽입하지 않은 채 반환하도록 했고

삽입 종료 후 인접 네트워크의 통합 (예: 10.0.0.0/9 + 10.128.0.0/9 = 10.0.0.0/8)을 수행했습니다.

package main

import (
	"bufio"
	"fmt"
	"net"
	"os"
)

var in = bufio.NewScanner(os.Stdin)

func NextInt() int {
	in.Scan()
	r := 0
	for _, c := range in.Bytes() {
		r *= 10
		r += int(c - '0')
	}
	return r
}

func NextCIDR() *net.IPNet {
	in.Scan()
	_, r, _ := net.ParseCIDR(in.Text())
	return r
}

func main() {
	for i, n := 1, NextInt(); i <= n; i++ {
		fmt.Printf("Case #%d:\n", i)
		main2()
	}
}

type trie struct {
	data  *net.IPNet
	child [2]*trie
}

func (t *trie) insert(data *net.IPNet) {
	s, _ := data.Mask.Size()
	var f func(*trie, int)
	f = func(n *trie, d int) {
		if d == s {
			n.data = data
			n.child[0] = nil
			n.child[1] = nil
		}
		if n.data != nil {
			return
		}
		k := (data.IP[d/8] >> uint(7-d%8)) & 1
		if n.child[k] == nil {
			n.child[k] = new(trie)
		}
		f(n.child[k], d+1)
	}
	f(t, 0)
}

func (t *trie) maybeMerge() {
	if t.child[0] != nil {
		t.child[0].maybeMerge()
	}
	if t.child[1] != nil {
		t.child[1].maybeMerge()
	}
	if t.child[0] != nil && t.child[1] != nil && t.child[0].data != nil && t.child[1].data != nil {
		ones, bits := t.child[0].data.Mask.Size()
		t.data = &net.IPNet{IP: t.child[0].data.IP, Mask: net.CIDRMask(ones-1, bits)}
		t.child[0] = nil
		t.child[1] = nil
	}
}

func (t *trie) print() {
	if t.data != nil {
		fmt.Println(t.data)
	}
	if t.child[0] != nil {
		t.child[0].print()
	}
	if t.child[1] != nil {
		t.child[1].print()
	}
}

func main2() {
	var r trie
	for n := NextInt(); n > 0; n-- {
		r.insert(NextCIDR())
	}
	r.maybeMerge()
	r.print()
}

startlink 6년 전 0

안녕하세요. 채점을 해보면 출력파일이 비어있습니다. 따로 실행을 시켜보면 출력이 정상적으로 나오는걸 보니 채점 프로그램 버그인듯합니다.

확인해보고 다시 답변달겠습니다.

bupjae 6년 전 0

"net" 패키지에 의존하지 않도록 답안을 수정해서 제출한 결과 (8073646) AC를 받았습니다.

혹시나 해서 원래 구현을 다시 제출했더니 (8073666) 이번에는 WA가 아니라 RTE를 받았습니다.

몇 번의 삽질 제출 끝에 "net" 패키지의 초기화 루틴에 채점 환경에서 허용하지 않는 syscall 이 있었던 것으로 잠정 결론을 내렸습니다.

언어 표준 라이브러리에서 CIDR을 제공하길래 그걸 이용해 보려는 안이한 생각이 이런 참사(?)를 불러올 줄은 몰랐습니다.

다만, 처음부터 WA가 아니라 RTE를 받았더라면 원인 파악이 좀 더 쉬웠을 거라는 아쉬움이 남네요.

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

문제

문제

출처

ICPC

IP Address Summarization 데이터 확인 부탁드립니다.

bupjae 6년 전 1

startlink 6년 전 0

bupjae 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말