티스토리 뷰

Study/Algorithm

02. BOARDCOVER

jhin.lee 2019. 3. 3. 16:14

알고리즘문제해결전략 p159



문제


게임판 덮기 (문제ID:BOARDCOVER, 난이도 하)

알고스팟 링크



풀이


나는 2차원 입력값을 브루트포스로 뭔가 시뮬레이팅 하는 문제가 제-일 싫다.

그래서 원래 이 포스팅을 시작하면서 한번 풀었던 문제도 다시 풀려고 마음 먹었는데

이 문제는 그냥 옛날 코드를 조금 손보기만 했다.


아이디어는 좌상단에서 우하단으로 좌표를 이동시키면서 빈 칸이 있으면 재귀호출을 하는 방식으로

4가지의 블럭 모양의 기준을 좌상단 좌표로 맞추는게 핵심이다. (위나 왼쪽으로 삐져나가지 않는 방법으로)

이렇게 했을 경우에 항상 한번 지나온 좌표는 더 이상 신경 쓸 필요가 없기 때문에

한번의 DFS로 모든 경우의 수를 다 찾을 수 있다.


조금 깔끔하게 코드를 쓰기 위해서 '.' 과 '#'을 각각 True와 False로 치환해서 풀었다.

책에서는 배열에다가 블록의 모양을 구성하는 좌표를 미리 선언하는 방법을 사용했는데

코드가 조금 더 깔끔해 질 것 같긴 하지만 큰 이익이 있는 건 아닌것 같아서 수정하지 않았다.

리턴값을 더하는 방식이 아니라 전역변수에 더해주는 방식을 사용했다.



코드


'Study > Algorithm' 카테고리의 다른 글

06. FANMEETING  (0) 2019.05.27
05. FENCE  (0) 2019.05.13
04. QUADTREE  (0) 2019.03.03
03. CLOCKSYNC  (0) 2019.03.03
01. PICNIC  (0) 2019.03.03
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함