Better

참고사이트:https://blog.naver.com/ndb796/221230994142

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 입니다.

* MST(최소 신장 트리)를 만들기위한 알고리즘 입니다.

MST란 Minimum Spanning Tree 로서 최소 신장 트리라고 합니다.

특징은

간선의 가중치 합이 최소여야 하고,

n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선을 사용해아 하며,

사이클이 포함되어서는 안됩니다.

구현 방법이 바로 Kruskal MST 알고리즘 입니다.

참고사이트:https://blog.naver.com/ndb796/221230967614

합집합을 찾는 그래프 알고리즘 입니다. Disjoint - Set 알고리즘 이라고도 합니다.

여러개의 노드가 존재할 때 두개의 노드를 선택해서, 두개의 노드가 현재 같은 그래프에 속하는지 판별하는 알고리즘 입니다.

크루스칼 알고리즘에 사용되는 알고리즘 입니다.

https://www.acmicpc.net/problem/17471

DFS혹은 BFS를 잘 활용해야하는 문제였습니다.

저는 DFS를 사용해 해결했습니다.

* n이 2일때 예외처리를 해줍니다.

접근방법

1. 그룹을 두개로 나누기 위해 1~n/2 개씩 그룹화 해주면, 각 케이스별로 나머지 도시들도 다른 그룹이 됩니다.
2. 그룹을 나누는건 백트래킹을 사용해 순열을 조합합니다. (next permutation)
3. 그룹이 정해지면 A,B그룹으로 도시들을 리스트에 담고, 각 그룹이 연결되었는지 DFS를 활용해 점검합니다.
4. 만약 두 그룹 모두 연결된 상태면 인구수 차이의 최솟값을 업데이트 합니다.

https://www.acmicpc.net/problem/17406

배열을 시계방향 회전시키는 시뮬레이션 문제였습니다.

연산 순서 순열을 백트래킹 적으로 만든 뒤 연산 순서에 따라 배열을 회전시켜주는 식으로 구현했습니다.

연산 순서를 바꿔 연산할때 마다 원본 배열을 사용해야 합니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo&categoryId=AWXRQm6qfL0DFAUo&categoryType=CODE

부르트포스, DFS(백트래킹), BFS를 사용한 시뮬레이션 문제였습니다.

구현방법

1. 구슬을 놓을 열의 위치를 백트래킹적으로 모든 경우의 수를 구해줍니다.
2. 주어진 구슬의 수 만큼 경우의 수가 충족되면 게임시작. 
3. 타겟 열의 가장 첫번째 벽돌을 시작점으로 합니다. 타겟 열에 벽돌이 없을경우 바로 다음으로 넘어갑니다.
4. 상하좌우로 벽돌의 파워만큼 주변벽돌을 깨트려 줍니다.
5. 벽돌을 깬 뒤, 남은벽돌 들 을 밑으로 내려 줍니다. (Stack을 사용합니다)
6. visited배열 도 매번 리셋해줍니다.(중요)

https://www.acmicpc.net/problem/3954

시뮬레이션 문제였습니다.

* 주의할 점

만약 [ [ ] [ ] ] 경우 내부에서 무한루프인지 외부에서 무한루프인지 알아야 합니다.

그리고 무한루프의 분기를 위해 배열을 사용해서 점프지점을 저장해줍니다.

이 부분은 다른 블로그를 참고하여 구현했습니다.

https://lcs11244.tistory.com/61

이 외에는 시뮬레이션으로 구현해주면 됩니다.

https://www.acmicpc.net/problem/17142

반례들이 많은 문제 였습니다.

특히 활성바이러스가 비활성 바이러스에 도달하면 활성으로 변하는 조건을 빠트리면 안됩니다.

주어진 조건을 세세하게 지켜주어야 합니다.

맵은 char배열로 구현하였고,

바이러스가 놓여질수 있는 곳을 LinkedList에 저장해놓고 시작합니다.

LinkedList를 사용해서 백트래킹적으로 바이러스가 활성화 될 수 있는 지점을 정해줍니다.(brute force)

활성 바이러스가 m개가 되면 바이러스 전파가 시작되고, 전파가 끝나면 맵에 전파가 안된 지점이 있으면 그대로 종료하고,

아니면 걸린시간의 최소값을 계속 업데이트 해줍니다.

* 백트래킹에 사용하기 위해 LinkedList와 같이 사용하는 boolean[] viisted배열이 있고

* 바이러스 전파할때 비활성 바이러스가 활성으로 변하는 반례를 해결하기 위해 boolean[][] virused배열을 사용했습니다.

* 활성 바이러스 지점을 처음엔 백트래킹을 위해 '!'으로 masking 해주고, 전파가 시작될때 비활성을 '*', 활성을 '0'으로 바꿔주어야 바이러스 전파가 끝나고 최소 시간을 측정할때 간편해 집니다.

https://www.acmicpc.net/problem/17140

• ArrayList[][]를 사용하여 맵을 구현했습니다.
• 정렬은 Comparator의  compare를 오버라이드 하여 사용했습니다.
• 횟수와 숫자를 저장할 Pari클래스를 정의하고
• ArrayList<Pair>[] pairs를 사용해 다음 행렬의 값들을 순서쌍으로 나타낸 뒤 정렬합니다. 제로패딩도 pairs를 사용해 구현합니다.
• 만들어진 pairs를 토대로 nextMap에 다음행렬을 나타내고, 원본 map을 다시생성해서 복사하는 식으로 구현했습니다.