paizaの練習問題を解く一方通行（グラフ上の移動） Go編

こんにちは、ナナオです。

前回に引き続き競プロを実施していきたいと思います。

今回の問題は以下です。

一方通行（グラフ上の移動） | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】

実装

まずは以下のように実装しました。

package main
import "fmt"
func main(){
    var n int
    fmt.Scan(&n)
    g := make([][]int, n)
    for i := 0; i < n; i++ {
        g[i] = make([]int, n)
    }
    for i := 1; i < n; i++ {
        var a, b int
        fmt.Scan(&a, &b)
        g[a - 1][b - 1] = i
        g[b - 1][a - 1] = i
    }
    fmt.Println(1)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if g[i][j] == i + 1 {
                fmt.Println(j + 1)
                break
            }
        }
    }
}

ですがこれだと入力例１は解けてもそれ以外が解けません。

ということで少し改修しました。

package main
import "fmt"
func main(){
    var n int
    fmt.Scan(&n)
    g := make([][]int, n)
    for i := 0; i < n; i++ {
        g[i] = make([]int, n)
    }
    for i := 1; i < n; i++ {
        var a, b int
        fmt.Scan(&a, &b)
        g[a - 1][b - 1] = i
        g[b - 1][a - 1] = i
    }
    fmt.Println(1)
    i := 0
    cnt := 1
    for {
        for j := 0; j < n; j++ {
            if g[i][j] == cnt {
                fmt.Println(j + 1)
                i = j
                cnt++
                break
            }
        }
        if cnt == n {
            break
        }
    }
}

問題は解けるようになったはずですが、タイムオーバーになってしまいました。

回答を見つつ修正しました。

package main
import "fmt"
func main(){
    var n int
    fmt.Scan(&n)
    g := make([][]int, n)
    for i := 0; i < n; i++ {
        g[i] = make([]int, n)
    }
    for i := 1; i < n; i++ {
        var a, b int
        fmt.Scan(&a, &b)
        g[a - 1][b - 1] = 1
        g[b - 1][a - 1] = 1
    }
    i := 0
    for _i := 0; _i < n; _i++ {
        fmt.Println(i + 1)
        for j := 0; j < n; j++ {
            if g[i][j] == 1 {
                g[j][i] = 0
                i = j
                break
            }
        }
    }
}

これで通るようになりました。

普通に配列には1入れるだけでよかったんですね。。

というわけで今回はこれで👍

実装#

実装