Red Salmon

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

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

이 문제는 처음 읽고 매우 당혹스러웠다. 벽을 부순다니..??? 하지만 벽을 1번만 부신다고 한다. 근데 더 생각해보니 한 100번쯤 구해도 결국 똑같은 것이다. 즉 메모리제이션이다.

젠장 정답률이 저조한 BFS는 무슨 공식마냥 3차원배열을 쓰면 만능키처럼 다풀린다.

역시 이문제도 똑같은 방식으로 전개하였다. 

벽을 부술때와 안부술때를 따로 나눠 전개하면 된다.

처음에는 안써보고 하려고 계산을 해봤으나, 택도없었다. 방식은 조금씩 다르게 코딩했지만, 이건 내가 아직 초보단계를 막 벗어나고있기 때문이고, 점차 정형화되고 깔끔해진 코드가 될 것 같다.

즉, 더많이 풀어야겠다.

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

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

이 문제 역시 BFS문제이다. 아 정말 많이 푸는거 같다. 매일 풀고있다.

이문제는 내가 자주하는 실수를 하였는데 문제를 제대로 읽지 않았다. 그래서 참 여러번 코딩했다. 중간에 포기하고싶었다 ㅠㅠ

암튼 go라는 명령에는 1,2,3 중에 한칸을 움직일수 있으며, 방향역시 4방향으로 그때마다 값이 달라진다.

역시 메모리제이션이 필요한대, 초기에 dp만을 활용하여 최소값을 갱신하는 방식을 사용하니, 수가 커지니 오류가 발생했다.

이를 완벽히 해결하는 유일한 방법은 아마도 메모리제이션이 아닐까 싶다. 

내가 오류가 발생한 이유는 방향을 고려하지 않았기 때문이므로, 방향을 고려하여 [][][4]를 만들어 각 방향별 최저값을 갱신하는 식으로 하였다. 그랬더니 정답이 나왔다. 

이문제에서 go는 방향이 맞아야먄 진행 할 수 있으므로 초점을 맞춰야하는건 방향인 것이다.

출처 : 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/2636

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

과거에 분명 풀었던기억이 있는데 다른 문제인가보다. 

이문제 역시 공기와 노출되면 치즈가 녹아없어지는데 단순히 치즈에 구멍이 있는것은 공기에노출되지 않은것으로 간주한다.

또한 출력은 다없어지기전에 몇개였는지를 물어보고있다.

풀이를 생각해보면 입력이 최대 100이므로 100x100 이 검색이라고할때 하나씩 사라진다고해도 100x100x100이므로 n^3으로 충분히 풀 수 있는 시간이다. 

그래서 나는 매번 스캔을 하면서 공기와접촉한 치즈영역을 찾고 해당영역을 지우는식으로 풀었다. 그리고 시간내에 간단히 풀렸다.

큐를 두개를 두어 풀었는데 이런 손이 많이가는 문제가 시험문제내기 좋은 문제라고생각한다.

왜냐면 계산 실수나 작은 손실수가 답을 해매게 만들기 때문이다.

많은 연습만이 이런실수를 줄일수있다.