Red Salmon

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

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

이 문제는 정답률이 21퍼센트로 낮길래 풀어봤다. 간단해보였는데 그렇진 않았다. 먼저 처음에는 stack을 써서 해결하려고했다. 그런데 입력의 최대가 100만이기 때문에 만약 <가 많다면 매우 곤란할것이다. 

그래서 아예 list를 활용했는데 굳이 구현하지 않은 이유는 구현을 할 수 있고, 시간도 오래걸리기 때문에 STL을 사용했다. 다만 조금 해맸던것은 -를 할때 글을 지워야하는데 iter값을 어떻게 설정해야 할지 참 난감했다.

나는 우선적으로 iter를 한번 뒤로가게하여 숫자를 가르키고 다시 삭제하게 하였다.

STL에서 자동으로 비었거나 잘못된 영역을 참조하면 -1을 리턴해주면 참 좋겠다 ㅠㅠ

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

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

이 문제는 DFS로 풀었는데..풀었지만 이해가 되지 않는다. 왜 정답인지 모르겠다. 분명 느린 답안인데...

알고리즘은 다음과 같다. A가 B를 신뢰할때 B를 해킹하면 A가 해킹되므로 입력을 반대로 받는다.

그리고 모든 컴퓨터에 대하여 DFS를 구해 몇개나 연결되어있는지 확인하는 방법인데, 매 진행할때마다 chk를 초기화 해야 하며, 중복도 심하게 일어난다. 그런데도 불구하고 정답이 나온게 신기하다.

암튼 dfs를 통해 몇단계까지 갔는지 리턴하게 되고 그 값을 sava라는 배열에 담고 그중 최고값을 찾아 다시 처음부터 검색하여 최고값과 같을때만 출력하게 하면 된다.

처음에 if(chk[][])이  확인을 함수 맨앞에 배치했는데 이러니 간혹 문제가 발생했다. 

생각해보니 이렇게 하면 중첩이 발생 할 가능성이 생긴다. 노드가 얽혀있을때 저런 표현은 중간에 값을 사라지게 할 가능성이 농후하다. 저러면 안되겠다고 느꼈다.