BFS에 관한 문제를 정리 하였다.

• BFS는 주로 최단 거리를 찾을때에 사용한다.

기본적으로 구현한 코드이다.

• 어렵지 않으니 이런식이라고만 이해를 하자.

첫번쨰 노드와 연결된 모든 값을 확인하면서 진행하는 알고리즘이다.

🔥 송아지 찾기 [BFS]

다른 방법으로도 해결할수 있다고 생각하는 문제이지만 BFS를 연습할겸 문제를 풀어보았다.

결과적으로는 해결하지 못했지만 그래도 배운점이 많은 문제이다.

문제를 설명하자면 우리는 다음 단계로 갈수 있는 경우의 수가 3가지가 있다.

• -1, +1, +5

이렇게 트리를 내려 나가며 중복된 값이 나온다면 시간복잡도를 위해서 처리를 해주어야 한다.

이것을 명심하고 한번 코드를 살펴보면

ch배열은 값의 중복을 확인하는 배열이고
dis를 트리의 깊이를 표현하는 배열이다.

일단 while문이 계속해서 돌게 만든다.

그후 BFS를 이용하기 위해 shift를 사용하여 값을 뺴내온다.

그뒤에 트리를 펼치게 되는데 이때 For문을 사용한다.

해당 for문중 우리가 원하는 값이 나오게 된다면 바로 return해주게 되고

그렇지 않다면 중복되는 값인지 확인을 하고 깊이를 표현하는 dis변수를 갱신한다.

코드를 읽어보면 조금 이해하기가 난해한 부분은 dis였다.

말 그대로 깊이를 표현하는 배열인데

처음 5의 깊이는 0

그다음 4,6,10 의 깊이는 1

그다음 트리 값들의 깊이는 2 이런식으로 작동을 하게 된다.

이해가 안되면 이 코드를 참고해 보자

dis만 없는 코드이다.

dis대신 깊이를 표현하기 위해 L이라는 변수를 사용 하였다.

• 이런식으로도 해결이 가능하다.

🔥 섬나라 아일랜드 [BFS, DFS]

두가지 방법으로 모두 해결할수 있는 문제이다.

🌪 DFS

우선적으로 익숙한 DFS로 해결해 보았다.

• 이 문제는 내가 스스로 해결한 문제이다.

일단 board에서 1인 값을 찾아낸다.

• 그러면 그곳에는 땅이 있다는 소리니깐

그후 DFS를 돌려서 그냥 지나친 지점을 0 으로 초기화 해주면 된다.

• 사실 이떄까지 배운점을 활용하는것이기 떄문에 별다른 설명은 넘어가겠다.

🌪 BFS

이번에는 이번에 학습한 BFS를 이용한 코드이다.

• 내 기준에서는 DFS가 좀더 익숙하다.

어떻게 작성을 하냐의 차이지 이 또한 기본적인 베이스는 같기 떄문에 부가 설명은 넘어가겠다.

후기

내 입장에서는 하나도 못풀것 같은 문제도 서서히 풀려가는 모습을 보고 참 뿌듯하면서도

한편으로 정말 좋은 시간을 보냈다고 생각을 한다!!

어느 정도 그래프를 활용하는 것에 대해서 익숙해 진것 같다.

• 재귀도 좀 많이 익숙해 진것 같다.