[백준] 14500번 : 테트로미노 (Java)

14500번: 테트로미노

 

📚 문제 한 줄 요약

주어진 테트로미노(4칸의 연속으로 이어진 도형) 모양으로 계산한 수의 합의 최댓값 구하기

 

📚 문제 포인트 : 어떻게 주어진 테트로미노 모양으로 계산한 수의 합을 전부 탐색해볼 수 있을까?

 

📚 풀이

위 질문에 대해 나는 완전 탐색으로 풀기로 결정했다.

주어진 도형은 총 5가지로, 회전, 대칭한 모양으로 탐색할 수도 있다.

회전 대칭까지 고려하면 고려해야 하는 모양은 아래와 같고, 총 19가지이다.

테트로미노로 수의 합을 탐색해야 하는 경우의 수

이 경우의 수를 모두 탐색할 때 실행 횟수를 계산해보니,

(배열의 최대 크기) x (테트로미노 모양으로 합 구하기) x (테트로미노 경우의 수)

= (500 * 500) * 4 * 19

약 2*10^7번이었고 완전 탐색으로 풀어도 시간 초과가 나지 않을 것이라 판단했다.

제한 시간이 2초 Java언어인데 10^8회를 넘지 않기 때문이다.

 

위와 같은 아이디어로 푼 코드는 아래 링크에서 볼 수 있다.

GitHub - nhee0410/Coding-Test-Study: 코딩 테스트 문제 풀이 및 업로드

 

📚 느낀 점

1. 시간제한을 걸고 문제를 풀어서 맞추는 것에만 집중했더니 효율은 전혀 고려하지 못한 부분이 많고 때문에 코드가 너무 길어졌다. 같은 완전 탐색이라도 여기서 중복되는 코드는 줄여서 좀 더 간결하고 효율적인 코드를 짤 수 있을 것 같다.

2. 4칸인 정사각형이 변끼리 연결(상하좌우)이라는 정보에서 그래프 탐색으로 풀 수도 있겠다는 힌트를 얻을 수 있었고, 완전 탐색 외에 그래프 탐색으로도 도전해 봐야겠다.