www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 처음엔 완전 탐색으로 다리를 전부 놓으면서 최적의 수를 찾는 줄 알았다. 알고리즘 분류를 보니 BFS, DFS여서 어떻게 해야 할지 감이 잘 안 잡혔다. 1. 1차 BFS를 통해 대륙의 번호를 지정해준다. 2. 큐에 땅의 위치를 전부 삽입해준다 3. BFS를 한번 더 돌려서 이동 범위가 바다라면 큐에 삽입해준다 4. 이동 범위가 땅인데 대륙 번호가 같지 않다면 거기까지의 거리를 리턴해준다. #include #incl..

www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도� www.acmicpc.net BFS와 DFS를 연습하기에 좋은 간단한 문제였다. 주의해야 할 점이 있다면 상하좌우뿐만 아니라 대각선에도 땅이 있다면 섬으로 연결시켜줘야 한다. #include #include using namespace std; int ar[51][51]; bool vis[51][51]; int dx[8] = { 0,0,1,-1,-1,1,-1,1 }; int dy[8] = { 1,-1,0,0,-1,-1,1,1 }; ..