꼼개의 개발자취

문제 : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제설명 1. BFS, DFS, Prim, Kruskal 등 다양한 알고리즘이 사용된다. 2. 문제를 잘 분석하고 하나하나 디버깅하며 해결한다. 알고리즘 1. BFS와 DFS를 사용하여 labeling 후 labeling 한 구역을 하나의 정점이라 생각한다. 2. 정점 사이의 거리를 PQ에 넣어준다. 3. PQ와 Union-Find를 이용하여 Kruskal 알고리즘을..

서론 DFS는 가장 많이 쓰이는 알고리즘이다. 아마 대부분의 문제들은 DFS와 BFS 알고리즘으로 해결되기 때문에 꼭 알아야 한다. DFS는 Stack 또는 재귀로 구현할 수 있는데 재귀로 구현하는 것이 직관적이고 가독성도 좋다. DFS를 구현하기 전에 문제에서 원하는 조건을 꼭 알아야 한다. 중복이 되는지, 순서대로 하는 건지 등등.. 조건에 따라서 방문했던 곳을 제 할 수 돼있고, 포함시킬 수 도있다. 그러므로 꼭 문제의 조건을 확인해야 한다. 만약 DFS가 구현하기 어렵다면 기본적인 틀을 외우고 문제를 풀어가며 이해한다. 구현 코드 1. 중복 가능 순열(1~2중에 3개 선택 중복가능) public class PermutationNPIN { static int n; //순열의 자리수 static in..