카테고리 구현방법 (백트레킹 알고리즘 사용)

 

카테고리는 조직도와 같이 부모-자식 관계를 가지고 있으며 항목들을 일목요연하게 보여줄 수 있는 방법이다. 하지만 부모-자식 관계는 데이터베이스에 명확하게 표현할 수 있어도 프리젠테이션 영역에서 표현하기가 어렵다. 따라서 보통 카테고리를 표시하기 위해 '01/01/01' 카테고리의 순서와 깊이를 표시하는 값을 데이터베이스에 저장하여 카테고리를 구현한다. 대부분의 인터넷 검색이 이런 구현을 설명하고 있다.

 

하지만 '01/01/01' 이런 방식은 카테고리 생성에 99개로 제한되어 있으며, 또한 카테고리 삽입시 카테고리 표시값을 알아내기 위한 쿼리문이 복잡하며 문자열 파싱을 통해 카테고리의 깊이와 순서를 알아내야 하는 단점이 있다. 이에 데이터베이스 스키마를 간단하게 부모-자식 관계로만 유지하고 표현부는 백트레킹 알고리즘을 사용하여 구현하는 방법으로 카테고리를 구현하였다.

 

백트레킹 알고리즘은 회귀검사로 재귀함수를 사용하여 경로를 저장하는 방법이다.

 

 

1. 데이터베이스 스키마

 

카테고리_ID  : 카테고리의 고유한 인덱스값

카테고리_레벨 : 카테고리의 레벨을 표시(루트는 1, 자식은 1씩 증가) 

카테고리_부모값 : 상위 카테고리의 인덱스값 

 

카테고리_이름 : 카테고리의 이름

 

여기에서 중요한 값은 ID, 레벨, 부모값이다. ID는 고유한 값으로 auto_increment 를 지정해도 무관하다. 또한, 레벨을 페이지 상에서 표시하기 위해 반드시 필요한 값이고 카테고리는 부모값을 가지고 있다. 데이터베이스에 저장되는 데이터는 다음과 같다.

 

카테고리_ID | 카테고리_레벨 | 카테고리_부모값 | 카테고리_이름

100             |                   1   |                       1  |               본사     // 루트 카테고리입니다.

101             |                   2   |                   100  |         청주지점     // 루트 > 청주지점

102             |                   2   |                   100  |         대전지점     // 루트 > 대전지점

103             |                   3   |                   101  |         청주1팀      // 루트 > 청주지점 > 청주1팀

104             |                   3   |                   101  |         청주2팀      // 루트 > 청주지점 > 청주2팀

105             |                   3   |                   102  |         대전1팀      // 루트 > 대전지점 > 대전1팀  

 

 위와 같이 테이블에 데이터가 저장될 것다. 이제 백트래킹 알고리즘을 사용하여 순서대로 출력하는 방법이다.

 

 

2. 루트 카테고리를 검색하는 메소드

 

// 테이블의 레벨 1값을 검색하여 값을 ArrayList<Integer>로 반환

public ArrayList<Integer> getRoots(Connection conn) {

    PreparedStatement pst = null;
    ResultSet rs = null;
  
    try {
        String sql = "SELECT departmentID FROM "+TABLE+" WHERE level = 1";
        pst = conn.prepareStatement(sql);
        rs = pst.executeQuery();              
        ArrayList<Integer> list = new ArrayList<Integer>();   

        while( rs.next() ){
            list.add(rs.getInt(1));
        }

        return list;

    } catch(Exception e) {
        e.printStackTrace();
        return null;
    } finally {
       JdbcConnector.release(pst);
       JdbcConnector.release(rs);
    }
}

 

 

3. 루트 카테고리를 기준으로 자식 카테고리 리스트를 백트레킹 알고리즘을 사용하여 저장하기

 

// 카테고리_ID 값을 받아 자식들을 ArrayList<DepartmentVO> 에 순서대로 저장 

public void getChildList(Connection conn, int departmentID, ArrayList<DepartmentVO> list) {

    PreparedStatement pst = null;
    ResultSet rs = null;
  
    try {
        String sql = "SELECT * FROM "+TABLE+" WHERE departmentID = ?";
        pst = conn.prepareStatement(sql);
        pst.setInt(1, departmentID);
        rs = pst.executeQuery();
        

        // 부서의 데이터를 저장합니다.
        if ( rs.next() ) {
            DepartmentVO department = new DepartmentVO();
            setDepartment(rs, department);
            list.add( department );
        }
   

       // 자식들을 검색합니다.
        sql = "SELECT departmentID FROM "+TABLE+" WHERE parent = ?";
        pst = conn.prepareStatement(sql);
        pst.setInt(1, departmentID);
        rs = pst.executeQuery();
   
        while ( rs.next() ) {
            int parent = rs.getInt(1);
            getChildList(conn, parent, list);   // 재귀함수를 사용하여 위의 과정을 반복(백트레킹)
        }
   
        return ;
   
    } catch(Exception e) {
        e.printStackTrace();
    } finally {
        JdbcConnector.release(rs);
        JdbcConnector.release(pst);
    }

}

 

3번의 메소드는 재귀함수를 사용하여 카테고리를 저장한 후 자식 카테고리가 있으면 다시 함수를 호출하여 자식 카테고리를 저장하고 자식-자식 카테고리를 검색하고 있다면 다시 함수를 호출하여 자식-자식 카테고리를 저장하고 자식-자식-자식 카테고리를 검색하는 반복 작업을 계속해서 수행한다.

 

즉, 다음과 같은 과정을 수행한다.

 

루트부서ID 입력 → 루트 부서ID의 데이터 저장 → 루트 부서의 자식 부서 검색 → 자식부서의 수만큼 반복 → 첫번째 자식의 부서ID를 가져와 다시 함수(재귀함수) 호출

 

위의 과정을 거치면서 루트 - 첫번째 자식 - 자식의 첫번째 자식 - ... 이런 방법으로 첫번째부터 순서대로 ArrayList 에 저장을 한다. 자식이 없다면 위의 단계를 거쳐 모든 자식들을 방문한 후 함수는 종료된다.

 

 

4. 위의 코드를 합쳐 루트를 기준으로 모든 카테고리를 검색하여 ArrayList 객체로 반환하는 메소드

 

public ArrayList<DepartmentVO> getList(Connection conn) {

    ArrayList<DepartmentVO> childList = new ArrayList<DepartmentVO>();
    PreparedStatement pst = null;
    ResultSet rs = null;
  
    try {
        ArrayList<Integer> rootList = new ArrayList<Integer>();
        rootList = getRoots(conn);   // 루트 리스트를 가져옴

        // 가져온 루트 리스트만큼 반복수행
        for ( int i = 0 ; i < rootList.size() ; i++ ) {
            int departmentID = rootList.get(i);    
            getChildList(conn, departmentID, childList);  // 루트의 자식을 가져옴
        }
   
        return childList;
    } catch(Exception e){
        e.printStackTrace();
        return null;
    } finally {
        JdbcConnector.release(rs);
        JdbcConnector.release(pst);
    }
}

 

 

위의 getList() 메소드를 실행하여 얻은 결과

 

이와 같은 방법은 베이터베이스의 테이블은 부모-자식 관계를 이용하고 표현할 때만 재귀함수를 사용한 백크레킹 검색을 하기 때문에 카테고리가 몇 건이건 컴퓨터의 자원이 할달할 수 있을 만큼 카테고리를 생성하거나 자식 카테고리를 늘릴 수 있다.