728x90

목sssssss록다리 만들기 2 (1)

개발조아

[BOJ/백준] 17472 다리 만들기 2 파이썬

문제 링크 : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 예전에 풀었던 걸 MST로 다시 풀어봤다. 예전에는 BFS,DFS로 완탐으로 해결했었다. 이번에는 BFS, MST로 해결했다. BFS로 각 섬에 번호 매기면서 섬의 가장자리를 구한다. 이때 해당 점에서 이동하려는 점이 격자판 안에 있고 물인 경우 가장자리로 판별해서 저장했다. (x,y,방향) 이때 방향은 해당 칸으로 온 방향이다. 구한 가장자리에서 다리를 만들면..
알고리즘/백준 2021. 12. 3. 23:32
Prev 1 Next
728x90