23.04.11 파이썬 코딩 퀴즈#214 아이템 줍기 (프로그래머스 스쿨)

이번 문제는 아이템 줍기 문제이다.

그런데 문제가 좀 특이하다. 위와 같이 전달받은 도형은 다각형이다.

정확히 말하면 몇개의 사각형들이 겹쳐진 형태이며, 캐릭터는 다각형의 둘레를 따라서 이동한다.

만약 위와 같이 겹쳐진 공간 중앙에 빈 공간이 생긴 경우에는 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 된다.

위 그림과 같이 서로다른 사각형이 꼭지점으로 해서 만나거나, 변이 겹치는 겨우는 없다.

또한 위 그림처럼 2개 이상의 지역으로 분리되는 경우도 존재하지 않는다.

또한 위와 같이 한 사각형이 다른 사각형 안에 존재하는 경우도 없다.

이제 제한사항을 살펴보자.

전달받은 rectangle의 원소는 각 직사각형의 좌표이다. 이때 순서대로 좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y 이다.

즉 rectangle[0] 이 [1,1,7,7] 이라면 이는 (1,1) 부터 (7,7) 범위를 의미하게 되고, 이를 그림으로 그리면

왼쪽 아래 지점의 좌표가 (1,1)이고 오른쪽 위 꼭지점의 좌표가 (7,7)인 사각형을 의미하게 된다.

그리고 위 사각형에서 이동 가능한 좌표는 각 테두리를 의미하게 되며, 

(1,1) 에서 (7,1)까지 한줄 (오른쪽 이동)

(7,1) 에서 (7,7)까지 한줄 (위로 이동)

(7,7) 에서 (1,7)까지 한줄(왼쪽으로 이동)

(1,7) 에서 (1,1) 까지 한줄(아래로 이동)

이며, 위 값에서 알 수 있듯이 x 또는 y값만 증가된 좌표값을 가지게 된다.

이제 입출력 예제 1번을 살펴보자.

먼저 전달받은 좌표를 이용하여 사각형을 2차원 배열에 그리게 되면 위와 같은 형태를 띄게 된다. 

하지만 위를 코드로 작성하여 '이동 칸'을 계산하면 15칸이 나온다. 그림도 해설과는 다른 느낌이다.

이유는 바로 [3,2,5,5] 사각형과 [2,6,8,8] 두 사각형 사이에서 발생한다.

수치상으로는 (3,5)와 (3,6) 사이에 빈 공간이 주어져야 하지만, 실제로 위 처럼 값을 채우게 되면 (3,5)도 값을 가지고 (3,6)도 값을 가지게 되어 위 그림과 같은 문제가 생기게 되는 것이다.

실제 코드로 작성한 뒤 결과물

정답은 17이지만, 결과물은 15가 되었다.

이제 원인을 찾아야 한다.

원인은 각 좌표들이 바로 옆의 숫자처럼 붙어있기 때문이다. 이를 해결하기 위해선 여러가지 방법이 있겠지만 내가 선택한 방법은 배열도 2배~ 좌표 크기도 2배로 늘려주는 방법이다.

즉 위에서 [3,2,5,5]와 [2,6,8,8] 이 문제가 되었다면, 2배로 늘리게 되면 [6,4,10,10] 과 [4,12,16,16]으로 늘려주어 겹쳐지는 부분은 그대로이고 서로의 간격만 1칸 더 생기게 해주는걸로 해결하였다.

먼저 전달받은 rectangle 에서 보드를 생성하기 위한 최대값을 찾아야 한다. 이때 사용할 것은 우측 상단 지점의 x,y 좌표이다. 이를 이용하여 2배 큰 보드를 생성하였다.

이제 시 반복문을 돌며 범위에 맞게 사각형을 그려주는 작업을 하는데, 테두리만 그리면 되기에 i 값은 y1*2, y2*2, j값은 x1*2, x2*2와 같은 경우에만 1로 표기해 주었고 나머지는 -1로 칠해 주었다.

입출력 예제 1을 위 코드로 사용하여 그린 2차원 배열

이제 해야할 일은 한가지 이다. 시작 지점(2배로 늘린 좌표)에서 도착 지점(2배로 늘린 좌표)까지의 거리를 계산한 뒤 이를 반환 (//2) 하면 된다.

탐색 코드는 언제나 보던 형태이기 때문에 따로 설명은 남겨놓지 않겠다. 모든 수치를 2배로 늘려서 사용한다는 점과, 반환시에는 이를 다시 2로 나누어야 한다는 사실만 기억하면 끝이다.