[백트래킹/자바] 코드트리 IL. 겹치지 않게 선분 고르기

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 해석

이 문제는 선분들의 조합을 완전 탐색하여, 겹치지 않는 가장 많은 선분 선택 조합을 구하는 문제이다. 따라서 백트래킹을 이용하여 풀어낼 수 있다.

 

문제 풀이

[실패] 처음 떠올린 로직은 다음과 같다. 재귀 과정에서 앞뒤로 for loop을 활용하여 선분들을 수직선 상에 추가해주고 초기화하는 로직을 배치해 주었다.

package 코드트리.완전탐색.백트래킹;

import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
import java.io.*;
import java.util.*;

public class 겹치지않게_선분고르기 {
    private static class Line {
        private int a;
        private int b;

        public int getA() {
            return this.a;
        }

        public int getB() {
            return this.b;
        }

        public Line(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    private static int n, size = 0;
    private static boolean stop = false;
    private static int[] arr;
    private static Map<Integer, Line> m = new HashMap<>();


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        arr = new int[1000];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            Line l = new Line(a, b);
            m.put(i, l);
        }
        boolean flag = true;
        for (int i = n; i > 0; i--) {
            // combination
            go(i);
            if (stop == true) {
                System.out.println(i);
                flag = false;
                break;
            }
        }
        if (flag) {
            System.out.println(0);
        }
    }

    public static void go(int k) {
        for (int i = 0; i < n; i++) {
            Line line = m.get(i);
            int a = line.getA();
            int b = line.getB();

            for (int j = a; j <= b; j++) {
                arr[j]++;
                size++;
            }
            if (size == k+1) {
                return;
            }
            go(k);

            for (int j = a; j <= b; j++) {
                arr[j]--;
                size--;
            }
        }
    }


}

위 로직은 stackoverflow error를 받았다. 즉, 재귀 구현이 올바르게 되지 않아 탈출을 하지 못하고 있는 것이다. 따라서 설계를 바꿔야 한다.

 

[성공]

• 재귀 구간 쯤에서는 간단하게 조합을 하는 로직만 넣어주고, 그 조합이 유효한지는 모든 조합이 완성되었을 탈출 직전에 검사하는 것으로 바꾸었다.
• 재귀가 끝날 때 다시 돌아야 하는 경우에는, 수직선(arr)을 초기화 하는 것 또한 중요한 수정 포인트였다.
• (매번 실수하지만,) x가 1000까지이므로 수직선은 1001의 사이즈를 가져야 한다.

package 코드트리.완전탐색.백트래킹;

import java.io.*;
import java.util.*;

public class 겹치지않게_선분고르기 {
    private static class Line {
        private int a;
        private int b;

        public int getA() {
            return this.a;
        }

        public int getB() {
            return this.b;
        }

        public Line(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }
    private static final int X_RANGE = 1001;

    private static int n;
    private static int[] arr = new int[X_RANGE];
    private static Map<Integer, Line> m = new HashMap<>();
    private static boolean stop = false;

    private static List<Line> li = new ArrayList<>();


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            Line l = new Line(a, b);
            m.put(i, l);
        }

        for (int i = n; i > 0 ; i--) {
            // i : 몇 개의 라인을 고를 것인가?
            arr = new int[X_RANGE];
            go(i, 0);
        }
        if (!stop) {
            System.out.println(0);
        }

        /*
        * 몇 개의 라인을 고를건지 for loop으로 완전탐색
        * */

        /*
        * 골랐으면 재귀 깊이가 그 정도에서 멈출 수 있게 함
        * */

        /*
        * 정해졌으면 재귀를 돌려서 line 조합을 선정 -> 각 조합에 대한 정답 검사를 탈출 조건에서 수행.
        * */



    }

    public static void go(int i, int j) {
        if (stop) {
            return;
        }
        if (li.size() == i) {
            if (isDistinct(li)) {
                System.out.println(i);
                stop = true;
            }
            arr = new int[X_RANGE];
            return;
        }

        for (int k = j; k < n; k++) {
            li.add(m.get(k));
            go(i, ++j);
            li.remove(li.size() - 1);
        }
    }

    public static boolean isDistinct(List<Line> li) {
        for (Line line : li) {
            int a = line.getA();
            int b = line.getB();
            for (int i = a; i <= b; i++) {
                arr[i] += 1;
            }
        }
        for (int i : arr) {
            if (i > 1) {
                return false;
            }
        }
        return true;
    }


}