꼼개의 개발자취

문제 : https://www.acmicpc.net/problem/6987 6987번: 월드컵 www.acmicpc.net 문제설명 6팀의 모든 경우의 수를 탐색하는 문제이다. 재귀와 백트래킹을 이용하여 해결한다. 알고리즘 1. 재귀를 이용하는데 종료조건은 무사히 15경기까지 오는 것이다. 2. 각 팀의 승리 , 패배 , 무승부 횟수가 음수가 되면 return 한다. 3. 1팀은 2,3,4,5,6 팀과 경기 2팀은 3,4,5,6 경기 3팀은 4,5,6 ~~ 이런식으로 진행된다. -> team, index 변수 사용 주의사항 1. 승 패 무승부 합쳐 30개가 안되는 TK가 존재한다. 2. 백 트래킹 조건은 종료조건 보다 위에 배치한다. 구현 public class Main_월드컵 { static int w..

문제 : 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 알고리즘을..