Red Salmon

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.02/7562.cpp

칸을 이동하란다. BFS라고 말하고있는것과 같다.

다만 이동할수있는 범위가 생각보다 많다. 하나하나 다 해주라는 말이다. 참 귀찮게 하는 문제이다.

문제자체는 어렵지 않다. 

bfs몸풀기 문제로써 20분 컷으로 풀어보면 좋을것 같다.

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

정답 : 

문제를 보면 인풋이 천만개이다. 그리고 더 읽어보면 10,000보다 작거나 같은 자연수라고 한다. 즉, 10000개의 숫자들을 가지고 천만개를 입력하게 되니 반드시 중복이 있다는 말이다. 

이 부분을 캐치해야 문제를 풀 수있다. 나는 맵을 사용하여 풀었는데, 맵을 사용하지 않고도 풀 수있다.

맵을 사용하지 않는다면 어차피 숫자는 10000개니까 bool 함수를 써서 인풋이 들어오면 그 부분을 참으로 맞춘다.

그리고 int배열을 하나만들고 해당 부분을 카운팅해준다.

입력이 끝나면 for(1만) 을 돌려서 bool이 참이면 그에따른 int배열의 개수만큼 그 수를 출력해주면된다. 

결국 입력은 천만번이지만 정렬도 없고 그냥 포문 1만번으로 답을 구할수있다.

그리고 이런 문제의 경우 인풋도 출력도 엄청많은데 cin, cout보다는 scanf와 printf를 센스있게 써줘야한다. 

속도면에서 엄청난 차이가 있다.

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.02/2072.cpp

처음에 이문제에 기교를 부려보려고 했다. 무배열로 풀어보려고했으나, 생각외로 소스가 너무 복잡해져서 포기했다.

먼저 나는 인풋이 들어올때마다 오목판에 돌을 배치하였고 그 돌을 가지고 승부를 판별하도록 설계했다. 

이렇게 해야 누가 먼저 승리하는지 알 수있다.

승부가 결정된 시점부터는 인풋이 들어오면 그냥 들어오는것이지 어떠한 이벤트를 주는건 아니다.

역시 주의해야할점은 승부가 나지 않는 경우가 있고 이때 -1을 출력해야하며, 6개이상의 돌로 이루어지면 그것또한 이긴것이 아니게 된다.

이 부분만 체크해주면 간단히 끝나는 문제이다. 

그리고 이런문제의 특성상 설계를 잘못하면 소스가 하염없이 길어지게 마련이다. 소스가 길어진다는것은 틀릴확률이 기하급적으로 증가한다는 말이기도 하다. 

그렇기 때문에 최대한 함수로 표현하고 깔끔하게 코딩하도록 노력해야한다. 물론 나보다 더 짧게 만든사람도 많다.

좀 더 생각해보면 나도 더 줄일수있을것 같지만 그만하련다.

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.02/2573.cpp

참으로 진부한 bfs문제이다. 단, 주의해야할점이 분리가 되지 않는 경우도 있다는 점이다. 

난 이문제를 엄청 해맸는데 그이유는 단한글자 때문이었다. 그 한글자의 오류를 찾기까지 정말 오래걸렸다.

정답을 맞긴하였지만, 만약 시험을 보고있는 중이고 알고리즘에 대한 확신이 있는데 오답이라면 수정하기보다는 그냥 새로 처음부터 짜는게 훨씬 득이 될것이다.

물론 알고리즘 자체가 불확실하거나 빈틈이 있다면 새로 짜는것은 오히려 독이 될 수 있다.

암튼 이런문제는 2개의 배열을 준비해두고 이것들을 스위칭 시키는 방식으로 나는 자주 푼다. 물론 다른사람들은 다르게 풀겠지만 이것은 내스타일이다.

그래서 배열이 2개에 카피하는 배열을 두는데 여기에는 어느정도 리스크가 있다.

그러나 문제가 bfs를 요구한다면 이 방법은 거의 다 통과이다. 현재까지 bfs이지만 이런방법을 썼기때문에 TL이나 오답이 나온적은 없다. 

만약 틀렸다면, 알고리즘 자체가 틀렸을 것이다.