본문 바로가기
알고리즘 문제/Leetcode

[Leetcode][934] Shortest Bridge

by 햄과함께 2018. 11. 10.
반응형

문제 : https://leetcode.com/problems/shortest-bridge/




BFS로 풀었다.

먼저 배열을 탐색하면서 1 위치를 찾는다.

찾은 위치를 시작점으로 BFS를 돌리면서 연결된 1을 2로 모두 바꾼다.

바꾼 배열에서 아까의 시작점을 또 다시 시작점으로 하여서 BFS를 한 번 더 돌린다.

이번에는 0을 1로 바꾼 횟수도 저장해야 한다. 따라서 이때의 너비우선탐색은 0 -> 1로 바꾼 횟수가 가장 작은것부터 먼저 탐색한다.

다음 탐색 위치가 0이라면 탐색횟수+1을 한다.

2라면 같은 땅이므로 탐색횟수는 이전과 같다.

1이라면 현재까지 탐색한 횟수가 정답이 된다.


시간복잡도는 정확하게는 잘 몰겄지만 BFS를 2번 돌리니까 대략적으로 배열크기와 같다고 보면 될 듯하다. 




소스코드 : https://gist.github.com/fpdjsns/59962287227c57a39840805344abf895

반응형

태그

댓글0