[백준] 새로운 게임 : 17780 Python

나에게는 너무 어려운 구현 그 자체인 문제였다. 구현 문제를 풀 때, 항상 고민인 점이 '시간, 메모리 통과할까?'이다. 내가 아직 경험이 부족하여 시간에 대한 정확한 확신이 없어서 이런 일이 있는 것 같다. 이 문제를 풀 때도 손 코딩 단계에서 이렇게 해야 하나? 아니면 이렇게? 이 고민으로 한 시간은 족히 소모한 것 같다. 결국 손 코딩을 완전히 끝내지 말고 일단 그냥 풀어보자는 마음으로 키보드를 쳐봤는데 막상 치기 시작하니 금방 푼 느낌도 드는 것 같다. 

문제를 간략히 설명하자면, 말그대로 재원이가 만든 게임을 진행하고, 게임 진행조건을 도달했을 때 소요된 턴을 출력하는 문제이다. 결국은, 문제에서 설명하는 게임을 구현해내는 문제이다.

게임 규칙은 문제에서 읽어보는 것이 가장 좋을 것 같고, 결국 이문제에서 중요했던 것들은 게임을 구현해내기 위한 여러 정보를 어떻게 저장할래? 인 것 같다. 그 이유는, 게임을 구현해내기 위해 필요한 정보가 엄청 많았고(체스판의 색깔, 움직이는 돌의 순서, 움직일 수 있는 돌의 번호, 돌의 방향, 같은 위치의 돌의 개수) 이로 인해 시간 초과가 자연스럽게 신경 쓰였기 때문이다.

일단 나는 문제를 해결하기위해 총 세 개의 자료 공간을 사용했다.
1. 체스판의 색깔을 알려줄 2차원 배열 : arr 
2. 돌의 위치 및 쌓여진 돌들의 번호(개수) : table
3. 돌의 번호순서대로 돌의 위치, 방향을 저장해 놓는 리스트 : stone

변수 셋팅

N와 SN 은 문제에서 제공해주는 변수로 arr, table, stone을 만드는 데 사용했다.

이렇게 변수 셋팅을 해놓은 상태에서 나의 아이디어는
1. 항상 stone의 번호대로 돌들을 움직인다.
2. stone을 통해 table의 r, c위치를 확인하는데 가장 밑 의돌이 현재 stone의 돌과 같으면 움직인다.
3. arr을 통해 테이블의 색깔을 확인하고 색깔조건에 맞는 위치로 돌을 움직인다.
4. 움직임이 끝난 후에 table과 stone의 돌 정보를 최신화한다.
이런 방식이였고, 시간과 공간 메모리가 걱정이었지만 일단 구현해보자는 마음으로 시작하였다. 

코드

구현하면 이렇게됐고, 생각보다 시간은 정말 얼마 걸리지 않았다.

지금은 그나마 정리를 한것이고 실제 문제를 풀고 제출할때는 어마어마한 스파게티 코드였다. 구현문제를 풀때 손코딩을 어느정도로 하고 코드구현을 해야할지 이 중간점을 찾는것이 중요한 것 같다.

구현 문제를 아직 많이 안 풀어봐서 그런지 시간도 많이 걸리고 접근 방법 또한 매우 까다로운 것 같다. 역시 답은 많이 풀어보는 것 밖에 없는 거겠지...?

오늘도 하루한개 알고리즘 파이팅이다,,,!

 

문제출처 : 백준  https://www.acmicpc.net/problem/17780