[프로그래머스] 가장 먼 노드 (Swift, Java)

[프로그래머스] 가장 먼 노드 (Swift, Java)

https://programmers.co.kr/learn/courses/30/lessons/49189

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

풀이

1. BFS

일단 문제를 읽고 1번 노드와 모든 노드간의 거리를 구해야했기 때문에 가장 가까운 노드부터 탐색하는 BFS 를 이용해야겠다고 생각했습니다.

 

노드의 탐색은 BFS 를 이용하면 비교적 간단하게 구현할 수 있지만, 가장 먼 노드의 개수를 알아야 했기 때문에 노드간의 거리를 계산하는 것이 문제의 핵심이라고 생각했습니다.

2. 거리 계산

거리계산을 위해 각 노드마다 1번 노드로부터의 거리를 계산하여 저장하기로 했습니다. 먼저 1번 노드는 자기 자신이기 때문에 거리를 0 으로 초기화시켜줍니다.

 

1번 노드부터 BFS 를 시작한다면 1번 노드와 인접한 노드들을 모두 방문하기 때문에 1번 노드에 인접한 노드들은 모두 거리가 1이 됩니다. 이를 dist 1 이라고 하겠습니다.

 

다음으로는 dist 1 노드들과 인접한 노드들을 탐색하게 됩니다. 이 노드들과 1번 노드와의 거리는 2가 됩니다.

 

이후 탐색하는 노드들과 1번 노드와의 거리는 이전에 탐색했던 노드와 1번 노드와의 거리에 1을 더한 값이라는 것을 알 수 있습니다.

 

모든 노드들과 1번 노드와의 거리를 구한 다음, 가장 큰 값이 몇 번 등장하는지 세어주면 정답이 도출됩니다.

코드

Swift

Java

TIL

메모리 초과

그래프 탐색 문제를 풀 때 대부분 인접행렬로 구현하는것이 익숙해서 그렇게 하는 편입니다. 해당 문제를 처음 풀 때도 인접행렬로 구현하였으나 테스트케이스 8,9 번에서 메모리초과가 발생했습니다.

 

알아본 바로는 그래프 문제를 인접행렬로 풀면 메모리나 시간초과가 발생하는 경우가 많으니 인접리스트로 해결하는게 더 효율적이라고 합니다.

 

생각해보면 노드의 개수가 많아질수록 낭비되는 공간이 더 많을테니 당연한 얘기라고 생각합니다.

 

시간복잡도도 인접리스트가 더 효율적이니 앞으로는 인접리스트로 구현하는 버릇을 들여야겠습니다.