개발 다이어리

컴포지트 패턴을 공부하다. 갑자기 파일 시스템이랑 비슷한 것 같아서 연습해봄.

컴포지트 패턴이란

개체를 트리 구조로 구성하여 부분-전체 계층을 나타냅니다.

이 패턴을 사용하면 클라이언트가 개별 개체와 개체 구성(컴포지트)을 동일하게 처리할 수 있습니다.

구성요소 

component

컴포지션의 모든 개체에 대한 기본 인터페이스입니다. 하위 조합을 관리하는 공통 메서드가 있는 인터페이스 또는 추상 클래스여야 합니다.

leaf

자식이 없는 노드를 의미합니다.

composite

자식이 있는 노드를 의미합니다. 이때 다른 composite도 포함될 수 있습니다.

코드 예시

import java.util.ArrayList;
import java.util.List;

public class SimpleComposite {
	
	abstract static class Component{
		String name;
		
		void addComponent(Component component) {
			throw new UnsupportedOperationException();
		}
		abstract void print();
	}
	
	static class Leaf extends Component{
		String name;
		
		public Leaf(String name) {
			this.name = name;
		}



		void print() {
			System.out.println("[Leaf]"+name);
		}
	}
	static class Composite extends Component{
		String name;
		List<Component> components = new ArrayList<>();
		
		public Composite(String name) {
			this.name = name;
		}
		@Override
		void addComponent(Component component) {
			components.add(component);
		}
		void print() {
			System.out.println("[Composite]"+name);
			for(Component component : components) {
				component.print();
			}
		}
	}
	
	public static void main(String[] args) {
		Component root = new Composite("회장님");
		root.addComponent(new Leaf("홍 비서"));
		root.addComponent(new Leaf("박 비서"));
		
		Component composite1 = new Composite("전무");
		composite1.addComponent(new Leaf("김 비서"));
		Component composite2 = new Composite("이사");
		composite2.addComponent(new Leaf("이 비서"));
		
		root.addComponent(composite1);
		root.addComponent(composite2);
		
		Component composite1_1 = new Composite("영업팀");
		composite1_1.addComponent(new Leaf("임꺽정 팀장"));
		
		Component composite2_1 = new Composite("기획팀");
		composite2_1.addComponent(new Leaf("홍길동 팀장"));
		
		composite1.addComponent(composite1_1);
		composite2.addComponent(composite2_1);
		
		
		root.print();
	}
	
}

[Composite]회장님
[Leaf]홍 비서
[Leaf]박 비서
[Composite]전무
[Leaf]김 비서
[Composite]영업팀
[Leaf]임꺽정 팀장
[Composite]이사
[Leaf]이 비서
[Composite]기획팀
[Leaf]홍길동 팀장

간단한 조직도를 만들어봤다. 

만든 김에 트리처럼 레벨로 출력해보기

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class SimpleComposite {
	
	abstract static class Component{
		
		abstract String getName();
		abstract boolean isLeaf();
		void addComponent(Component component) {
			throw new UnsupportedOperationException();
		}
		List<Component> getComponents(){
			throw new UnsupportedOperationException();
		}
		
		abstract void print();
	}
	
	static class Leaf extends Component{
		String name;
		public String getName() {
			return name;
		}
		boolean isLeaf() {
			return true;
		}
		public Leaf(String name) {
			this.name = name;
		}


		void print() {
			System.out.println("[Leaf]"+name);
		}
	}
	static class Composite extends Component{
		String name;
		List<Component> components = new ArrayList<>();
		
		public Composite(String name) {
			this.name = name;
		}
		public String getName() {
			return name;
		}
		boolean isLeaf() {
			return false;
		}
		void addComponent(Component component) {
			components.add(component);
		}
		public List<Component> getComponents() {
			return components;
		}
		void print() {
			System.out.println("[Composite]"+name);
			for(Component component : components) {
				component.print();
			}
		}
	}
	
	public static void main(String[] args) {
		Component root = new Composite("회장님");
		root.addComponent(new Leaf("홍 비서"));
		root.addComponent(new Leaf("박 비서"));
		
		Component composite1 = new Composite("전무");
		composite1.addComponent(new Leaf("김 비서"));
		Component composite2 = new Composite("이사");
		composite2.addComponent(new Leaf("이 비서"));
		
		root.addComponent(composite1);
		root.addComponent(composite2);
		
		Component composite1_1 = new Composite("영업팀");
		composite1_1.addComponent(new Leaf("임꺽정 팀장"));
		
		Component composite2_1 = new Composite("기획팀");
		composite2_1.addComponent(new Leaf("홍길동 팀장"));
		
		composite1.addComponent(composite1_1);
		composite2.addComponent(composite2_1);
		
		
//		root.print();
		BFS(root);
	}
	
	static void BFS(Component root) {
		Queue<Component> components = new LinkedList<>();
		components.offer(root);
		int lv = 1;
		
		while(!components.isEmpty()) {
			int len = components.size();
			System.out.print(lv++ +" ");
			for(int i=0;i<len;i++) {
				Component compo = components.poll();
				System.out.print(compo.getName()+" ");
				if(!compo.isLeaf()) {
					for(Component com : compo.getComponents()) {
						components.add(com);
					}
				}
			}
			System.out.println();
		}
	}
	
}

1 회장님 
2 홍 비서 박 비서 전무 이사 
3 김 비서 영업팀 이 비서 기획팀 
4 임꺽정 팀장 홍길동 팀장

코드

package algorithm07;

import java.util.*;

class Node2{ 
    int data; 
    Node2 lt, rt; 
    public Node2(int val) { 
        data=val; 
        lt=rt=null; 
    } 
} 
  
public class BFS레벨탐색{ 
    Node2 root; 
    public void BFS(Node2 root){ 
        Queue<Node2> Q=new LinkedList<>();
        Q.add(root);
        int L=0;
        while(!Q.isEmpty()){
            // for문에서 Q.size()를 조건식으로 주면 메서드 이기 때문에 상태 변화에 따라 값이 변동된다.
            int len = Q.size(); 
            System.out.print(L+" : ");
            for(int i=0; i<len; i++){
                Node2 cur = Q.poll();
                System.out.print(cur.data+" ");
                if(cur.lt!=null) Q.add(cur.lt);
                if(cur.rt!=null) Q.add(cur.rt);
            }
            L++;
            System.out.println();
        }
    } 
    
    public static void main(String args[]) { 
        BFS레벨탐색 tree=new BFS레벨탐색(); 
        tree.root=new Node2(1); 
        tree.root.lt=new Node2(2); 
        tree.root.rt=new Node2(3); 
        tree.root.lt.lt=new Node2(4); 
        tree.root.lt.rt=new Node2(5); 
        tree.root.rt.lt=new Node2(6); 
        tree.root.rt.rt=new Node2(7);
        tree.BFS(tree.root); 
    } 
}

결과

0 : 1 
1 : 2 3 
2 : 4 5 6 7

L 을 기준으로 큐 자료구조를 사용하여 탐색해 나아간다.

DFS와 달리 큐를 사용해 탐색해 나아가므로 재귀호출을 하지 않는다.(큐 특징, FIFO, 선입선출)

위 예제에서 int size = Q.size(); 따로 변수로 빼서 사용한 이유는 Q.size()가 메서드이기 때문이다.

Q가 poll()한다면 Q의 상태가 변화했으므로 size()메서드도 변동된다. 

따라서 L별 최초 너비 탐색 직전에 size() 상태를 저장해 놓고 같은 L에 속하는 모든 노드를 탐색하게 된다.

왜 큐 자료구조와 size() 메서드를 상태 값을 따로 로컬 변수로 저장해 반복문을 더 사용하는지 알아보자

현재 데이터 구조는 위와 같다.

L 이 0일 때는 문제 없어보인다.

L이 1일때 Q는 [2,3]을 저장하고 있고, 우리가 원하는 것은 이 과정에서 다음 탐색 L 2 노드데이터인 4,5는 다음에 처리하고 싶을 것이다.

그렇기에 L 값이 변하고 최초 너비 탐색 시 size()값을 저장하여 사용하는 것이다.

또한 큐 특성상 선입선출이므로 앞자리부터 사용하기에 큐를 사용하는 것이다.

엄밀히 말하면 선입선출은 배열을 기반으로 한 ArrayList로 사용은 가능하지만 빈 공간 메꾸는 작업으로 엄청난 비효율이 발생하게 된다. 따라서 LinkedList를 사용한 것이다.

L1의 노트 3 까지 다 탐색한다면 비로소 for문 조건식이 false가 되며, 다음 L++ 너비를 탐색하게 된다.