<백준> 숫자고르기(Gold 5)
[백준]
2668번: 숫자고르기
세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절
www.acmicpc.net
[깃허브]
ForCodeKata/baekjoon 문제집/숫자고르기 at main · heesoo-park/ForCodeKata
Contribute to heesoo-park/ForCodeKata development by creating an account on GitHub.
github.com
정~~말 오랜만에 푸는 알고리즘 문제였다.
본가도 다녀오고 몸 상태도 회복하느라 손을 댈 수 없었던 나날이었다.
그래서 오늘 문제를 보고 기가 좀 죽었다.
하지만 생각보다는 머리가 굴러갔는데 어디까지 굴러갔냐면 DFS를 사용해서 사이클을 찾아야겠다는 것까지 도달했다.
그 이유는 첫번째 줄의 숫자와 아래 쪽의 숫자의 집합이 같아지려면 어쨌든 짝이 맞아야한다는 것고 짝이 맞기 위해서는 각각의 표 안에 숫자 간의 연결고리가 있어야한다고 생각했기 때문이다.
딱 여기까지는 생각을 했지만 막혔다.
그래서 좀 도움을 받았다.
그랬더니 생각보다 매우 간단하게 구현할 수 있었고 체크하는 방식에 대해서도 좀 새롭게 알게 되었다.
깊이 우선 탐색이기 때문에 첫번째 줄을 기준으로 사이클 비교를 하고 두번째 줄의 값으로 다음 깊이로 넘어가는 방식이었다.
여기서 DFS는 모든 배열 값에 대해서 출발을 하는데 이는 각각을 출발점으로 했을 때 사이클이 생기는 경우에 정답에 값을 추가하기 위해서다.
사이클이 생기면 그냥 한번에 다 사이클에 있는 숫자를 넣으면 되지 않나 했는데 그걸 저장하고 있을 배열이나 추가, 삭제 등의 관리까지 생각해보니 이 방법이 더 편리하게 생각됐다.
그리고 한 숫자에 대해 탐색이 끝나면 visited 배열을 초기화해준다.
해당 방법으로 작성한 코드는 다음과 같다.
import java.io.BufferedWriter
import java.io.OutputStreamWriter
val table = IntArray(101) { 0 }
val visited = BooleanArray(101) { false }
val answer = mutableListOf<Int>()
fun main() = with(System.`in`.bufferedReader()) {
val bw = BufferedWriter(OutputStreamWriter(System.out))
val size = readln().toInt()
repeat(size) {
table[it + 1] = readln().toInt()
}
for (i in 1..size) {
resetVisited()
dfs(i, i)
}
bw.write("${answer.size}\n")
answer.forEach {
bw.write("$it\n")
}
bw.flush()
bw.close()
}
fun dfs(cur: Int, start: Int) {
if (visited[cur]) {
if (start == cur) answer.add(cur)
return
}
visited[cur] = true
dfs(table[cur], start)
}
fun resetVisited() {
for (i in visited.indices) {
visited[i] = false
}
}
참고)