Red Salmon

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

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

이 문제 역시 BFS 문제이다. 뭐 DFS로도 풀릴지는 모르겠다.

문제를 처음에는 다익스트라로 접근하였으나 다익스트라로는 몇가지 문제에서 해결이 난해하여 모두 지워버렸다.

그 후 생각을 해보니 해당 지점마다 몇의 무게가 가능한지 값을 매긴 후 그 값을 초과하는건 전부 그값으로 만들고 새로들어오는 값이 크다면 갱신하는 방식을 쓰면 간단할것 같았다.

어쩌다보니 다시 코드가 다익스트라와 조금 비슷한 구도가 되었는데, 결국은 기존값보다 크면 갱신하고 작으면 무시하면서 현재 w보다 새로운 w가 크면 다 깍아버리는 식으로 진행한다. 어차피 한계를 넘으면 옮길수 없기 때문이다. 

생각보다 너무 오래 해맸다. 거의 2시간은 걸린거 같다. 다익스트라를 어떻게든 살려볼려고 하다 망했다.

과거 교수님이 한번 더러워진 옷은 아무리 빨아도 더럽다고 하며 코드도 그렇다고했는데, 정말 그런거였다. 그냥 새로사는게 깔끔한것이다.

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

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

요즘 BFS에 푹 빠져있다. 부족함을 느끼고 엄청나게 푸는 중이다. 하지만 속도가 굉장히 느리다..

속도향상에 힘써야겠다.

암튼 이 문제는 BFS로써 메모리제이션이 필요한 문제이다. 왜냐면 원숭이가 말처럼 뛸수도있고 안뛸수도있으며, 횟수마저 제한되어 있고, 언제뛸지 모르기때문이다. 그래서 모든 경우에 대한 체크를 해줘야 한다.

그래서 3차원배열로써 확인하게 한다. 

모처럼 한번에 정답맞은 문제이다.

출처 : https://algospot.com/judge/problem/read/CLOCKSYNC

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/AOJ%20CLOCKSYNC.cpp

이 문제는 DFS문제이다. 완전탐색을 해도 4^10 정도로 풀 수 있다. 처음 이문제를 봤던게 아마 2년전쯤일것이다. 정말 멘붕을 하며 어렵다 생각했었는데 이제보니 별것도 아니었다.

키워드는 다음과 같다.

시계를 4번누르게되면 원위치가 된다. 그러므로 모든 시계를 한번씩 눌러본다.

그렇다면 간단히 이런 계산이나온다

for(i<4)

   시계 버튼 누름

for(i)

  변화

이런식이 되는데 즉 처음 포문은 시계버튼을 몇번 누르는가 이고 그아래는 변화를 주는것이다. 먼저 변화를 주지 않는 이유는 시계를 누르지 않을 가능성도 있기 때문이다. 물론 먼저써줘서 결국 4번을 누르면 원위치되게끔 해도 된다.

몇번째 시계버튼을 누를지는 dfs함수의 인자로 넣어주게 된다. 그래서 +1씩하면서 10이되면 검사하고 출력하게 하면 된다. 

당시 나는 DFS/BFS를 잘한다고생각했는데 지금생각하면 쥐뿔도 못하는게 깝쳤던거같다.

출처 : https://algospot.com/judge/problem/read/BOARDCOVER#

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/AOJ%20boardcover.cpp

이 문제도 약 1년만에 드디어 풀었다. 

풀고나서 생각해보니 1년전에도 거의 다 풀었었는데 마지막 실마리를 찾지 못했던 것이었다. 

3점이 있는 도형을 어디를 기준으로해서 만들것인지인데 탐색을 왼쪽에서 오른쪽으로가고 위에서 아래로 가기때문에 거기에 초점을 맞추고 구현을 해야 하는데, 자꾸 다른 모습으로 하다보니 정답이 나오지 않았던 것이었다.

하... 지금이라도 알아서 참 다행인 실수이다. 

결코 어렵지 않았으나, 내가 간과한 실수가 문제였다.