프로그래머스 3단계 BFS 문제, 순위 swift 알고리즘 풀이

---

프로그래머스 BFS 3단계 문제, 순위 문제 개요

프로그래머스의 BFS문제 중 하나인 순위문제를 swift언어로 풀어보겠습니다. 해당 문제는 n명의 선수와 승/패기록이 주어졌을때 순위를 단정지을 수 있는 선수의 수를 구하는 문제로, 자세한 설명은 아래 문제링크를 통해 확인하신 후 풀이를 보시기 바랍니다.

프로그래머스 BFS문제, 순위 swift문제링크 ▼

코딩테스트 연습 - 순위

오랜만에 문제를 풀어보네요 ^-^... 그럼 바로 swift언어로 BFS 접근을 통해 프로그래머스 Lv3 문제, 순위문제 풀어보겠습니다.

---

프로그래머스 BFS 3단계 문제, 순위 swift 문제풀이

먼저, 순위를 단정지을 수 있는지를 체크하는 이차원배열, chk와 승패 관계를 저장할 그래프, G를 선언했습니다.

4행) chk[j][j]는 i번째 선수와 j번째 선수와의 순위를 단정지을 수 있는지 유무를 갖고 있습니다.
5행) G[i][j]는 i번째 선수가 j번째 선수를 이겼음을 의미합니다.

num번째 선수에 대한 BFS를 연산하는 메서드입니다. G 그래프를 사용해서 num번째 선수에 대해 순위를 단정지을 수 있는 선수들을 기록하게 됩니다. swift에서는 기본적으로 Queue를 제공하지 않으므로, 일반 배열 + cur 커서를 사용해서 큐와 비슷한 동작을 구현했습니다.

14행) 만약 num, next번째 선수에 대한 정보가 true로 갱신된 적이 있었다면 건너뜁니다. BFS에서 중복연산을 방지하기 위함입니다.
만약 num, next번째 선수 간의 순위 단정가능 여부 정보가 기록된적이 없다면 양쪽의 관계에 대해 순위 판별이 가능함을 chk 이차원배열에 갱신해줌며, 이어서 next번째 선수에 대한 너비우선탐색을 위해 Queue에 next를 넣어주며 탐색을 계속 수행해줍니다.

* 이전에 커서 개념을 통해 물었던 문제가 있었는데요. 궁금하시면 아래 다른 문제풀이 링크도 참고하시면 되겠습니다.

프로그래머스 알고리즘, 기능개발 swift 배열큐 문제풀이

이제 실제 구현할 ㅁ메서드 부분입니다.

23행) 먼저, num번째 선수는 자기자신과의 순위 판별가능 여부를 확인할 필요가 없으므로, chk[num][num] 값을 true로 초기화해주고 있습니다.
27행) result는 result[0]번째 선수가 result[1]번째 선수를 이겼음을 표현하는 정보입니다. 이를 G에 기록하는 과정입니다. G를 통해서 BFS과정에서 선수간 순위판별가능 여부를 확인하고, chk에 기록했었죠?
31행) 이제 1 ~ n번째 선수를 차례대로 BFS연산 수행해서 chk 배열에 답 도출에 필요한 정보를 기록하게 됩니다.

이제 답을 반환하는 과정입니다. 저의경우에는 reduce를 사용해서 1 ~ n번째 선수를 하나하나 돌아보며, 1 ~ n번째 선수와의 순위판별이 가능할 경우, result에 하나하나 카운팅을 해서 result값을 반환했습니다.

내부의 for문은 대신 forEach를 사용할 수도 있겠지만, forEach는 break를 통해 반목문 수행 도중에 빠져나오는게 불가능합니다. 모든 케이스를 무조건 순회해야하는 단점이 있기에 for문을 사용했습니다.

이렇게 커서와 배열을 활용하여 큐와 같은 동작을 수행시키고, BFS로 접근해서 선수 간의 정보를 chk에 기록하고, reduce를 통해 chk값에 따른 정답을 도출할 수 있었습니다.

관련해서 질문, 지적 환영합니다. 즐거운 하루되세요 ^-^//

---

프로그래머스 BFS 3단계 문제, 순위 swift 문제풀이 결과 ▼