2019-06-25 19:06 작성됨

문제 풀이 과정

문제 파악

#과 .으로 이루어진 게임판에서 ㄱ자 모양의 블럭을 퍼즐처럼 채우는 경우의 수를 찾는 문제이다. 그래프와 기하 문제에 약해서 이런 문제는 보기보다 어렵게 느껴졌다. Brute force를 활용하는 문제이기 때문에 한 블록을 빈칸에 넣을 때마다 새로운 문제로 나뉘는건 명확하게 느껴졌다.

문제점

1번 문제도 그렇고 경우의 수를 세는 Brute force 문제는 중복해서 세는 경우를 반드시 피해야 한다. 시간관계상 구현은 하지 못하고 대략적인 해결책만 생각했을 때 중복을 피하는 법이 바로 떠오르지는 않았다.

문제 풀이 과정에서의 핵심 아이디어

• 중복을 제거하기 위해 좌상단의 빈 공간을 가장 먼저 확인하는 것
• 좌상단의 공간으로 범위를 좁힘으로서 네 개의 블록만 확인하는 것이 가능해짐
• 블록의 형태를 나타내기 위해 배열을 통한 상대좌표 구현
• 하나의 함수(set())으로 블록 채우기와 비우기에 모두 활용

추가 학습

• 이중 벡터
• C++ 참조자