백준 14500 테트로미노 문제 파이썬 해설/코드

코드만 보실 분은

GitHub - Rhyankwon/algorithms

우선 문제 설명 고고

문제는 보기보다는 간단하다. 주어진 배열에서 테트리스 모양처럼 숫자 네개를 잇는 방식으로 만들 수 있는 조합들이 있는데 각 조합 내 숫자들의 합중 가장 큰 값을 리턴하면 된다.

내 생각에는 이 문제를 보고 가장 처음으로는 사람들이 다들 테트리스 모양대로 배열을 미리 만들어두고 매치시켜가면서 풀어야할거라고 생각할 것 같다. 나도 그랬고. 그리고 사실 이 문제는 구글링을 좀 하면서 푼 문제라서.. 여러 풀이를 봣는데 그렇게 푼 사람도 많다. 그런데 나는 그렇게 풀기가 싫어서 다른 풀이를 찾아봤고 그렇게 오늘 풀이..처럼 코딩을 하게 됐다.

의외로 이 문제는 dfs를 사용할 수 있는 문제이다. 각 요소에서 상하좌우로 이동하고, 거기서 또 재귀호출하는 방식으로 4회 dfs를 호출하면서 값들을 더하면 각 배열마다 만들 수 있는 테트리스 모양대로 값들을 더해볼 수 있다. 자세한 설명을 원하면 아래 블로그를 보면 이해가 쉽다.

백준 14500 테트로미노

아무튼 그렇게 매 요소마다 4회씩 반복하면서 값을 비교하면 답을 찾을 수 있다. 그리고 이건 맨 아래에 링크로 걸어둔 블로그에서 참고한 최적화팁인데, 전체 배열에서 가장 큰 수를 미리 저장해둔 뒤- 만약 지금까지 탐색하면서 더해진 값에다가 앞으로 더할 나머지 값들이 모두 '전체 배열에서 가장 큰 수'여도 이미 지금 나온 답이 더 크다면 굳이 거기에서 파생될.. 블락들은 탐색해보지 않아도 된다. 전형적인 가지치기! 말이 어려울 수 있지만 맨 위에 내 깃허브 링크에 가면 코드를 보면서 공부할 수 있을 것 같다.

테트리스 어쩌고 하는 문제가 나오면 항상 뭐랄까.. 매번 [[1,0], [1,0], [1,1]] 이런식으로 미리 테트리스 모양을 만들어놓고 풀었었다. (역시 이 문제를 검색해보면 그렇게 푼 사람들이 dfs를 활용한 사람보다 훠어얼씬 많다) 그리고 이번에도 그렇게 풀어야되나 싶은 생각이 들었는데.. 사실 이거는 음. 첫번째, 그렇게 풀고 싶지가 않았고 두번째는 그렇지 않은 방식으로는 내가 바로 풀 수가 없었다. 그러다가 이 풀이를 봤을때 딱 감이 왔다. 아 이게 내가 원하던.. 풀이구나.. ㅋㅋㅋㅋㅋㅋㅋㅋ 아무튼 재귀도 스택을 사용하니까 이 문제도 잘 하면 스택으로 풀 수 있을 것 같다. 가령 스택을 미리 선언해두고 하나를 뺄 때마다 주변 네개(중 아직 탐색하지 않은 것들)를 모두 스택에 넣고, 다시 빼고.. 뺀 값은 길이 4짜리 다른 스택에 쌓아가면서 꽉 찰때마다 값 비교하고..? 될지 않될지 안 해봐서 모르겠지만 해볼 분은 그렇게 해봐도 될듯하다. 안되도 제 탓은 아닙니다,, ㅋㅋㅋㅋㅋ아마 될 것 같은데 저도 재귀를 스택으로 바꾸려고 시도해봤다가 낭패를 봤던 경험이 있어서,,ㅋㅋㅋㅋㅋㅋ 재귀로 푸는게 쉬운 문제가 있고 그 반대인 경우도 있으니까.

삼성 sw 역량 테스트에서 나온 문제라는데 역시 삼성인가. ㅋㅋㅋ 구현문젠데.. dfs를 쓰면 되게 해놨고.. 또 더럽지도 않음. 백준 정답률은 35%이다.

내가 본 풀이는 아래 블로그에서 참고했다. 보고 그대로 따라서 풀진 않았지만 처음부터 끝까지 이해한 뒤 푼거라, 풀고나서 보니 사실상 거의 똑같은 코드가 됐다. 최적화 부분이 가장 마음에 든다.

[파이썬]백준 14500 테트로미노