[ 백준/C++] 17472 다리만들기2 (삼성A형 기출문제,BFS,DFS 이용하기)

파란것은 섬이고 하얀것은 바다 그리고 회색의 다리로 섬들을 최소 길이로 이으라는 문제이다. 문제 자체는 이해하기 어렵지 않다. 다리는 직선이어야 하고 길이는 2이상이어야 한다. 그리고 다리는 섬과 섬 사이를 이어야한다. 즉, 다리를 잇는 도중에 다리를 짓는 방향과 다른방향으로 섬이 있다고 해서 섬이 이어졌다고 판단하면 안된다. 그런데 이 문제를 푸는 방법은 좀 생각을 잘 해야 한다. 코드를 보면 좀 복잡 해 보이겠지만 함수의 이름을 최대한 직관적으로 쉽게 지정해 놓았으니 찬찬히 보면서 이해해 보면 좋을 것 같다. 일단 풀이의 알고리즘 순서는 다음과 같다. 1.dfs()를 이용하여 일단 섬의 개수를 구한다. dfs를 이용하여 동서남북 4방향 다 체크하면서 더 이상 갈 곳이 없으면 빠져나와서 섬 개수를 카운..

2023.02.12