이 블로그를 작성하는 지금 내 심정은 너무 진이 빠진 느낌이다. 골드5 수준에 문제고 뿌요뿌요 게임을 모티브로 만들어진 코딩 테스트 문제이다. 시뮬레이션 타입에 문제인데 DFS 까지 포함된 단순하지만은 않는 문제이다.
게임의 룰은 간단하다, R, G, B, Y, P 로 이루어진 레터들만 있는 12 * 6 필드안에서 하나의 레터가 상하좌우로 4가지 이상 모였을때 터져야 하며 터짐과 동시에 그 위에 있던 다른 뿌요들은 아래로 떨어진다. 이 과정을 반복하여 마지막에 몇가지에 뿌요가 터졌는지를 출력하면 된다.
사실 문제만 읽었을때 구상하는거는 빠르게 구상했었다. 상하좌우 (DFS) 방식으로 써칭을 하여 4가지에 연결된 뿌요를 찾고 터진 뿌요 위에 남아있는 뿌요들을 밑으로 내리는걸로 코드를 짰다. 분명히 내가 원하는데로 구현이 됐는데 답이 틀려서 읽었더니 조건중에 내가 자세히 안본 조건이 있었는데,
"터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다."
이 말은 즉, 일반적인 DFS 방식으로 하나하나 서치해주는게 아니고 아예 모든 필드에 모여있는 뿌요들을 전부 터트려주고 위에 있는 뿌요들을 내려줬어야 했던것이다. 이 조건을 무시하게 되면 완전히 틀린답이 나온다.
이 순서로 코드가 진행이 됐었는데. 먼저 첫번째부터 뿌요를 발견하면 pop_all() 을 사용해가지고 그 시작 index부터 모든 뿌요들을 대상으로 dfs 를 해주었다. 그리고 dfs 리턴결과 모여있는 뿌요가 4가지 이상일 경우에는 표시를 해주었고, 성공했다는 의미에 flag 를 리턴해주었다. 그리고 여기서 중요한 reshape() 부분이 있는데 이거는 구상하는 사람마다 다 다른 스타일로 구현을 했던거같다.
내가 생각한 reshape() 방법은 가장 밑에서부터 시작해서 빈칸이 있을경우, 그 빈칸이 있는 column 을 기준으로 위로 쭉 올라가서 뿌요가 있는 공간과 없는공간의 위치를 바꿔주었다. 그 결과 깔끔하게 코드가 나왔다.
이렇게 쓰고나니 굉장히 간단해 보이고 쉽게 푼거 같지만 내가 너무 애를 먹었던 부분은 Solution() 파트안에서 while() 룹을 안써줬던것이다. 그리고 reshape() 을 pop_all() 안에 넣었어가지고 필드를 재구성 하는 단계에서 테스트케이스중 뭔가를 놓쳤었던거 같다. 생각해보면 while() 룹을 하는 이유가 뿌요가 전부 없어질때까지, 혹은 터지는게 불가능한 잔여 뿌요가 남을때까지 계속 돌리는건데 그냥 일반적인 for 룹으로 끝낼려했던게 원인 이였던거같다. 그 외에 구성이랑 구현은 정말 잘했다고 생각하는데 저런 디테일이 자꾸 부족한거같아서 너무 아쉽다. 만약 이게 실제 코딩 테스트였다면 나는 저 while() 룹 하나때문에 시간을 아마 전부 날렸을거다...
배운점:
1. 문제를 잘 읽기
2. 디테일 놓치지 않기
