WOOHU

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

문

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

문

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?

천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.

케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.

오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.

2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4르 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다.

4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

입

첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다.

출

첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

입력예

5 5
1 3
1 4
4 5
4 3
3 2

출력예

3

링크 http://59.23.113.171/30stair/dam/dam.php?pname=dam&stair=14

댐 문제는 다음과 같다.

우선 입력으로 마을의 크기가 주어지고

기둥과 물이 지나 갈 수 있는 길이 1 과 0으로 표기된다.

그 후에 호수의 좌표가 주어지고 

댐을 건설 할 때 걸리는 시간을 주어지게 된다.

위 문제는 dfs bfs 모두 사용 가능 하다(최대 마을의 크기가 100*100 이기 때문) 

하지만 맵의 크기가 더 크게 주어진다면 bfs를 사용 시 타임 아웃에 걸리게 될 것이다.

나 같은 경우는 큐를 생성하고 큐에 첫 좌표를 주어주고 물이 이동 가능한 길을 찾아서 너비 우선 방식으로 찾아가게 만들었다.

너비 우선(BFS)의 경우 큐를 만들어야 하므로  알고리즘을 짜는데 시간이 더 걸리고 디버깅도 힘들게 된다.

하지만 쓸데없는 연산을 하지 않아 유용하다. 

해결 방법은  물의 좌표를 가지고 상하좌우 방향으로 물을 퍼트린다. 

나 같은 경우는 큐에 물에 좌표를 넣고 물이 모두 마을을 덮칠 때 까지를 구하고 그 값에 대해서 댐을 건설 할 수 있는지 체크해서 

출력하는 방법을 택하였다.

여기서는  다 찾을 필요없이 댐을 건설하는데 걸리는시간+1 까지만 구하면 최적의 방법으로 구할수있지만 나는 완전 다찾은후에 개수를 세었다.

위의 방법으로하면 수행 시간을 조금 더 단축 할 수 있을 것이다.

정렬정리

버블정렬은 구현하기 매우쉽고 이해하기도 가장쉽다

하지만 시간복잡도가 평균과 최악의경우 O(n^2)로 크기때문에 개수가 몇개안될때만 사용가능하다.

정렬해야할 원소의 개수가많아진다면 퀵소트나 병합정렬을 이용하는게 더  나을수 있다.

10만개의 배열을 랜덤하게 생성후 정렬한 결과.

정렬정리

선택정렬은 앞쪽에서부터 차례대로 순서에 맞게 원소를 넣어주는 소팅방법이다.

일단 최소값을찾고 그값에대한 자리를 확정해주는 방법이다. 

구현이쉽고 간단하지만 시간복잡도가 높은게 단점이다.

10만개의 배열을 랜덤하게 생성후 정렬한 결과.

정렬 정리

병합정렬은 N개의 원소에 대해 N/2개로 분리하고 또 N/4개 .....  N/(2^N)개로 나눈후 합치면서 정렬해나가는 정렬방법이다.

분할하는 과정은 재귀함수를 통하여 분할을한다.

원소가 1개 까지 남는 과정을 재귀를 통하여 분할하도록하는데

이때 if문을 통하여 확인한다  //if(left<right)

분할이 완료되었다면 병합하는 함수를 호출해준다. //marge_sort(arr, left, mid, right)

병합하는 과정은 다음과같은데 left ~ mid 부분의 원소와 mid+1 ~ right 부분의 원소를 크기순으로 구분하고

병합해주도록 한다.

이떄 한쪽의 원소가 모두 정렬이 된다면 남은 한쪽의 원소를 전부 넣어준다(한쪽원소들보다 클수밖에 없으므로)

이과정을 재귀를 통해 모두수행하고나면 정렬이 완료된다.

10만개의 배열을 랜덤하게 생성후 정렬한 결과.