다리2 [Java] BOJ 17472번 다리 만들기 2 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 BFS와 Prim 알고리즘을 사용하여 해결했습니다. 자세한 내용은 코드의 주석을 참고해주세요. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.St.. 2021. 7. 15. [Java] BOJ 1010번 다리 놓기 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 DP를 사용하여 해결했습니다. 예를들어 N = 2, M = 5이고 i = 1, j = 1이라면 왼쪽에 한개, 오른쪽에 한개의 사이트이므로 위 이미지와 같이 1개의 연결이 가능합니다. i = 1, j = 5라면 왼쪽에 1개 오른쪽에 5개의 사이트가 있으므로 위 이미지와 같이 5가지 경우로 연결이 가능합니다. 이를 그래프로 표현하면 1 2 3 4 5 1 1 2 3 4 5 가 됩니다. 다음으로 i = 2이고 j = 1일 경우에는 위 그림과 같이 2개의 다리가 설.. 2021. 4. 16. 이전 1 다음