[BOJ] 2668 - 숫자 고르기


BOJ 2668 - 숫자고르기

풀고보니 간단한 DFS 문제였다.

2~3주 전쯤에 봤을 땐 좀 어려워보이니 나중에 풀어보자고 킵했던 문제인데, 생각보다 금방 풀었고 다른 사람들 풀이도 간결해서 놀랬다.

나는 조금 복잡하게 접근해서 풀었는데.. 일단 내 방법을 써보려고 한다.

풀이

일단 이 문제는 세로 두줄짜리 배열에서 사이클을 찾는 문제이다.

뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 아랫 줄에 있는 정수들이 이루는 집합이 일치해야하는데 이 조건대로 선을 그어보면 사이클이 생긴다는걸 알 수 있다.

boj-2668

여기서 한 가지 사실을 더 알 수 있는데, ‘둘째 줄에 존재하지 않는 숫자는 고려할 필요가 없다’이다.

그래서 사이클이 가능한 숫자 리스트를 별도 배열로 만들어서 관리하고, 이 숫자에 대해서만 DFS를 돌렸다.

이 문제에서 DFS는 재귀로 구현하는게 편하고, 처음 시작할때의 숫자로 되돌아왔을 때 ArrayList에 사이클에 해당하는 숫자들 넣어주면 된다.

나는 편의상 스택을 같이 활용했는데, 다른 사람 풀이를 봐도 잘 이해가 안되는 경우 스택 사용을 추천한다.

소스 코드