기억하고싶은것들

There are n rooms labeled from 0 to n - 1 and you start in the room 0.

All the rooms labeled from 1 to n are initially locked and you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it

and you can use them to open locked rooms and enter them.

You can visit the same room any number of times and the goal is to visit all the nrooms.

Given an array rooms where rooms [i] is the set of keys that you can obtain if you visited room i,

return true if you can visit all the rooms, or falseotherwise.

0부터 n-1까지의 이름 지어진 방이 있고, 0번째 방부터 시작된다.

1부터 n까지의 모든 방은 초반에 잠겨 있고, 열쇠가 없이는 들어갈 수 없다.

특정 방에 방문했을 때, 열쇠 꾸러미를 발견할 수 있고 그 열쇠 꾸러미를 이용해 잠긴 방을 방문할 수 있다.

방문했던 방에는 몇 번이고 중복해서 방문할 수 있고, 최종 목표는 모든 방에 방문하는 것이다.

방들의 배열이 주어지고, 해당 방에는 열쇠 꾸러미 정보를 가지고 있다.

만약 주어진 정보로 모든 방들을 방문할 수 있으면 true를 반환하고 그렇지 않으면 false를 반환하라.

주어진 방들과 열쇠들의 정보는 tree 형태로 형상화할 수 있다.

주어진 트리를 방문하며, 방문한 방들의 정보를 저장하고 모든 트리의 노드를 순회했을 때 저장한 방문한 방들의 모든 정보가 주어진 방들의 길이와 같으면 모든 방을 방문한 것이다.

recursive 한 형태로 순환을 하고, Depth First Search를 이용하여 tree를 방문하여 보자.

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {

        List<Integer> visited = new ArrayList<>(); // 방문한 방들의 정보를 저장

        recursiveVisit(visited, rooms, 0); // 0번 방부터 시작

        if (visited.size() == rooms.size()) { // 주어진 방의 갯수와 방문한 방의 갯수 비교 
            return true;
        }
        return false;
    }

    private void recursiveVisit(List<Integer> visited, List<List<Integer>> rooms, int i) {

        visited.add(i);
        List<Integer> list = rooms.get(i);

        for (int idx : list) {
            if (!visited.contains(idx)) { // 이미 방문한 방은 다시 방문할 필요가 없다
                recursiveVisit(visited, rooms, idx);
            }
        }
    }

Tree의 종류 

Tree의 탐색 방법

Tree는 노드와 엣지의 연결관계를 나타낸다.

Root는 가장 상위의 노드를 나타내고, Leaf는 가장 하위의 노드를 나타낸다.

대부분의 알고리즘 문제에서 나오는 Tree는 Binary Tree로 자식이 2개 이하만 존재하는 Tree를 칭한다. 

Binary Tree의 종류

Full Binary Tree

각각의 노드가 Child가 없거나 2개의 Child를 가지는 경우

Complete Binary Tree

왼쪽(Left)에서 부터 가득 차있는 경우

Perfect Binary Tree

모든 노드들이 2개의 Child를 가지고 있고 Leaf의 Level이 모두 같은 경우

Tree의 탐색 종류

PreOrder : N->L->R 

( 가운데 노드가 가장 먼저 나온다 ) 

InOrder : L->N->R

( 가운데 노드가 중간에 나온다 )

PostOrder : L->R->N

( 가운데 노드가 가장 마지막에 나온다 )

Recursive를 이용해 Tree 탐색 구현해보기 ( PreOrder )

	public static void main(String[] args) {
		
		TreeNode n1 = new TreeNode(1);
        
        // ... TreeNode 구성 
        
		System.out.println("PreOrder");
		recursivePreOrder(n1);
	}

	private static void recursivePreOrder(TreeNode n) {
		
		if (Objects.isNull(n)) {
			return;
		}
		
		System.out.print(n.val + " - ");
		
		recursivePreOrder(n.left);
		recursivePreOrder(n.right);
		
	}

Iterative를 이용해 Tree 탐색 구현해보기 ( PreOrder )

	private static void iterativePreOrder(TreeNode n) {
		
		if (Objects.isNull(n)) {
			return;
		}
		
		Stack<TreeNode> stack = new Stack<>();
		stack.push(n);
		
		while (stack.size() > 0) {
			TreeNode tmp = stack.pop();
			System.out.print(tmp.val + " - ");
			
			if(Objects.nonNull(tmp.right)) {
				stack.push(tmp.right);
			}
			
			if(Objects.nonNull(tmp.left)) {
				stack.push(tmp.left);
			}
		}
	}