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

 

컴포지트 패턴이란

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


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

 

구성요소 

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 임꺽정 팀장 홍길동 팀장

 

 

 

 

 

 

 

 

 

'개발 > 자바(JAVA)' 카테고리의 다른 글

SuperTypeToken  (0) 2023.06.29
컴포지트 패턴 연습 - 2  (0) 2023.04.16
기본형 배열 List로 변환하기  (0) 2023.03.10
객체 지향 - 6  (0) 2023.02.03
객체 지향 - 5  (0) 2023.02.01

코드


import java.util.LinkedList;
import java.util.Queue;

class 섬나라아일랜드BFS {
	static int answer=0, n;
	static int[] dx={-1, -1, 0, 1, 1, 1 , 0 , -1};
	static int[] dy={0 , 1 , 1, 1, 0, -1, -1, -1};
	static Queue<Point> q = new LinkedList<섬나라아일랜드BFS.Point>();
	
	
	static void BFS(int[][] board,int x, int y) {
		
		q.offer(new Point(x, y));
		while(!q.isEmpty()) {
			int size = q.size();
			for (int i = 0; i < size; i++) {
				Point p = q.poll();
				for (int j = 0; j < dx.length; j++) {
					int nx = p.x+dx[j];
					int ny = p.y+dy[j];
					if(nx>=0&&nx<n && ny>=0&&ny<n && board[nx][ny]==1) {
						board[nx][ny] = 99;
						q.offer(new Point(nx, ny));
					}
				}
			}
		}
		
		
		for (int i = 0; i < dx.length; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx>=0 && nx<n &&ny >=0 &&ny <n &&board[nx][ny]==1 ) {
				board[nx][ny] = 99;
			}
			
		}
	}
	public void solution(int[][] board){
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if(board[i][j]==1) {
					answer++;
					board[i][j] = 99;
					BFS(board, i, j);
					
					System.out.println("==="+answer+"번 섬지우기===");
					for(int[] a : board) {
						for(int b : a) {
							System.out.printf("%2s ",b);
						}
						System.out.println();
					}
					System.out.println();
				}
			}
		}
	}
	static  class Point{
		int x,y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args){
		섬나라아일랜드BFS T = new 섬나라아일랜드BFS();
		int[][] arr=
				{{1, 1, 0, 0, 0, 1, 0}
				,{0, 1, 1, 0, 1, 1, 0}
				,{0, 1, 0, 0, 0, 0, 0}
				,{0, 0, 0, 1, 0, 1, 1}
				,{1, 1, 0, 1, 1, 0, 0}
				,{1, 0, 0, 0, 1, 0, 0}
				,{1, 0, 1, 0, 1, 0, 0}};
		
		
		n= arr.length;
		T.solution(arr);
		System.out.println(answer);
	}
}

결과

===1번 섬지우기===
99 99  0  0  0  1  0 
 0 99 99  0  1  1  0 
 0 99  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===2번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===3번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
 1  1  0 99 99  0  0 
 1  0  0  0 99  0  0 
 1  0  1  0 99  0  0 

===4번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
99 99  0 99 99  0  0 
99  0  0  0 99  0  0 
99  0  1  0 99  0  0 

===5번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
99 99  0 99 99  0  0 
99  0  0  0 99  0  0 
99  0 99  0 99  0  0 

5

단순히 DFS=>BFS로 해결한 코드

'자료구조&알고리즘 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비' 카테고리의 다른 글

씨름선수  (0) 2023.04.07
피자배달거리DFS  (0) 2023.04.05
섬나라아일랜드  (0) 2023.04.01
토마토BFS활용  (0) 2023.03.30
미로의차단거리통로BFS  (0) 2023.03.28

코드


import java.util.*;

class Main {
	static int[] dx={-1, 0, 1, 0};
	static int[] dy={0, 1, 0, -1};
	static int[][] board, dis;
	static int n, m;
	static Queue<Point> Q=new LinkedList<>();
	
	static void BFS2(){
		
		while(!Q.isEmpty()) {
			int len = Q.size();
			for (int i = 0; i < len; i++) {
				Point p = Q.poll();
				
				for (int j = 0; j < dx.length; j++) {
					int nx = p.x+dx[j];
					int ny = p.y+dy[j];
					
					if(nx>=0&&nx<n  && ny>=0&&ny<m && board[nx][ny]==0) {
						board[nx][ny]= 1;
						Q.offer(new Point(nx, ny));
						dis[nx][ny] =dis[p.x][p.y]+1;
					}
				}
			}
		}
	}
	
	public static void main(String[] args){
		m=6; //가로 크기
		n=4; //세로 크기
		board=new int[n][m];
		dis=new int[n][m];
		
		int[][] tmp = 
			{{0, 0, -1, 0, 0, 0}
			,{0, 0, 1, 0, -1, 0}
			,{0, 0, -1, 0, 0, 0}
			,{0, 0, 0, 0, -1, 1}};
		
		board = tmp.clone();
		
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				if(board[i][j]==1) Q.offer(new Point(i, j));
				//출발점이 여러개라 미리 넣어둠
			}
		}
		
		BFS2();
		
		//0이 하나라도 존재하면 토마토가 모두 익지 못하는 상황
		long count = Arrays.stream(board)
		      .flatMapToInt(Arrays::stream)
		      .filter(value->value==0)
		      .count();
		if(count>0) System.out.println(-1);
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if(board[i][j]==0) {
					System.out.println(-1);
					return;
				}
			}
		}
		
		// 만약 처음부터 모두 익어있다면 자연스럽게 0 출력될 것
		int value = Integer.MIN_VALUE;
		for (int i = 0; i < dis.length; i++) {
			for (int j = 0; j < dis[i].length; j++) {
				value = Math.max(value, dis[i][j]);
			}
		}
		System.out.println(value);
		for (int[] arr : dis) {
			for (int val : arr) {
				System.out.printf("%2s ",val);
			}
			System.out.println();
		}
		
	}
	static class Point{
		public int x, y;
		Point(int x, int y){
			this.x=x;
			this.y=y;
		}
	}
}

결과

4
 3  2  0  2  3  3 
 2  1  0  1  0  2 
 3  2  0  2  2  1 
 4  3  4  3  0  0

전부 똑같다. 다른 점은 시작점이 여러 개라면 미리 큐에 넣어둔다. 그 차이가 전부다.

문제에서 시작점인 것에 위치값을 준게 아니라 미리 board[x][y] = 1 같이 넣어뒀기에 시작 시 출발 값에 1을 체크할 필요 없다.

'자료구조&알고리즘 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비' 카테고리의 다른 글

섬나라아일랜드BFS  (0) 2023.04.03
섬나라아일랜드  (0) 2023.04.01
미로의차단거리통로BFS  (0) 2023.03.28
미로탐색DFS  (0) 2023.03.26
조합구하기  (0) 2023.03.24

코드


import java.util.*;

class 미로의차단거리통로BFS {
	static int[] dx={-1, 0, 1, 0};
	static int[] dy={0, 1, 0, -1};
	static int[][] board, dis;
	static int cnt = 0;
	static int answer = Integer.MAX_VALUE;
	
	static void BFS(int x, int y){
		Queue<Point> Q=new LinkedList<>();
		Q.offer(new Point(x, y));
		board[x][y]=1;
		while(!Q.isEmpty()){
			Point tmp=Q.poll();
			for(int i=0; i<4; i++){
				int nx=tmp.x+dx[i];
				int ny=tmp.y+dy[i];
				if(nx>=1 && nx<=7 && ny>=1 && ny<=7 && board[nx][ny]==0){
					board[nx][ny]=1;
					Q.offer(new Point(nx, ny));
					dis[nx][ny]=dis[tmp.x][tmp.y]+1;
				}
			}
		}	
	}
	
	
	static void BFS3(int x,int y) {
		Queue<Point> q = new LinkedList<Point>();
		q.offer(new Point(x, y));
		board[x][y]=1;
		while(!q.isEmpty()) {
			int size = q.size();
			//Q 순회용 
			for (int i = 0; i < size; i++) {
				Point p = q.poll();
				// Q 요소의 다음 갈 곳 순회용
				for (int j = 0; j < dx.length; j++) {
					int nx = p.x+dx[j]; //다음갈 곳
					int ny = p.y+dy[j];
					if(nx>=1&&nx<=7 && ny>=1&&ny<=7 &&board[nx][ny]==0) {
						board[nx][ny] = 1;
						dis[nx][ny] = dis[p.x][p.y]+1;
						q.offer(new Point(nx, ny));
					}
				}
			}
		}
	}
	
	public static void main(String[] args){
		dis=new int[8][8];
		//인덱스 [0][n], [n][0]은 버리는 공간, 1부터 시작을 위함
		int[][] arr = 
			{ {0, 0, 0, 0, 0, 0, 0, 0}
			/*-----------------------*/
			, {0,/**/ 0, 0, 0, 0, 0, 0, 0}
			, {0,/**/ 0, 1, 1, 1, 1, 1, 0}
			, {0,/**/ 0, 0, 0, 1, 0, 0, 0}
			, {0,/**/ 1, 1, 0, 1, 0, 1, 1}
			, {0,/**/ 1, 1, 0, 0, 0, 0, 1}
			, {0,/**/ 1, 1, 0, 1, 1, 0, 0}
			, {0,/**/ 1, 0, 0, 0, 0, 0, 0} };
		
		board = arr.clone();
		
		BFS3(1, 1);
		for(int[] y : dis) {
			for (int x : y) {
				System.out.printf("%2s ", x);
			}
			System.out.println();
		}
		if(dis[7][7]==0) System.out.println(-1); //목적지 도달 불가
		else System.out.println(dis[7][7]);
	}
}

class Point{
	public int x, y;
	Point(int x, int y){
		this.x=x;
		this.y=y;
	}
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return x+":"+y;
	}
}

결과

 0  0  0  0  0  0  0  0 
 0  0  1  2  3  4  5  6 
 0  1  0  0  0  0  0  7 
 0  2  3  4  0 10  9  8 
 0  0  0  5  0  9  0  0 
 0  0  0  6  7  8  9  0 
 0  0  0  7  0  0 10 11 
 0  0  9  8  9 10 11 12 
12

최단 거리는 DFS가 아닌 BFS를 쓰는 것이 맞다. 

DFS도 가능하지만 모든 경우의 수를 끝까지 탐색해야만 최단 거리임을 보증할 수 있다.

반면에 BFS는 가장 먼저 발견한 것이 최단거리임을 보장한다.

'자료구조&알고리즘 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비' 카테고리의 다른 글

섬나라아일랜드  (0) 2023.04.01
토마토BFS활용  (0) 2023.03.30
미로탐색DFS  (0) 2023.03.26
조합구하기  (0) 2023.03.24
수열추측하기  (0) 2023.03.22

코드


//각 정점으로 가는 최소 이동 간선수
class 그래프최단거리BFS {
    static int n, m, answer=0;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    static int[] ch, dis;
    
    public void BFS2(int v){
        LinkedList<Integer> q = new LinkedList<Integer>();
        ch[v] = 1;
        dis[v] = 0;
        
        q.offer(v);
        
        while(!q.isEmpty()) {
            int cur = q.poll();
            
            for(Integer next : graph.get(cur)) {
                if(ch[next] == 0) {
                    ch[next] = 1;
                    dis[next] = dis[cur]+1;
                    q.add(next);
                }
            }
        }
    }

    
    public static void main(String[] args){
        그래프최단거리BFS T = new 그래프최단거리BFS();
        n=6;//최대 노드
        ch=new int[n+1];
        dis=new int[n+1];
        int[] aArr= {1,1,2,2,3,4,4,6,6};
        int[] bArr= {3,4,1,5,4,5,6,2,5};
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for(int i=0; i<bArr.length; i++){
            int a= aArr[i];
            int b= bArr[i];
            graph.get(a).add(b);
        }
        T.BFS2(1);
        for(int i=1; i<=n; i++){
            System.out.println(i+" : "+dis[i]);
        }
        System.out.println(Arrays.toString(dis));
    }   
}

결과

1 : 0
2 : 3
3 : 1
4 : 1
5 : 2
6 : 2
[0, 0, 3, 1, 1, 2, 2]

시작 정점에서 각 정점으로 가는 최소 횟수

 

간선 시각화

ch체크를 적용한 상태 트리, 각 레벨 별 횡단은 Q에 저장된 노드다.

브레이크 포인트를 지정하고 디버깅 해보면, 확실히 알 수 있다.

2 지점 큐 상태

 

코드


import java.util.*;

class Node{ 
    int data; 
    Node lt, rt; 
    public Node(int val) { 
        data=val; 
        lt=rt=null; 
    } 
} 
  
public class Tree말단노드까지의가장짧은경로BFS{ 
    Node root; 
    
    public int BFS2(Node root){ 
        Queue<Node> Q=new LinkedList<>();
        Q.offer(root);
        int L = 0 ;
        
        while(!Q.isEmpty()) {
            int len = Q.size();
            
            for (int i = 0; i < len; i++) {
                Node cur = Q.poll();
                if(cur.lt ==null && cur.rt == null) return L;//자식노드가 없다면 말단
                if(cur.lt != null) Q.add(cur.lt);
                if(cur.rt != null) Q.add(cur.rt);
            }
            L++;
        }
        return 0;
    } 
    
    
    public int BFS(Node root){ 
        Queue<Node> Q=new LinkedList<>();
        Q.offer(root);
        int L=0;
        while(!Q.isEmpty()){
            int len=Q.size();
            for(int i=0; i<len; i++){
                Node cur=Q.poll();
                if(cur.lt==null && cur.rt==null) return L;
                if(cur.lt!=null) Q.offer(cur.lt);
                if(cur.rt!=null) Q.offer(cur.rt);
            }
            L++;
        }
        return 0;
    } 
  
    public static void main(String args[]) { 
        Tree말단노드까지의가장짧은경로BFS tree=new Tree말단노드까지의가장짧은경로BFS(); 
        tree.root=new Node(1); 
        tree.root.lt=new Node(2); 
        tree.root.rt=new Node(3); 
        tree.root.lt.lt=new Node(4); 
        tree.root.lt.rt=new Node(5); 
        System.out.println(tree.BFS(tree.root)); 
    } 
}

결과

1

자식 노드가 없으면 당연히 말단이다. 그리고 BFS탐색 특성상 가장 먼저 발견한 것이 가장 최단 거리이므로 바로 리턴한다.

코드

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++ 너비를 탐색하게 된다.

 

 

 

 

 

+ Recent posts