가장 먼 노드 BFS 알고리즘

오늘도 역시 프로그래머스 코딩을해보았다.

 

요새 블로그 예쁘게 쓰려고 노력 많이하는데 퇴근하고 막상 쓰려니 이쁘게 못쓰겠다.

 

그리고 문제를 푸는데 Lv3짜리인데 뇌를 안쓰니 역시 뇌가 굳는 것 같다.

이제 몸과 뇌가 서로 같이 굳는 것 같다. 홍홍홍

 

 

아무튼 오늘도 역시 혼자서 풀지 못했다.

시간도 그리 많지 않고 빨리 이해하고 호그와트 레거시를 하고 싶을 뿐

 

아무튼 여차저차 내가 이해한대로 주석을 다 넣어 놨으니 이제야 이해가 갈 것 같다.

사실 문제라는 것은 답이나 해석을 모르면 어렵지 

답이나 해석을 알면 이제 알기 쉬워진다.

 

모르는 책이다 그냥 맘에 들어서 넣어봤다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/49189?language=csharp

프로그래머스

 

문제는 이렇다.

 

n개의 노드가 있는 그래프가 있다.

1부터 n까지 시작하는 노드이며

각각 노드는 서로 양방향으로 연결되어 있거나 연결되어 있지 않다.

이 때 가장 멀리 떨어진 노드를 구하란다.

그래프 이미지

음 처음에 이걸 보고 하나하나씩 가면 되지 않을까?

라고 생각했는데 틀림

그래서 노드에서 순회하는 방법이 뭔가 있었던 것 같은데 인터넷 검색을 해보니까 나왔다.

BFS 알고리즘

너비우선탐색(Breadth First Search)이란 루트(시작점) 노드에서 인접한 노드를 먼저 탐색하는 방법이다.

BFS크리스마스트리

층으로 생각해보면 1층 부터 탐색해서 다시 내려가서 왼쪽부터 다시 2층을 검색이라고 보면 된다.

그럼 순서는 이렇다.

1⟶2⟶3⟶4⟶5⟶6⟶7⟶8

순으로 검색한다.

 

BFS의 특징

1. 이 것은 노드가 서로 양방향 즉 두 노드사이의 최단 경로를 탐색할 때 활용하기 좋다.
   왜냐하면 멀리 떨어진 노드들은 나중에 검사하기 때문이다.
2. Queue를 활용해서 탐색할 노드의 순서들을 저장해서 저장된 순서대로 탐색해야 하기 때문에 FIFO인 Queue를 사용한다.

 

그니까 시작 지점에서 연결된 노드들을 순서대로 탐색하고

다시 순서대로 탐색한 노드에서부터 다시 순서대로 순서대로 순서대로 순서대로 순서대로 순서대로 ㅇㅇㅇ ㅇㅋ?

그림을 보자.

시작지점이 0이다.

 

시작지점도 큐에 담아놓는다.

 

그럼 검사하는 과정을 그림으로 살펴보자.

글보다는 그림이다.

나는 6번부터 갑자기 1번에서 아무것도 갈 수 없는데 왜 2로감? 라고 생각해보았어요.

퇴근해서 멍청이가 되나봄

 

아무튼

 

다시 설명 한다.

방으로 넣는다고 생각하고 보자.

 

(1)번에서 루트 노드에 방문해서 방문을 했으니 방문체크를 한다.

(2) ~ (5)까지 루느토드와 인접한 노드는 다 방문한 적이 없으니 큐에 다 하나씩 담고 방문했다고 가정

그러면 이제 (6)에서 담아놓은 큐부터 인접한 노드를 검사를 한다.

 

근데 이미 루트노드(0)과 2는 이미 방문 한 적이 있으니 끝

거리는 1이 된다.

 

그럼 이제 1층에는 1이 추가가 된다.

그러면 큐에 담겨있는 2, 4 중 2가 먼저 들어왔으니 2를 또 검사한다.

2는 주변에 다 방문한 노드밖에 없다. 물론 시작점으로 돌아갈수는 절대 없다.

그러면 3번을 방문하고 큐에 다시 담는다.

 

이런식으로 노드를 다 방문하기 전까지 계속 반복된다.

 

이 방식은 정말 목표노드까지는 최단길이 경로를 항상 보장한다.

 

하지만 단점은

경로가 매우 길게 되면 탐색 가지가 급격히 증가해서 많은 기억 공간이 필요하게 된다.

한마디로 3층에 100명이 살명 큐에 100개의 데이터가 들어가야 하는것이다 ㅇㅇㅇ

또한 목표노드가 존재하지 않으면 모든 그래프를 탐색하고 실패로 반환이 되는데

무한 그래프로 노드를 짜게 되버리면 목표노드를 찾지도 못하고 끝내지도 못한다.

 

그렇단다.

 

오늘 끝