Red Salmon

출처 : https://www.acmicpc.net/problem/1707

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/1707.cpp

이 문제는 저번에 푼 이분매칭과 비슷한 문제이다. 이분 매칭, 최대유량, 네트워크플로우, 이분그래프 다 비슷한것 같다. 즉 어렵다... 완전히 내 지식이 되지 않은 것 같다.

우선 이 문제는 최대 정점이 2만개 최대 간선이 20만개다. 거기에 K가 최대 5까지 들어온다. 단순 계산만 22만번의 입력이 5번이 들어오니 총 110만번의 입력이 필요하다. 즉, cin쓰면 안된다. scanf를 써야 시간을 줄일 수 있다.

문제는 그냥 그래프를 주어졌을때 이것이 이분그래프인지 아닌지 판별하는 것이다. 이 문제를 나는 저번과 같은 생각을 하며 접근하면 답이 나올거라고 확신하였다. 

그러나 생각은 했으나 구현에는 실패하여 타인의 소스 도움을 받았다. 그리고 다시 작성하여 정답을 맞았다.

우선 알아두어야 할것은 이분 그래프이다. 즉 A아니면 B인것이다. 어떤 한 정점이 A로 가면 A와 연결된 녀석들은 B로 가야만 한다. 그런데 B로 갔는데 서로 연결이 되어 있으면 불가한 것이다. 이 부분만 명심하고 문제를 풀면 된다.

나는 우선 이를 복사한다는 개념으로 생각하여 A그룹과 B그룹이 모두 똑같다고 전제를 놓고 시작하였다. 그래서 check를 만들고 이미 사용된 녀석이라면 바로 스킵해가는 식으로 전개하였다. 하지만 사용하지 않았다면 dfs함수를 호출하는데 여기의 인자는 pos는 해당 위치인덱스이고 flag는 위에 말했던 A인가 B인가를 구별하기 위한것으로 초기 값은 크게 중요하지 않다. 

함수에서는 현재 인덱스값에 flag를 주고 그 연결된 간선의 크기만큼 포문을 돌린다. next를 할당하는데 next가 만약 flag와 같다면 같은 그룹에 속한다는 말이니 false를 리턴한다. 

하지만 만약 값이 아직 할당 전이라면 dfs를 다시 리턴하여 위 과정을 반복한다. 

그래서 check[next]의 값이 -1이지만 dfs가 트루를 보낸 경우와  check[next]의 값이 현재 flag와 다르다면 성공한 경우로 간주하고 다음으로 넘어가게 된다. 어떻게 보면 더 쉬운문제라고 할 수 있다. 이전 이분매칭과 다른점이 있다면

그 녀석은 A그룹 B그룹이 명확히 다르기 때문에 check를 2개를 두었다고 보면 된다. 아직 이런문제는 더 많이 풀어봐야 내것이 될 것 같다.

출처 : https://www.acmicpc.net/problem/2146

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/2146.cpp

문제가 상당히 귀찮다. 어려운건 아니지만 상당히 귀찮고 오직 BFS로는 풀 수있으나 오직 DFS로는 풀 수가 없다. 아마 있긴할텐데 엄청 복잡해질거다. 나는 DFS+BFS로 풀었다.

문제는 어떤 섬에서 섬까지 다리를 놓을때 최소한이 되는 값이다. 이는 결국 하나씩 다 해봐야 알 수 있는 것이다.

나는 다음과 같이 접근하였다.

1. 먼저 다리를 놓아야할 모든 엣지를 구한다. (즉, 주위에 0이 있다면 다리가 건설 가능한것으로 보고 큐에 해당 지점을 전부 푸시한다.)

2. dfs를 통해 구역별로 값을 따로 매긴다. 나는 처음 영역을 2부터 매겼는데 그 이유는 1은 이미 입력으로 들어온 값이기 때문에 혼동을 피하기 위함이다. 

3. 1번에서 받은 모든 엣지를 통해 다리를 건설하기 시작한다. BFS를 사용하는게 현명하다 왜냐면 모든 값을 조사할 필요 없이, 최소 값만 알면 되기 때문이다. 

절차는 처음에 해당 지점이 몇번째 구역인지 값을 통해 area에 담고, bridge라는 큐에 담는다. 그리고 큐를 통해 사방을 검색하며 BFS를 진행하면 된다. 

여기서 주의해야할 점이 있다. 나는 메모리 초과로 상당히 애먹었다...

1. 만약 ans(현재까지 최소값)보다 현재 cnt(현재 건설중인 다리 수)가  크다면 이는 의미가 없으므로 종료시킨다.
   (시간 초과 방지)

2. BFS로 영역을 확장할때 0인 값과 다른구역의 값을 한번에 큐에 집어넣고 큐가 다음 반복될때 현재 위치가 다른 값이면 이라는 이프문으로 확인시킬수도 있다. 그러나 이렇게하면 시간 및 메모리가 낭비되므로 나처럼 분할시키는 것이 도움이 된다. 

3. 하다보면 1로 둘러 쌓인 지역이 있을것이다. 이런 경우는 만약 0을 기준으로 동서남 쪽이 1이면 3번이 푸시가 된다. 이건 피하기보다는 일단 담는다. 하지만, 어느 한쪽에서 사용되면 -1로 값을 변경하였기 때문에, 아래의 모든 과정을 스킵하게 해야한다. 하고 안하고는 메모리 초과이냐 정답이냐를 가른다. 매우 중요한데 너무 오랜만에 BFS를 하여 실수를 하였다.

이 부분만 잡는다면 그리 어렵지는 않은 문제이다. 다만 귀찮은 문제인데, 시험용으로는 정말 좋은 문제같다. 이런건 보통 KOI에서 정말 많이 봤었다..

출처 : https://www.acmicpc.net/problem/2161

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/2161.cpp

이 문제는 매우 간단하다. 우선 이 문제에서 가장 먼저 볼것은 N의 최대 크기이다. 그런데 1000밖에 안된다. 

그렇다면 단순 시뮬레이션으로도 값을 찾을 수 있다는 말이다. 왜냐면 1000장일때 500장을 버릴거고 그다음 250장을 버릴거고 그다음 125장을 버리는 식으로 계속 1/2씩 버리게 되니 반복해봤자 lg시간대로 끝나게 된다. 

큐를 사용하면 더 쉬워지는데 큐를 구현하는건 다음에 하기로 하고 STL을 활용하여 풀었다. 

쉬운문제로써 한 10분정도 걸린거 같다.

출처: https://www.acmicpc.net/problem/2188

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/2188.cpp

이번주 내내 공부했던 알고리즘이다. 드디어 문제에 적용시켜보았고 풀었다. 아직 완벽히 내것으로 만든건 아닌것 같다. 그렇기 때문에 나의 이해가 틀릴수도 있다고 생각한다. 

먼저 내가 가장 많이 참고한 사이트는 여기를 들어가면 볼 수 있다.  약 20번정도 읽은 것 같다. 소스는 그냥 외워질정도로 많이 봤다. 

먼저 간략히 설명하면 이분매칭은 두개의 그룹이 있을때 서로 매칭을 시키는데 단순 DFS를 하면 굳이 하지 않아도 될 검사들을 많이 하는데 이를 전부 빼버리고 한번에 연결하고자 할때 쓰는 방법이다. 

인터넷을 찾아보면 참 많은 사진과 글들이 나오는데 나는 나만의 방법대로 쓰겠다.

용도

1. 일단 두개의 그룹이 주어지고 조건에 따라 그룹이 최대의 매칭을 찾아야 하는 경우

2. DFS나 BFS같은 탐색 문제 같은데 시간초과가 나오고, 묹데는 결국 매칭을 찾아 특정 어떤 값을 찾아야하는경우(값을 찾는건 알고리즘과는 별개로 새로운 방법을 도입해야 한다.)

대강 이정도로 이해하고 있으면 용도를 알게 될 것이다. 이 문제는 1번의 경우이다. 

이 문제 역시 결국 축사라는 그룹과 소라는 그룹이 있고 이 두 그룹이 소의 축사 선호도에 따라 매칭을 시켜주는 것이다.  

소스를 보며 자세히 살펴보면 입력은 일반적인 그래프와 동일하다. like에서 -1을 해주는것은 입력은 1부터 들어오지만 나는 0부터 사용을 할 것이기 때문이다. 

그리고 보면 함수 bmp가 있다 bmp는 Bipartite Matching 이라 bpm 인데 잘못쓴거다...

암튼 해당 함수의 목적은 매칭의 수를 검색하여 리턴해주는 것이다. 즉 이 함수의 리턴값이 최대 매칭 수가 되는 것이다. 처음 fill을 사용하여 bmatch를 -1로 초기화하였는데 해당 배열은 한번이라도 이 값이 사용이 되었는지 아닌지를 체크하기 위함이고 처음 호출시 당연히 모든 값이 사용되지 않았기 때문에 -1이 된다. 

그후 n만큼 체크를 하는데 이는 A그룹의 처음과 끝을 의미하게 된다. 각 그룹마다 인덱스 값을 dfs함수에 넘겨주게 된다. 그 전에 chk는 bmatch와 다른데 bmatch는 전체적으로 볼때 한번이라도 사용을 했는지 안했는지를 판단하게 되고, chk는 해당 싸이클에서 사용이 되는지 안되는지를 체크한다. 그러므로 각 인덱스마다 초기화를 해주어야 맞다. 이 차이는 dfs함수를 보면 이해가 빠르다.

dfs함수는 우선 bfs로도짤수있고 다양한 방법이 존재한다. 그러나 어떤 글쓴이의 말에 의하면 대부분의 문제는 dfs로도 풀린다고 한다. 뭐 간혹 bfs를 요구하는 문제가 있다고 하는데 그냥틀리련다...

dfs함수를 보면 처음 if문은 현재 인덱스값이 사용이 되었는지를 판단하게 되고, 사용되었다면 리턴값을 주고 아니라면 사용했다고 체크를 하게 된다. 그리고 현재 인덱스 값에서 연결된 간선을 조사하게 된다.

next는 해당 위치에서 연결된 B그룹의 인덱스 를 의미하게 된다. 

그리고 나오는 if는 우선 bmatch를 체크하는건 한번도 사용이 안되었다면 사용을 함으로써 매칭이 이루어진다는 것을 의미한다. 그게 아니라면 dfs에 bmatch[next] 값을 주어 다시 검사를 한다. 이것이 결국 매칭이 안되는 녀석으로 온다면 매칭이 끝내 성공하게 되는 것이다. 더 깊게 설명하기는 힘들다. 직접 작은 테스트케이스를 잡고 실험해보는게 좋다. 

안에서는 bmatch[next]에 현재 인덱스 즉 pos값을 주어 bmatch가 결국 현재 인덱스와 매칭이 되고 있음을 알려주고 트루를 리턴해준다.  결국 bpm에서는 트루를 리턴을 받으니 매칭이 성공했다고 인식하고 match를 하나 올려주게 된다. 

bpm에서 i가 0부터 시작했으니 1이되면 다시 1을 기준으로 시작한다. 하지만 bmatch는 변하지 않는데 그 이유는 이 녀석은 결국 0번에서 체크가 이루어진 결과를 담고 있다고 보면 되기 때문이다.(즉, 이 녀석이 담고 있는 값은 큰 의미가 없다. 그저 해당 인덱스가 어떤 인덱스와 매칭이 이루어졌다. 이것이 다일뿐이다.) chk만 현재 인덱스를 기준으로 사용되지 않는 결과를 담고 있다고 보면 된다.

결국은 두개의 그룹이 서로 왔다갔다 하는것이다.

상당히 어려운 알고리즘이라고 생각한다.