오늘은 나의 실패썰과 다른 분의 좋은 코드를 보며 공부한 나의 일기라고 할 수 있다. 나는 처음에 부분집합으로 해당 문제를 풀다가 '메모리 초과'가 떴었다. 그래서 내가 아직 풀기에는 어려운 문제라고 판단하여 다른 분의 코드를 보았다. 내가 참고한 블로그는 아래와 같다.
[백준-2668]-[DFS]-숫자고르기
문제링크 : https://www.acmicpc.net/problem/2668 이 문제는 사이클이 발생할 때 까지 DFS로 탐색을 진행하면 된다. 만약 사이클이 발생하지 않는다면 visited 정보를 초기화 해주고 사이클이 발생했다면 방
pangsblog.tistory.com
1. 문제출처
2668번: 숫자고르기
세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절
www.acmicpc.net
2. 설계
1) 실패한 설계
인덱스를 1~N개 고르는 경우를 따지고 싶었고, 순서는 중요하게 생각하지 않았기 때문에 부분 집합을 쓰고자 했다.
예를 들어 (1,2,3)을 뽑는 경우 (2,3,1)을 뽑는 경우는 조합이 같기 때문에 순서는 중요하게 생각하지 않았다.
이렇게 부분집합으로 조합을 뽑고, 뽑은 조합이 인덱스 조합과 일치하는지 확인해주었다.
그런데 이렇게 하면 메모리 초과가 나온다.
import java.util.Arrays;
import java.util.Scanner;
public class Main {
/**
* 인덱스 번호와 숫자의 조합이 맞는 최대 길이를 찾는 문제 => 부분집합
*/
static int[] nums;
static int[] sel;
static int N;
static int resultLen;
static int[] resultArr;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
// 초기화
nums = new int[N + 1];
sel = new int[N + 1];
resultArr = new int[N+1];
for (int i = 1; i <= N; i++) {
nums[i] = sc.nextInt();
}
// 입력받기 끝
powerset(1,0);
//결과 출력
System.out.println(resultLen);
Arrays.sort(resultArr);
for(int i=1;i<=N;i++) {
if(resultArr[i]!=0)System.out.println(resultArr[i]);
}
}
public static void powerset(int idx, int len) {
if (idx == N + 1) {
// 조합이 인덱스번호와 값이 맞는지 체크
// 맞으면 최대 길이 확인
if(check()) {
if(resultLen<len) {
resultLen = len;
for(int i=1;i<=N;i++) {
resultArr[i] = sel[i];
}
}
}
return;
}
sel[idx] = idx;// nums 배열의 인덱스 번호가 sel에 들어감
powerset(idx + 1, len + 1);//이 요소를 선택함
sel[idx] = 0;
powerset(idx+1, len);//이 요소를 선택하지 않음
}
// 조합 체크 함수
public static boolean check() {
//sel 값인 인덱스에 포함되는 nums배열의 값을 가져온다.
//카운팅 정렬
int[] countNums = new int[N+1];
int[] countSel = new int[N+1];
for(int i=1;i<=N;i++) {
countSel[sel[i]]++;
countNums[nums[sel[i]]]++;
}
//nums와 sel 카운팅 배열 비교
for(int i=1;i<=N;i++) {
if(countSel[i]!=countNums[i]) return false;
}
return true;
}
}
2) 참고한 설계
내가 참고한 블로그의 주인장님은 cycle을 이용했다.
만약 이러한 데이터가 있다고 해보자. (1번줄 : 인덱스번호 / 2번줄 : 값)
1번부터 7번까지 순환관계를 조사할 것이다.
1) (1번 인덱스, 처음 시작하는 인덱스, 길이)를 가지고 DFS를 진행한다. 즉, 처음엔 차례대로 (1, 1, 1)
2) 1번 인덱스를 방문한 적이 없다면, 방문처리를 해주고, 큐에 집어 넣는다.
3) 만약 처음 시작하는 인덱스값과 내가 다음에 가려고 하는 인덱스 값이 같으면 cycle이라고 본다.
- 예를들어 인덱스 5번의 경우이다. 처음시작하는 인덱스(5)와 다음 가려고 하는 인덱스(5)가 같다.
- 또한 1과 3의 관계이다. 처음 시작하는 인덱스(1)과 다음 가려고 하는 인덱스(3)는 같지 않으므로 방문처리 및 큐에 추가하고, 다음 턴으로 이동한다. 이 때 처음 시작하는 인덱스(1)과 다음 가려고 하는 인덱스(1)이 같으므로 cycle에 해당한다.
4) 만약 cycle이 아닌 경우 visited 배열의 해당 위치를 false로 처리해준다.
visited의 결과에 따라 번호를 순차적으로 출력해 줄 것이다. 위의 표를 예시로 들면 다음과 같다.
1턴 : 시작 인덱스 1
[visited]
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| T | F | T | F | F | F | F |
2턴 : 시작 인덱스 2
시작 인덱스(2)와 다음 가려고 하는 인덱스(1)은 같지 않고, 1은 이미 방문상태이므로 갈 수 없다. 이 때는 메인으로 다시 돌아와 큐에 넣은 요소들을 다시 FALSE 시킨다. (이 때 큐는 시작 인덱스가 바뀔 때마다 초기화 되므로 한 턴에 연관된 인덱스 번호만 들어가 있어서 사이클이 아닌 요소만 FALSE 시킬 수 있다.)
[visited]
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| T | F | T | F | F | F | F |
3턴 : 시작 인덱스 3
3은 이미 방문 처리된 인덱스이므로 스킵한다.
[visited]
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| T | F | T | F | F | F | F |
4턴 : 시작 인덱스 4
시작 인덱스(4)와 다음 가려고 하는 인덱스(5)은 같지 않기 때문에 다음 인덱스(5)로 향한다.
근데 다음 인덱스가 시작 인덱스(4)와 다음 가려고 하는 인덱스(5)가 같지 않기 때문에 다음 인덱스(5)로 향한다.
다음 DFS에서 이미 5는 방문처리된 상태이므로 FALSE 처리된다.
이때 다시 메인으로 돌아와 이번 턴에 큐에 넣은 요소들을 다시 FALSE시킨다. (이 때 큐는 시작 인덱스가 바뀔 때마다 초기화 되므로 한 턴에 연관된 인덱스 번호만 들어가 있어서 사이클이 아닌 요소만 FALSE 시킬 수 있다.)
[visited]
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| T | F | T | F | F | F | F |
5턴 : 시작 인덱스 5
시작 인덱스(5)와 다음 가려고 하는 인덱스(5)은 같기 때문에 TRUE를 리턴하고, visited를 true인 상태로 남겨둔다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| T | F | T | F | T | F | F |
6턴 : 시작 인덱스 6
시작 인덱스(6)와 다음 가려고 하는 인덱스(4)은 같지 않기 때문에 다음 인덱스(4)로 향한다.
근데 다음 인덱스가 시작 인덱스(6)와 다음 가려고 하는 인덱스(5)가 같지 않기 때문에 다음 인덱스(5)로 향한다.
다음 DFS에서 이미 5는 방문처리된 상태이므로 FALSE 처리된다.
이때 다시 메인으로 돌아와 이번 턴에 큐에 넣은 요소들을 다시 FALSE시킨다. (이 때 큐는 시작 인덱스가 바뀔 때마다 초기화 되므로 한 턴에 연관된 인덱스 번호만 들어가 있어서 사이클이 아닌 요소만 FALSE 시킬 수 있다.)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| T | F | T | F | T | F | F |
7턴 : 시작 인덱스 7
시작 인덱스(7)와 다음 가려고 하는 인덱스(6)은 같지 않기 때문에 다음 인덱스(6)로 향한다.
시작 인덱스(6)와 다음 가려고 하는 인덱스(4)은 같지 않기 때문에 다음 인덱스(4)로 향한다.
근데 다음 인덱스가 시작 인덱스(6)와 다음 가려고 하는 인덱스(5)가 같지 않기 때문에 다음 인덱스(5)로 향한다.
다음 DFS에서 이미 5는 방문처리된 상태이므로 FALSE 처리된다.
이때 다시 메인으로 돌아와 이번 턴에 큐에 넣은 요소들을 다시 FALSE시킨다. (이 때 큐는 시작 인덱스가 바뀔 때마다 초기화 되므로 한 턴에 연관된 인덱스 번호만 들어가 있어서 사이클이 아닌 요소만 FALSE 시킬 수 있다.)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| T | F | T | F | T | F | F |
그리하여 정답은 길이가 3이고, 조합은 T가 표시된 1, 3, 5가 되는 것이다.
3. 전체코드
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
/**
* 1. 1번 인덱스부터 조사를 시작한다.
* 2. 싸이클이 생기면 선택할 수 있다는 의미이다.
* 3. 싸이클이 생기면 visited = true로 바꾼다.
* 4. 싸이클이 안생기면 visited = false로 초기화한다.
*/
public class Main{
static int N;
static int[] arr;
static int resultLen;
static boolean[] visited;// 결국 방문한 인덱스만 결과로 뽑아내면 된다.
static PriorityQueue<Integer> recur;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
// 초기화
arr = new int[N + 1];
visited = new boolean[N + 1];
for (int i = 1; i <= N; i++) {
arr[i] = sc.nextInt();
}
// 데이터 입력받기 끝
// 인덱스 하나씩 돌면서 사이클이 생기는지 확인할 것임
for (int i = 1; i <= N; i++) {
recur = new PriorityQueue<>();// 매 순환 체크 마다 새로운 큐
// 순환하지 않는다면 visited=false처리 -> 결과반영 x
if (!DFS(i, i, 1)) {
while (!recur.isEmpty()) {
int target = recur.poll();
visited[target] = false;
}
}
}
// 결과 출력
System.out.println(resultLen);
for (int i = 1; i <= N; i++) {
if (visited[i])
System.out.println(i);
}
}
public static boolean DFS(int index, int startIdx, int len) {
//처음에 들어오는것도 방문했으면 넣지 않기
if(!visited[index]) {
recur.add(index);
visited[index] = true;
}
// 순환을 돌아 시작점으로 다시 돌아왔다면 사이클이 완성된 것이다.
if (arr[index] == startIdx) {
resultLen += len;
return true;
}
// 순환을 돌아야 한다면 dfs속으로!
if (!visited[arr[index]])
return DFS(arr[index], startIdx, len + 1);
return false;
}
}
내가 절대 생각할 수 없었던 설계여서 다시 공부하고 기록할 겸 적었다.
-끝-
'알고리즘 > 백준' 카테고리의 다른 글
| [너비우선탐색] 백준 5427번 불 - JAVA (2) | 2023.04.09 |
|---|---|
| [깊이/너비우선탐색] 백준 1260번 DFS와 BFS - JAVA (0) | 2023.04.08 |
| [너비우선탐색] 백준 10026번 적록색약 - JAVA (0) | 2023.04.05 |
| [브루트포스 알고리즘] 2851번 슈퍼 마리오 (0) | 2023.02.14 |
| [브루트포스 알고리즘] 2798번 블랙잭 (0) | 2023.02.14 |
