프로그램을 배웠으나 알고리즘 시험을 봐야 한다면. #35

그 동안 회사일이 바빠서 글을 못썼습니다.

일단 최근 시험이 오전 오후 2문제씩 4문제였는데 지난번에 2문제만 살펴봤고

오늘 나머지 2문제 중 1개를 생각해 보겠습니다.

 

시험을 보신분 들이 이 글을 보실것 같지는 않은데 재수?나 다음 시험을 준비하시는 분은

꼭 기출문제를 구해보세요. 모든 시험의 기본은 기출문제입니다.

 

남은 2문제 중 바이러스 관련 문제가 있었지요?

이 문제는 전형적인 BFS문제 였습니다.

 

바이러스를 시작점으로 BFS를 돌려서 더 이상 갈 수 없는 때 까지 돌리면 되고

바이러스가 복수 개이니 각각 돌리면 되는 문제입니다.

 

하지만 이 문제는 벽을 쌓을 수 있으니 그 벽의 위치에 따라 바이러스가 퍼질 수 있는

범위가 달라지게 됩니다.

 

여기서 많이 실수를 하는 것이 현재의 바이러스 위치를 보고 벽을 쌓을려고 하면 너무 어려운 문제가 됩니다.

판의 크기가 최대 8x8 인것도 그렇게 하지 않아도 된다는 것을 알려주는 것입니다.

 

현재의 바이러스 갯수나 벽의 위치에 따라 달라지겠지만

(8x8)C3 = 약 4만가지경우, 각 위치에서 벽을 쌓을 위치를 3개를 고르고 (조합이겠지요?)

그 경우에 각각 BFS로 바이러스를 퍼뜨려서 보고 남은 위치가 가장 많은 것이 답입니다.

 

바이러스 위치에 따라 바둑두는 것 처럼 벽을 쌓아 보려고 하면 너무 어렵게 접근하는 하는 것입니다.

 

일단 위처럼 풀고 시간 초과가 되면 Memoization을 이용하여 시간을 줄이는 방법을 생각하면 됩니다.

여러가지 아이디어가 생각이 나지만 이 시험은 이렇게만 해도 Pass가 되었을 것입니다.

 

#삼성_소프트웨어_역량_테스트