풀이 과정
1. 각각의 섬들을 bfs를 사용하여 구분한다. 코드에서 color 변수가 구분해주는 역할을 한다. 1번섬은 1로 표시 2번섬은 2로표시...
2. 구분된 섬들을 저장한 map배열을 순회하면서 가장자리인 {i,j}와 가장자리가 몇번섬의 가장자리인지를 함께 edge vector에 넣는다.
3. edge벡터를 2중 반복문으로 택시거리를 이용해서 거리를 구한 후에 가장 최소값 저장후 답에서 -1을 했다.
가장자리를 구한후에 전부 bfs로 돌려서 거리를 알아낼까 하다가
가장자리가 적어도 10000개 이하이고 2초가 주어졌기 때문에
터지지 않을 것이라 판단하였다.
*택시거리란?
만약 두점 { x1, y1 }, { x2, y2 }가 주어졌을 때
거리를 | x1 - x2 | + | y1 - y2 | 로 계산하는 거리이다.
코드
'Algorithm' 카테고리의 다른 글
프로그래머스 - 순위 검색 / C++ (0) | 2021.03.04 |
---|---|
프로그래머스 - 신규 아이디 추천 / C++ (0) | 2021.03.03 |
백준 - 16947번(서울 지하철 2호선) / C++ (1) | 2021.02.26 |
프로그래머스 - 키 순서 / C++ (0) | 2021.02.23 |
백준 - 1422번(숫자의 신) / C++ (0) | 2021.02.22 |