[Swift] 프로그래머스 가장 먼 노드 (쉬운 풀이 포함)

Problem

 

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

---

Solution

 

해당 문제는 BFS로 풀어야 하는 문제입니다.

 

1부터 시작해서 1과 연결된 숫자들 그리고 연결된 숫자들과 연결된 숫자들을 나열해줍니다.

 

나열하면 아래 그림처럼 될 것입니다.

 

 

여기서 우리는 한 라인이 연결될 때마다 라인의 숫자를 늘려가줍니다.

 

위  그림에서 왼쪽 파란색 숫자 모양을 참고 해주세요.

---

하지만 라인 2까지 왔을 때 문제점 이 생기는데요.

 

2와 연결된 1,3,4,5 중에서 1과 3은 갈 필요가 없습니다.

 

왜냐하면 이미 위에서 연결을 만들어준 숫자들이기 때문입니다.

 

이 문제를 해결하기 위해서 이미 지나온 숫자들은 true라고 표시를 해줍니다.

 

그 다음 연결될 숫자들 중 true값이 있는 숫자들은 아래라인으로 연결하지 않아도 되게끔 하는 것이죠!

---

하지만 여기서 이렇게 연결하면 또 한가지의 문제점 이 생깁니다.

 

2와 연결된 숫자들은 4,5 

 

3과  연결된 숫자들은 4,6

 

4가 중복 이 되죠?

 

그러므로 각 라인에 저장될 숫자들은 중복을 없애준 뒤 저장하도록 합니다.

 

이렇게 모두 한 뒤 가장 마지막 라인을 찾아내서 숫자들이 몇 개 있는지 확인하면 정답이 됩니다!

 

---

Source Code

 

 

---

---

P.S

 

맨 처음에 각 라인별 숫자들을 저장할 때 이차원 배열을 만들어서 각 라인별로 인덱스를 다르게 해서 

 

넣어 저장한 뒤 가장 마지막에 있는 배열의 갯수를 반환하려고 했다.

 

하지만 테스트 7번과 9번에서 2301ms , 6424ms라는 말도 안되는 시간이 걸렸다...

 

그래서 결국 위 풀이처럼 배열 대신 딕셔너리에 키값으로 숫자를 밸류값으로 라인값을 넣고 가장 큰 밸류값의 갯수를 세어서

 

반환했더니 2400,6400이었던 시간이 40,60으로 줄어들었다.

 

다음부터 BFS 문제를 풀 때 값을 딕셔너리 안에 저장해야겠다.