Red Salmon

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1967.cpp

이 문제는 다풀어놓고 한참을 틀렸던 문제이다. 어처구니 없이 모든걸 만들어놓고 틀렸다 ㅠㅠ 왠지 작년에 본 삼성 SW역량 시험이 생각났다.. 다만들고 문장하나를 생각하지 못했던...

아무튼 문제는 가장 긴 구간을 찾는것이다. 

당연히 어떤 구간이 긴지 모르므로 전부 검색해봐야한다.

나는 DFS를 활용하였다. 여기서 내가 놓친 부분이 그것이다. 최대 지름을 구하는 문제이므로 2개의 길이만 필요하다. 

그리고 문제에서는 이진트리 느낌으로 보여졌는데, 실제 데이터에는 이진트리가 아닌것들도 많다. 자식노드가 여러개인경우 말이다.

사실 이정도면 미리 문제에서 알려줘야하지 않나..싶다.

알고리즘은 다음과 같다.

1. 벡터를 사용하여 연결된노드와 값을 입력한다.

2. 함수를 호출하는데 인자는 루트노드만 보내준다.

3. 각 루트노드에서 연결된 간선을 전부 탐색하고 그 간선의 값을 더해본다. 

4. 그리고  temp와 val[2]를 활용하여 val[2] 에는 가장 긴 2개의 녀석만 담아둔다.

5. 그 2개의 값의 합이 ans보다 큰지 비교를 한다.

6. 리턴은 그 2개에서 가장 긴녀석을 리턴한다.

이 과정이 반복이되면 딱 한번 모든 노드를 검색하게 되고 자연스레 답이 담기게 된다.

뭐랄까..예전엔 이런 DFS가 조금 힘들었는데 이젠 뭐...그냥 술술 풀린다. 그래도 실수한건 실수한거다. 문제를 잘 읽어야겠다.

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

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

이 문제는 참 그렇다. 이렇게 많이 틀린 문제가 있엇던가 싶다. 

그래도 이번엔 정답을 맞았다. 1년전에 도전했고 9개월전 6일전 1일전 도전하여 결국 풀어냈는데 생각해보면 이 단순한걸 왜틀렸을까? 왜생각을 못했을까 싶다..

위상정렬이라는것이 필요하다고 하여 공부해보았고 참 요긴하게 쓰이겠구나 했지만, 위상정렬이라는 개념을 모르더라도 DP와 dfs만 안다면 풀 수 있는 문제였다. 

결국은 최장길이를 구하는 문제인데 dfs로 전부 탐색해서 구했다.

풀이는 다음과 같다.

1. 인풋을 입력받지만 나는 벡터에 값을 담을때 반대로 담았다.

2. 찾고자하는 건물번호를 입력을 받으면 그 지점에서부터 시작을 하였다.

3. 그리고 dp[now] 에 값이 있다면 그값을 리턴하고 아니라면 dp[now]에 현재 arr[now]값을 주고 계산을 시작하였다.

그런데 여기서 계산을 한다.

4. 포문을 열고 현재 녀석과 연결된 녀석을 살펴보고 해당녀석을 다시 dfs로 작업을 시작한다.

그럼 결국 여기저기 찾으러 다닐텐데 만약 dp[now] 값이 존재하면 이미 만든 값이므로 그 값을 사용할테고 그값을 사용하면서+val이 크다면 그 구한값에 +val만하여 사용하고 아니면 그냥 쓰는식이다. 

간단한 문제라고 생각되는데 왜이리 해맸는지 모르겠다. 

가만보면 난 이런 dp+dfs에는 알면서 자주틀리는거같다. 나중에 다시풀어보거나 비슷한 문제를 다시 접해봐야겠다. 

출처 : 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에서 정말 많이 봤었다..