23.03.14 파이썬 코딩 퀴즈#195 기둥과 보 설치 (프로그래머스 스쿨)

이번 문제는 기둥과 보 설치 문제이다.

기둥과 보의 설치 기준은 2가지 이다.

1. 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나 또는 다른 기둥 위에 있어야 한다.

2. 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.

친절하게 그림설명 까지 되어있지만, 뭔가 난잡해 보인다.

위 그림에 대한 설명이다. 

한가지 주의깊게 확인해야 할 사항은 4번째 항목이다

(4,2) 에서 오른쪽으로 먼저 보를 설치 후, (3,2)에서 오른쪽으로 보를 설치한다.

만약 (3,2) 에서 오른쪽으로 보를 설치하게 되면, 2번째 규칙에 어긋난다( 보는 한쪽 부분이 기둥 끝에 연결되어야 한다)

따라서 (4,2) 에서 오른쪽으로 먼저 설치하고, 남은 빈 부분을 (3,2) 에서 오른쪽으로 설치하게 되면 보의 양쪽이 다른 보에 동시에 연결되기 때문에 설치가 가능하다.

제한사항을 보면 전달받는 배열 build_frame 을 좀더 이해하기 쉬워 진다.

먼저 build_frame 의 원소는 [x,y,a,b] 형태이며 

이때 x, y 는 기둥 또는 보를 설치/삭제할 교차점의 좌표이다.

a 는 구조물의 종류를 나타내며 0 은 기둥, 1은 보이다.

b 는 설치/삭제를 나타내며 0은 삭제, 1은 설치를 나타낸다.

그리고 최종 구조물의 상태는 다시 규칙에 맞춰 return 해야한다.

1. 배열은 가로 길이가 3인 2차원 배열이며, 원소는 [x,y,a] 형식이다.

2. x,y 는 기둥, 보의 교차점 좌표이며, 기둥, 보는 교차점 좌표를 기준으로 오른쪽 또는 위쪽 방향으로 설치되어 있음을 의미한다.

3. a는 구조물의 종류이며 0은 기둥, 1은 보를 의미한다.

4. return 하는 배열은 x좌표 기준으로 오름차순 정렬하며, x좌표가 같을 경우 y좌표 기준으로 오름차순 정렬해야 한다.

5. x,y 좌표가 모두 같은 경우에는 기둥(1)이 보(0)보다 앞에 오면 된다.

 

아... 굉장히 설명이 복잡하다... 역시 카카오 블라인드 채용 문제답다.

입출력 예 1번은 위 그림과 같다

1. (1,0) 에 기둥(0) 을 설치(1) 한다,  (위쪽방향)

2. (1,1) 에 보(1)를 설치(1) 한다. (오른쪽 방향)

3. (2,1) 에 기둥(0)을 설치(1)한다.  (위쪽방향)

4. (2,2)에 보(1)를 (1)설치(1)한다. (오른쪽 방향)

5. (5,0)에 기둥(0)을 설치(1)한다.  (위쪽방향)

6. (5,1)에 기둥(0)을 설치(1)한다.  (위쪽방향)

7.(4,2)에 보(1)를 설치(1) 한다. (오른쪽 방향)

8. (3,2)에 보(1)를 설치(1) 한다. (오른쪽 방향)

 

만약 중간에 명령을 수행 할 수 없으면, 무시하고 다음 명령으로 진행하게 된다.

이제 기둥을 세울 수 있는 조건과 보를 설치 할 수 있는 조건 두 가지를 가지고 입출력 예 2 번을 살펴보자.

 

1. (0,0)에 기둥(0)을 설치(1) 한다. (위쪽방향)

2. (2,0)에 기둥(0)을 설치(1) 한다. (위쪽방향)

3. (4,0)에 기둥(0)을 설치(1) 한다. (위쪽방향)

4. (0,1)에 보(1)를 설치(1) 한다. (오른쪽 방향)

5. (1,1)에 보(1)를 설치(1) 한다. (오른쪽 방향)

6. (2,1)에 보(1)를 설치(1) 한다. (오른쪽 방향)

7. (3,1)에 보(1)를 설치(1) 한다. (오른쪽 방향)

8. (2,0)에 기둥(0)를 제거(0) 한다. (기둥 제거)

9, (1,1)에서 오른쪽 보(1) 를 제거 한다. 하지만 이미 8번에 의해 기둥에 제거 되었기 때문에 해당 명령은 무시한다.

10. (2,2)에서 기둥()을 설치(1)한다. 하지만 설치 조건에 맞지 않기 때문에 해당 명령은 무시한다.

 

보는 단독으로 설치,제거가 불가능 하기 때문에 기둥을 먼저 잘 확인해 봐야 한다.

 

그리고 한가지 더 주의해야 할 점은 바로 보와 기둥의 설치 위치이다.

만약 기둥을 (0,0)에 설치하였다고 가정하자.

입출력 예 1번을 2차원 배열로 다시 옮긴 모습이다.

그리고 여기서 규칙을 다시 재확인 가능하다.

1. 기둥은 바닥에 세우거나, 좌,우,아래에 구조물(보 또는 기둥) 이 있는 경우라면 세울 수 있다.

2. 보는 아래에 기둥이 있거나, 왼쪽/오른쪽 아래에 기둥이 있는 경우와 양옆에 보가 있다면 세울 수 있다,.

삭제는 조금 더 까다롭다. 구조물을 제거 하더라도 해당 구조물이 무너지면 제거할 수 없다.

 

먼저 기둥이다.

1. 기둥을 제거하려면 위쪽의 구조물들을 확인하여야 한다.

2. 위 그림에서는 (2,1) 기둥을 제거하면 구조물이 무너진다.

3. 기둥을 제거해도 구조물을 유지하려면 기둥의 왼쪽 위, 위쪽, 오른쪽 위 구조물이 연결되어 있어야 한다.

 

보를 제거하려면 더 조건이 까다롭다.

1. (1,1)에 설치된 보는 오른쪽으로 뻗기 때문에 (1,2)에 기둥을 설치할 수 있다. 바꿔 말하면 보의 오른쪽에 기둥이 있고, 해당 기둥이 떠있다면 제거할 수 없다.

2. 보가 3개 나란히 연결된 경우에는 기둥과 연결된 보는 제거할 수 없다. 반대로 기둥과 연결되지 않은 가운데 보는 제거 가능하다.

3. 보가 n 개 나란히 연결된 경우라면 보를 제거할 수 없다.

입출력 예제 2를 통해 다시 확인해보면, 현재 기둥은 (0,0) (4,0) 두 곳에 설치되어 있고, 보는 (0,1) ~ (3,1) 까지 설치되어 있다. (0,1)의 보를 제거하게 되면 (1,1)의 보 왼쪽에는 지지할수 있는 구조물이 없다. 따라서 제거할 수 없다.

(1,1) 보를 제거하면 (0,1)은 아래 기둥이 있어 괜찮지만 (2,2) 보는 왼쪽에 구조물이 없어서 무너진다. 따라서 제거할 수 없다. (2,2) 보 역시 같은 이유로 제거 할 수 없다.

(3,3)보를 제거하면 (2,2)보의 오른쪽을 지지하는 구조물이 없다. 따라서 제거할 수 없다.

즉 해당 보를 제거했을때, 왼쪽 아래에 기둥이 있어야 하고, 오른쪽 아래에도 기둥이 존재해야 한다. 바로 아래 기둥은 해당 보만 지탱하기 때문에 의미가 없다.

 

이제 코드를 작성해 보자.

먼저 solutioin() 함수이다.

build_frame 에의 요소 build를 x, y, stuff, operation 총 4개의 변수로 나누어 할당하였다

그리고 operation 0, 1 을 조건으로 작동한다.

다음은 이 문제의 핵심인 check() 함수이다.

먼저 stuff 의 종류에 따라 조건문으로 나뉘게 된다.

stuff 0 기둥의 기준으로 보면 y == 0 즉 바다인 경우에는 설치 또는 해체에 문제가 없다.

[x-1, y, 1]가 answer 에 있는 경우라면 즉 바로 아래에 보가 있는 경우에도 설치/삭제가 가능하다.

[x, y, 1] 현재 위치에 보가 있는 경우데도 설치/삭제에 문제가 없다.

[x, y-1, 0] 그리고 바로 아래에 기둥이 있는 경우에도 설치/삭제에 문제가 없다.

위 3가지 조건중 한가지 조건이라도 만족하면 기둥은 설치/삭제가 가능하다.

stuff 1 보 기준으로 살펴보면

[x, y-1, 0] 바로 아래에 기둥이 있는 경우라면 설치/삭제가 가능하다.

[x+1, y-1, 0] 오른쪽 아래에 기둥이 있는 경우라면 해당 보는 설치/삭제가 가능하다.

[x-1, y, 1], [x+1, y, 1] 그리고 양옆에 보가 동시에 존재한다면 설치/삭제 가능하다.

위 3가지 조건중 한가지 조건이라도 만족하면 보는 설치/삭제가 가능하다.

 

그리고 다시 solution() 함수로 넘어와서, 해당 check()함수가 not check() 즉, 참이 아니라면 기존에 설치/삭제한 구조물을 다시 제거/설치 하게 된다.

 

처음부터 문제에 접근을 잘못하는 바람에 굉장히 삽질을 많이 했다.

이유는 기둥과 보의 설치 조건과 제거 조건을 따로 설정했기 때문이다.

역으로 생각했을때, 설치가 가능했던 기둥과 보 라면 같은 조건을 기준으로 삭제도 가능할 거란 생각을 못했었다.