조금만 파해쳐 보면 간단히 접근할 수 있는 ICPC 문제들 (7) - 2008년도 대회 뒷이야기 (3)

Asia - Seoul - 2008/2009 Internet Preliminary - Problem F: Rubik's Cube

문제는: http://acm.kaist.ac.kr/2008/problems/F_Cube.pdf

문제 설명:
Rubik's cube(루비큐브) 2개, A, B가 주어져 있을 때, 같은 cube인지 아닌지를 판별하는 문제입니다.
A와 B가 동일한 cube를 서로 다른, 혹은 같은 point of view에서 본 것이라면 같은 cube이고, 똑같은 모양으로 만들기 위해 조작을 해야 한다면 다른 cube입니다.

문제 접근:
문제 설계 후, 접근방법으로는 두가지가 제시되었습니다.
1. 하나는 주어진 cube의 image로부터 다른 시점에서 본 image를 얻는 함수를 구현하는 방법이고.
2. 다른 하나는 주어진 두 cube에서 서로 동일한 면을 찾고, 이를 기준으로 다른 면들을 훓어나가면서 서로 동일한지 검사하는 방법입니다.

뒷이야기:
사실 이 문제는 예선 B번 문제로 출제될 예정이었습니다.
루비큐브 문제를 내보자! -> 맞추는 문제는 여기저기 있네? -> 그러면 똑같은지 판별하는 문제로 주자 ; 과정을 거쳐 만들어진 문제입니다.
예선문제 솔루션 제작 메뉴얼대로 두명이 서로 다른 방법을 구현하기로 하고, 추석 쇠고 돌아와보니...

1. 구현하기로 한 B모 박사님 曰, '이거 B번문제로 쓰기는 너무 어려운거 아니냐?'
추석동안에 할일 없어서 겜방가서 노트패드로 구현했다고 합니다. 구현된 솔루션을 보니 무려 400줄!

저는 '설마!' 하고 2번 방식을 구현하기 시작했습니다. 150줄정도로 구현은 했는데 디버깅이 안되서 끙끙대다가 결국 포기하고, 노트에 한번 깨끗이 정리한 다음에 다시 구현했더니 한방에 됐습니다. 100줄 조금 넘는 정도로 구현을 했고, 새로 정리하고 코딩하는데 걸린시간은 50분정도...


결국...
'... B번은 아마... 안될거야...'
라는데 동의하고 F번 문제가 되었답니다.

그래서, 경험상 회전함수를 구현하는 것 보다 기준이 되는 면을 잡고 scan하는 방법이 시간과 노력이 덜 들었다. 라고 말할 수 있었습니다.
나름 꽤 잘만든 문제라고 생각하고 있었는데 풀어준 사람이 얼마 없어서 서글픈...



링크: algospot 관련글