2146번: 다리 만들기
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다
www.acmicpc.net
풀이 과정
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 |