프로그래머스 2단계, 무인도 여행 DFS 알고리즘 문제 풀이

 

 

오늘은 프로그래머스 2단계 문제, 무인도 여행을 풀어보겠습니다. 문제 개요부터 간단하게 설명 드리겠습니다.

---

프로그래머스 2단계 문제, 무인도 여행 개요

입력은 [String] 타입의 배열이 들어옵니다. 이 배열은 위와 같은 정보가 String 타입으로 구성되어있습니다.

각 행이 하나의 String으로, N개의 String이 답긴 [String] 배열이 입력으로 들어왔을때, X의 방해를 받지 않고 이동 가능한 인접한 숫자들의 합을 오름차순으로 출력하는 문제입니다. 인접합이 0을 초과하는 경우가 없다면, [-1]을 반환합니다.

예를 들어, 위 문제는 1, 1, 27(5 + 9 + 1 + 1 + 5 + 2 + 3 + 1) 이 답이 됩니다. 해당 문제는 BFS, DFS 등으로 문제를 해결할 수 있는데, 본 포스팅에서는 깊이우선탐색 개념인 DFS로 풀어보겠습니다. 이어서 문제를 풀어보겠습니다.

 

---

프로그래머스 2단계 문제, 무인도 여행 DFS swift 풀이
주어진 maps를 탐색하기 쉽게 이차원 배열로 가공, dfs 순회 준비

4 ~ 6행) 먼저, 입력으로 받은 [String] 타입의 maps 배열과 reduce 연산자를 사용하여 [[Character]] 타입의 2차원 배열을 생성했습니다. "X", "2" 등의 요소를 쉽게 접근하기 위해서 [String] -> [[Character]]로 가공하는 과정입니다.

* String타입의 Element는 Character입니다. Array 생성자 인자로 String 문자열을 넣으면 [Character] 타입이 됩니다.

7 ~ 11행) 이어서, 주어진 maps의 행과 열 크기를 row, col로 정의해서 기록했습니다. dx, dy는 상/하/좌/우로 인접한 숫자가 있는지 판별하기 위해 사용합니다. visit는 graph를 탐색할때 이미 방문했는지 여부를 체크하는데 사용합니다.

 

---

graph 내의 인접 숫자 탐색을 위한 dfs 구현

dfs 탐색을 하는 코드입니다. 특정 행, 열(x, y)를 기준으로 인접한 숫자들의 합을 도출하는 메서드입니다. 상/하/좌/우로 순회를 하는데, graph 범위를 이탈하거나, 이미 방문을 했으면 탐색을 하지 않습니다. 그렇게 인접한 숫자의 합을 반환하는 문제입니다.

* '0' ~ '9' Character의 asciiValue에 48을 빼면, 0 ~ 9라는 Int 타입 값을 얻을 수 있습니다.
* swift 언어는 메서드 내에 또다른 메서드를 선언하고 호출할 수 있습니다. 이런 것을 중첩 함수, nested function이라고 합니다.

 

---

구현한 DFS 메서드를 활용하여 모든 케이스에 대한 인접 숫자의 합 구하여 오름차순 반환

29 ~ 37행) 이제 앞서 구현한 DFS 메서드를 활용할 차례입니다. graph의 모든 위치에 대해 시작점으로 했을때 인접한 숫자의 합을 구합니다. 합이 0을 초과했다는 것은 최소한 어떠한 숫자를 방문했다는 것이기에, 유효한 케이스이며, 이를 ans에 추가해줍니다.

39행) 최종적으로 ans에 element가 존재하지 않다면, 케이스가 없었으므로 문제 룰에 따라 -1을 반환했습니다. 케이스가 존재했다면 모든인접합 케이스를 오름차순 정렬 후 반환해줍니다.

 

---

오늘은 DFS 접근을 통해 프로그래머스 2단계 연습문제, 무인도 여행이라는 문제를 해결해보았습니다.

해당 문제는 DFS뿐만 아니라, BFS로도 해결할 수 있는 문제이며, DFS, BFS를 익힐때 풀 수 있는 기본 수준의 문제라고 볼 수 있겠습니다.

지금까지 프로그래머스 2단계 코딩테스트 문제, 무인도 여행을 DFS 관점으로 swift언어로 풀이해보았습니다. 많은 의견 댓글 환영 드리며, 이만 포스팅 마치겠습니다. 감사합니다. 😁