(Challenge)Make a Bridge
문제 복기
"문제 풀 때 필요한 건 자신감"
Solution1. 단지 번호 붙이기(1그룹에 번호 붙이기) + 토마토(최소 거리 구하기) 아는 문제들을 짬뽕한 문제이다. 다만 시간 초과가 나오기 때문에 더 빠른 알고리즘을 사용해야하지만 말이다. 아는 문제들을 제대로 구현만 했어도 맞출 수도? 있었을 텐데 말이다.
그룹 배열 생성, 그룹 갯수 구한다.
거리 배열 구한다.
각각의 그룹에 대해 bfs로 최소 거리 구한다.
Solution1으로 풀었을 때 시간복잡도 : NM크기의 지도인 경우, 섬의 갯수는 NM/2개라고 할 수 있다. 하나의 섬에서 BFS 탐색으로 최소 거리를 구하는 방법은 상하좌우로 모든 섬을 탐색하기 때문에 O(NM)이고, 섬은 최대 NM/2이기 때문에 NM/2 x O(NM/2) = O(N^2*M^2)이라는 엄청나게 큰 수가 된다!
Solution2. Solution1에서 조금더 발전시킨 방법
그룹 배열 생성, 그룹 갯수 구한다.
거리 배열 구한다.
바다든 상관없이, 육지인 좌표의 상하좌우 탐색한 nx,ny 에 대해 1차로 붙인 그룹번호로 g[nx][ny] = g[x][y]로 해준다.
그룹 번호가 다른 좌표가 서로 맞닿으면 각각의 좌표값에 대한 거리 배열값을 더해준다!
bfs 구현을 다수번 해야하기 때문에 거리 배열을 구하면서 3번 그룹 배열 업데이트도 함께 구현해준다! 왜냐하면 거리 배열을 구할 때 육지(d[i][j]=0)이 아닌 d[i][j] = -1로 초기화되어있는 좌표들에 대해서만 거리를 구하기 때문에, 업데이트할 그룹 배열도 마찬가지로 바다를 향해 그룹번호로 채워야하기 때문이다!
Solution2로 풀었을 경우 시간 복잡도 BFS는 몇 번 실행되는가? 한번 실행된다고 한다. 일단 육지인 좌표 큐에 넣어서 g배열 완성 - 1번 거리 배열&g배열 업데이트 완성 - 1
Last updated