[BOJ] 29333 - One Walk

https://www.acmicpc.net/problem/29333

BOJ - One Walk

문제 유형: 그래프, 애드 혹, 해 구성하기

문제 난이도: Gold II

시간 제한: 1초

메모리 제한: 1024MB

 

문제

무방향 단순 그래프 G가 주어진다. 이때, 어떤 정점 S로부터 다른 정점 E까지의 보행이 단 하나가 되도록 G의 모든 간선에 방향을 부여하여라. 그래프의 보행이란 같은 정점과 간선을 여러 번 방문할 수 있는 경로를 말한다.

 

입력

첫째 줄에 정점과 간선의 개수 N, M, 시작점과 도착점의 번호 S, E가 공백으로 구분되어 주어진다. 

둘째 줄부터 M개의 줄에 간선으로 연결된 두 정점의 번호 u, v가 공백으로 구분되어 주어진다. 

 

출력

모든 간선의 방향을 어떻게 정하여도 S에서 E까지의 보행이 단 하나가 되도록 만들 수 없다면 -1을 출력한다. 그렇지 않다면 모든 간선의 방향을 입력된 순서대로 한 줄에 출력한다. u -> v로 방향을 부여했다면 0, 반대라면 1을 출력한다.

조건을 만족하는 출력이 여러 가지인 경우 그중 아무거나 출력한다.

 

풀이

우선, s -> e의 최단경로를 하나 구한다. 

그 뒤, 경로상의 노드들에 순차적으로 가중치를 붙인다.

예를 들면, (1 -> 4 -> 3)의 경로가 있다고 하면, 1의 가중치는 1, 4의 가중치는 2, 3의 가중치는 3이다.

나머지 노드들의 가중치는 0으로 한다.

그 뒤, 각 m개의 간선들을 확인하면서, 더 가중치가 높은 쪽으로 간선들을 잇도록 구성하면, DAG꼴이 되면서, 다른 사이클 없이 s -> e가 유일하게 된다.

 

답이 -1인 경우는 한 가지 경우이다.

s -> e로 도달할 수 없는 경우이다.

 

코드

Go

package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
)

const INF int = 1000000000

var reader *bufio.Reader
var writer *bufio.Writer

type Item struct {
	Node int
	Dist int
}

type Edge struct {
	u   int
	v   int
	dir int
}

type Heap []Item

func (h Heap) Len() int           { return len(h) }
func (h Heap) Less(i, j int) bool { return h[i].Dist < h[j].Dist }
func (h Heap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *Heap) Push(x any) {
	*h = append(*h, x.(Item))
}

func (h *Heap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]

	return x
}

func main() {
	reader = bufio.NewReader(os.Stdin)
	writer = bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n, m, s, e int
	fmt.Fscan(reader, &n, &m, &s, &e)

	edges := make([]Edge, m)
	adj := make([][]int, n+1)
	dist := make([]int, n+1)
	prev := make([]int, n+1)
	nodeWeight := make([]int, n+1)
	for i := 0; i <= n; i++ {
		adj[i] = make([]int, 0)
		dist[i] = INF
		prev[i] = -1
		nodeWeight[i] = 0
	}
	for i := 0; i < m; i++ {
		var u, v int
		fmt.Fscan(reader, &u, &v)
		edges[i].u = u
		edges[i].v = v
		edges[i].dir = -1

		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)
	}

	pq := make(Heap, 0)
	heap.Init(&pq)
	dist[s] = 0

	heap.Push(&pq, Item{Node: s, Dist: 0})
	for pq.Len() > 0 {
		curr := heap.Pop(&pq).(Item)

		if curr.Dist > dist[curr.Node] {
			continue
		}

		for _, nextNode := range adj[curr.Node] {
			nextDist := curr.Dist + 1
			if nextDist < dist[nextNode] {
				dist[nextNode] = nextDist
				prev[nextNode] = curr.Node
				heap.Push(&pq, Item{Node: nextNode, Dist: nextDist})
			}
		}
	}

	if dist[e] == INF {
		fmt.Fprintln(writer, -1)
		return
	}

	trace := make([]int, 0)
	pos := e
	for prev[pos] != -1 {
		trace = append(trace, pos)
		pos = prev[pos]
	}
	trace = append(trace, pos)
	for i := 0; i < len(trace)/2; i++ {
		trace[i], trace[len(trace)-i-1] = trace[len(trace)-i-1], trace[i]
	}

	w := 1
	for i := 0; i < len(trace); i++ {
		nodeWeight[trace[i]] = w
		w++
	}

	for i := 0; i < m; i++ {
		if nodeWeight[edges[i].u] > nodeWeight[edges[i].v] {
			edges[i].dir = 1
		} else {
			edges[i].dir = 0
		}
		fmt.Fprintf(writer, "%d ", edges[i].dir)
	}

	fmt.Fprintln(writer)
}