[c++] 백준 다리 만들기(2146), BFS, 반례모음

문제 https://www.acmicpc.net/problem/2146

• 회색은 땅, 하얀색은 바다. 땅간의 연결 가능한 최단거리를 구하시오.

 

반례모음

5 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 2

5 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1

6 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1

5 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 2

4 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 4

 

풀이

• 풀이가 2가지 있습니다.
• 1) BFS기반 정석적인 풀이 
  - 땅의 영역을 BFS를 통해서 찾고, 각 땅의 영역에서 BFS로 다른 땅의 영역을 찾습니다.
  - 먼저 다른 땅에 도달했을 때, 최단경로입니다.
  - 간단해보이지만, 다른 땅에 도달하도록 BFS를 구성할 때, 조건문이 까다롭습니다.
  - 그러나, 속도가 매우 빠릅니다. 4ms
• 2) BFS + 좌표기반 거리 구하기
  - 땅의 영역을 BFS로 찾는 것은 동일합니다.
    단, 땅의 좌표(x,y)를 모두 저장하고, 동시에 땅의 번호도 함께 저장합니다. 
  - 구한 좌표들을 다른 땅들간에 거리를 구해줍니다. (x,y)를 알기 때문에 손쉽게 가로 몇칸 세로 몇칸을 구할 수 있습니다. 가장 작은 거리를 출력합니다.
  - 속도가 조금 느립니다. 48ms
  - 그러나, 까다로운 조건문이 없기 때문에 직관적이며 실수할 확률이 적습니다.
• 저는 2)번 방법으로 풀이하였습니다.
     

코드

 

알게 된 점

• BFS는 속도는 빠르지만 조건문이 너무 까다로운 것 같다. 생각해줘야 할게 많음. 이론적으로는 납득이 쉽고 이해가 가지만 코드로 세세하게 구현이 필요하다. 

 

git 코드

https://github.com/intlabSeJun/c-plus-coding-test/blob/master/9.%20BFS/%EB%8B%A4%EB%A6%AC%EB%A7%8C%EB%93%A4%EA%B8%B0(2146)%EC%88%98%EC%A0%951.cpp