Red Salmon

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2017.05/1520.cpp

이 문제는 1년전에 틀렸던 문제였다. 결론만 보자면 매우 간단한 문제이다. 아마 1년전에 틀렸던건 작년 초에 내가 메모이제이션을 정의하지 못했던 시절인것 같다.

물론 너무 오랜만에 문제를 풀다보니 오래걸렸다.

먼저 문제의 요점을 파악해보자면 현재보다 낮은 지점으로 가야하고, 최대크기가 500x500이라는 것이다. 높이가 1만이라는건 크게 개의치 않아도 될 것 같다.  뿐만 아니라, 정답이 10억이하의 음이아닌 정수라고했으니 int범위안에 정답이 있을 것이다. 

그럼 이제 문제의 풀이를 보자.

500x500.. 적다면 적고 크다면 큰 매트릭스이다. 아마 일반적 dfs로 접근하면 시간초과가 날 확률이 매우 높다.(그래서 1년전에는 시간초과를 맞았다.)

그래서 BFS로 풀어보니 메모리가 너무 커지는 문제가 발생한다. (큐가 너무 커지는 문제..)

그래서 우리에겐 메모이제이션 개념이 있는것이다. 이미간 지점에 대해서는 더이상 계산을 하지않게 하는 방법!

이방법을 사용한다면 위의 두 문제를 해결할수있다. 나는 DFS로 풀었다.

먼저 memo를 할 배열을 만들고 -1로 전부 초기화를 한다. 이건 가지 않았다는 말이다.

그리고 dfs를 돌면서 만약 이 지점이 이미 값이 있다면 바로 리턴을 한다. 왜냐면 이미 방문한 지점에 대해서는 값이 갱신되어 있기 때문에 더이상 추가적인 계산이 필요없다. 어떤 점이든 정점에 다다르면 1을 리턴한다.

조금 더 풀이해보면 포문에

cnt+=dfs(nx, ny)라고 되어 있는데

이미 간 지점이라면 이미 이 지점에서 몇가지 경우의수로 도착을 하였다. 이걸 알려줄 것이고 없다면 쭉 돌다가 1을 리턴하니 이걸 추가할것이다. 즉 4방향에 대해서 모든 cnt가 더해진다.

그리고 최종적으로 해당 좌표의 cnt값이(목적지까지 가는 가짓수) 나올텐데 이를 memo에 기록해둔다. 그럼 각 지점마다 정점에 도달하는 수가 dfs를 통해 기록이 될 것이고 최종적으로 0, 0에서 출발하여 정점까지 다다를때의 경우의수가 기록되어 정답이 나오게 되는 것이다.

 메모이제이션은 참 간단한 개념이지만, 익숙해지는데 조금 걸리는것 같다. 하지만 한번 익숙해지면 참 써먹을 곳이 많고 특히!! sw회사 알고리즘 필기시험을 준비한다면 반드시 알아두어야 할 개념이다. 특히 삼성sw역량평가의 경우 2번문제에서 몇번 나왔었다. 일반적인 dfs, bfs로는 풀리지않고 메모이제이션을 써야 풀리는 경우. 

뭐 어쨌든 알고리즘은 많이 푸는게 장땡이다.

출처 : 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[][])이  확인을 함수 맨앞에 배치했는데 이러니 간혹 문제가 발생했다. 

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

출처 : 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를 잘한다고생각했는데 지금생각하면 쥐뿔도 못하는게 깝쳤던거같다.