oVeron

1.기존 '17412번: 도시 왕복하기 1' 문제와 비슷하지만, 두 가지가 다르다.- 간선이 단방향에서 양방향으로 바뀌었다.- 본래는 간선의 중복 방문이 불가능했지만, 여기서는 정점의 중복 방문이 불가능하다. 정점의 중복 방문을 어떻게 처리해야 할까? 정점을 용량이 1인 간선으로 만들어 버리면 된다. 예를 들어 정점 \(u\)를 간선으로 만들기 위해서는 \(u+N\)이라는 새로운 정점을 만들고 두 정점을 간선 (\(u, u+N)\)로 이으면 된다. \(u\)와 연결된 정점들은 전부 \(u+N\)에 이어주면 된다. 이렇게 하면 \(u+N\)을 단 한 번만 방문할 수밖게 없게 되므로 정점의 중복 방문을 해결할 수 있다. 간선이 양방향이기에, 간선의 용량 초기화를 쉽게 하기 위해 인접 행렬을 사용하였다.\(s..

알고리즘/baekjoon 2024. 6. 30. 14:14