27일차(BFS/DFS 실습문제)

BFS/DFS 실습문제

연결된 정점들(BFS/DFS)

무향 간선목록을 입력했을 때 연결된 정점의 컴포넌트(묶음)의 수를 리턴하라
입력은 [][]`타입의 간선목록

BFS/DFS 구현이 싫어서 비교하는 방법으로 구현해 봤는데 오히려 시간이 더 걸린 것 같다. 
그래도 성공해서 만족스럽다.

[DFS] 바코드

1,2,3으로 이루어진 수열 바코드를 리턴해야 함
int타입의 길이가 입력되며 수열중 가장 작은 값을 리턴해야 함
단 부분수열이 중복되면 안된다

핵심은 부분수열 중복을 걸러내는 방법
substring으로 비교대상들을 부분으로 나눠 조건문을 여러개 쓸까 하다가 
너무 복잡해지고 비효율적이라 Reference 이해하는 방향으로 학습을 바꿨다
재귀하는 부분은 여전히 어렵다고 치고, 문자열 비교하는 if문이 정말 깔끔하게 짜여져서 영감이 되었다.

[BFS] 순회

부모 노드가 전부 추가 된 후 하위 노드가 추가되기 때문에
Queue의 특성으로 상위 노드가 먼저 출력된 후 하위 노드가 출력되게 된다. 
결과적으로 Detph 순서로 순회 해 BFS가 된다