본문 바로가기

프림

[백준] 17472번 다리 만들기 2
[백준] 17472번 다리 만들기 2 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 이 문제에서는 섬과 바다를 2차원 배열의 형태로 제공합니다. 그리고 해당 섬들을 모두 잇는 최단 길이를 구하는 문제입니다. 🎲 문제 풀이법 1. 우선, 각각의 섬을 구별하는 작업부터 해주어야합니다. BFS를 이용해 각각의 섬에 인덱스를 부여해 구별하여 줍니다. 2. 그다음 이중포문으로 배열 전체를 돌면서 섬이 있는 칸으로 부터 상하좌우로 검사를 해줍니다. 검사는 재귀함수를 통..

티스토리툴바