Red Salmon

출처 : https://www.acmicpc.net/problem/2146

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/2146.cpp

문제가 상당히 귀찮다. 어려운건 아니지만 상당히 귀찮고 오직 BFS로는 풀 수있으나 오직 DFS로는 풀 수가 없다. 아마 있긴할텐데 엄청 복잡해질거다. 나는 DFS+BFS로 풀었다.

문제는 어떤 섬에서 섬까지 다리를 놓을때 최소한이 되는 값이다. 이는 결국 하나씩 다 해봐야 알 수 있는 것이다.

나는 다음과 같이 접근하였다.

1. 먼저 다리를 놓아야할 모든 엣지를 구한다. (즉, 주위에 0이 있다면 다리가 건설 가능한것으로 보고 큐에 해당 지점을 전부 푸시한다.)

2. dfs를 통해 구역별로 값을 따로 매긴다. 나는 처음 영역을 2부터 매겼는데 그 이유는 1은 이미 입력으로 들어온 값이기 때문에 혼동을 피하기 위함이다. 

3. 1번에서 받은 모든 엣지를 통해 다리를 건설하기 시작한다. BFS를 사용하는게 현명하다 왜냐면 모든 값을 조사할 필요 없이, 최소 값만 알면 되기 때문이다. 

절차는 처음에 해당 지점이 몇번째 구역인지 값을 통해 area에 담고, bridge라는 큐에 담는다. 그리고 큐를 통해 사방을 검색하며 BFS를 진행하면 된다. 

여기서 주의해야할 점이 있다. 나는 메모리 초과로 상당히 애먹었다...

1. 만약 ans(현재까지 최소값)보다 현재 cnt(현재 건설중인 다리 수)가  크다면 이는 의미가 없으므로 종료시킨다.
   (시간 초과 방지)

2. BFS로 영역을 확장할때 0인 값과 다른구역의 값을 한번에 큐에 집어넣고 큐가 다음 반복될때 현재 위치가 다른 값이면 이라는 이프문으로 확인시킬수도 있다. 그러나 이렇게하면 시간 및 메모리가 낭비되므로 나처럼 분할시키는 것이 도움이 된다. 

3. 하다보면 1로 둘러 쌓인 지역이 있을것이다. 이런 경우는 만약 0을 기준으로 동서남 쪽이 1이면 3번이 푸시가 된다. 이건 피하기보다는 일단 담는다. 하지만, 어느 한쪽에서 사용되면 -1로 값을 변경하였기 때문에, 아래의 모든 과정을 스킵하게 해야한다. 하고 안하고는 메모리 초과이냐 정답이냐를 가른다. 매우 중요한데 너무 오랜만에 BFS를 하여 실수를 하였다.

이 부분만 잡는다면 그리 어렵지는 않은 문제이다. 다만 귀찮은 문제인데, 시험용으로는 정말 좋은 문제같다. 이런건 보통 KOI에서 정말 많이 봤었다..