프로그래머스 가장 먼 노드, 그래프 BFS swift 문제풀이

 

안녕하세요. 민멍구입니다. ☺️
오늘은 프로그래머스의 그래프 문제, 가장먼노드 swift 알고리즘 문제풀이를 공유합니다. 
바로 진행하겠습니다. 

 

---

프로그래머스 그래프 문제 
가장 먼 노드

코딩테스트 연습 - 가장 먼 노드

가장 먼 노드는 그래프 문제입니다. N개의 노드를 가지며, 각각의 노드는 1 ~ N 까지의 번호가 적혀 있습니다.
이 노드들이 서로 양방향으로 연결이 되어있을때, 1번 노드에서 가장 멀리 떨어져있는 노드의 갯수를 구하는 문제입니다. 

 

 

제한사항은 위와 같습니다. 양방향 간선이므로, 각각의 노드는 연결된 인접 노드의 정보를 서로 갖고 있어야 합니다. 

 

---

입출력 예시

가장 먼 노드 문제는 n(노드갯수), vertex(노드 정보) 입력이 들어왔을 때 가장 멀리 떨어진 노드의 갯수를 구해야합니다. 

 

 

위의 예시의 경우 1로부터 멀리 떨어진 노드는 4, 5, 6이 됩니다.
지금부터 BFS를 통해 각 노드의 1로부터의 거리를 구하고 가장 멀리 떨어져있는 노드의 갯수를 구해보겠습니다. 🤗

 

---

BFS Swift 문제풀이

MX 변수는 가장 먼 노드의 거리를 확인하기 위해 사용합니다. 전역번수로 선언했습니다. 

 

 

위의 코드는 해당 문제, 가장 먼 노드 문제의 핵심인 BFS 구현 코드입니다. 
BFS(너비 우선 탐색) 으로 1번 노드부터 시작해서 노드를 순차적으로 방문합니다.

◼︎ 인자값은 그래프 정보를 담는 G, 각 노드의 방문여부를 담는 C, 각 노드의 1번 노드 간 거리의 빈도수를 담는 CC입니다. 인자값을 받는게 번거롭다고 느끼신다면 전역변수로 두고 해도 무방합니다. 

◼︎ 1번 노드부터 시작하는데 BFS는 큐를 사용하여 구현할 수 있습니다. 처음 시작은 1번노드이므로 1번부터 시작해서 BFS를 진행합니다.

스위프트에는 별도의 큐가 없는데, 간단하게 실제 큐와 유사한 효율을 갖기 위해 현재 큐가 pop() 해야할 인덱스를 갖는 cur 변수를 두어 큐의 끝 정보를 얻고 cur 변수가 1씩 증가시키는 것을 pop()으로 묘사하여 동작시킵니다. push 동작은 append() 가 되겠죠. 이로써 큐가 비었을 경우, Q에 요소가 없음을 체크하는 조건은 Q.isEmpty 가 아닌, cur < Q.count 가 됩니다. 

◼︎ 이제 1번노드부터 시작해서 BFS를 진행합니다. G[현재 순회중인 노드]와 인접한 모든 인접노드를 확인하며 방문하지 않았을 경우 해당 노드는 다시 큐에 넣어줌을 반복합니다. 이때 인접한 노드가 방문하지 않았다면(C[방문노드] == 0) C 배열에 해당 노드 위치의 방문기록(C[방문노드] = 1)을 함과 동시에 (현재 순회중인 노드의 거리 + 1) 처리를 해줍니다. 또한 현재 인접노드의 거리에 대해 CC배열에 빈도수를 카운팅(CC[현재 방문한 노드의 거리] += 1) 및 기록합니다. 

 

 

BFS 탐색을 시작하기 전의 변수 준비 부분입니다. 실제 구현해야할 method이죠.

◼︎ G는 양방향 그래프의 정보를 기록할 2차원 배열입니다. 예를 들면, G[1]에는 1번 노드와 인접한 노드의 정보를 담고 있습니다.

◼︎ C는 각 노드 별 방문 여부를 체크하는 배열입니다. C[2] = 1 이라면 2번노드를 방문했음, C[2]=0 이라면 방문하지 않았음을 의미합니다. 해당 배열은 0, 1 두개의 값 중 하나만을 담으므로 [Bool] 타입으로 선언해서 사용해도 무방합니다.

◼︎ CC는 각 노드 별 1번노드부터의 거리가 계산되었을 때 해당 거리를 가진 노드의 갯수를 기록할 배열입니다. 예를들면, 1번노드로부터 거리가 3인 노드가 5개 존재한다면, CC[3] = 5 가 되는 방식입니다. 

이렇게 배열을 준비 후 BFS를 진행합니다. BFS이후 가장 먼 거리의 노드 수는 CC[MX]를 반환하여 구할 수 있습니다. 앞서 CC에 대해 설명 드렸듯이, "CC[MX]" 는 곧 "가장 먼 거리의 노드 수" 이기 때문입니다. 

 

많은 의견, 댓글 환영합니다. 즐거운 하루 되세요 👨🏻‍💻

 

 

 

 

---

Swift Algorithm Club 커뮤니티 방 링크 ▼

Swift Algorithm Club