Problem Solving - 1. 퍼즐 맞추기(BFS/DFS)

본 문제는 프로그래머스 연습문제중에 하나이다. 이 문제를 풀면서 기억해 두면 좋을만한 사항들을 많이 발견했기 때문에 포스트로 작성하게 되었다. 

처음 문제를 읽고 주어진 상황을 추상화하고 단계화 하는 것은 성공적이었다. 그러나 다음의 3가지 이유로 인하여 모든 테스트케이스에 대해서 맞추는데는 시간이 좀 소요되었다. 

 

1. Rotate와 Translation의 순서의 중요성

문제에서 주어진 형태를 좌표를 통해 수치화 하고 이를 회전 변환 행렬, 평행 이동등을 통해서 답을 구해야 겠다고 처음부터 생각하였다. 그러나 평행이동을 한 후 회전 변환을 하는 것과 회전 변환을 한 후 평행이동을 수행하는 것에는 큰 차이가 있었다. 평행이동을 먼저 하고 그 후 회전 변환을 하게 된다면 회전의 중심이 되는 점이 회전하는 각도에 따라 변하게 된다. 그러나 회전 변환을 먼저 한 후 평행이동을 하게 되면 동일 한 점을 원점으로 이동 가능하게 된다. 

 

2. 함수에 매개변수로 Mutable한 객체를 전달할 때

C++에서와 마찬가지로 파이썬에서도 함수에 매개변수로 Mutable한 객체를 전달 할때 주의 해야 한다. Call by Reference가 되기 때문에 함수에서 객체가 변하면 함수 밖에서도 그 변한것이 그대로 유지된다. 더나아가서 Python에서의 List에 +=과 +, 그리고 append를 사용할 때 주의해야 한다. 예를들어 다음과 같은 코드를 보자 

a = [1, 2, 3, 4, 5]

def func(arr):

     arr += [7]

     arr.append(8)

     arr = arr + [9]

func(a)

print(a)

위와 같은 코드의 결과는 무엇이 될지 예상이 되는가? 

정답은 [1,2,3,4,7,8]이다. arr += [7]과 arr.append(8)은 모두 기존의 Mutable한 객체를 수정하는 Method 이기 때문에 함수 밖에서도 그 기능했던 값들이 유지된다. 그러나 arr = arr+[9] 의 경우에는 arr와 [9]를 합친 새로운 객체를 만드는 함수 이기 때문에 밖에서 기존의 값을 호출하여도 그 작동이 유지되지 않는다. 

 

3. 동일한 퍼즐인지 판단하는 로직으로 Degree는 적합하지 않다. 

처음의 시도 평행이동과 회전변환의 조합으로 회전했을 때, 동일한 블럭을 찾는 것이 막히고 나서 각 요소들의 Degree를 이용해서 그래프의 동치를 알아보려고 했다. 그러나 이러한 시도는 쉽게 반례를 찾을 수 있는 방법이었다.