23.03.30 파이썬 코딩 퀴즈#206 카드 짝 맞추기(프로그래머스 스쿨)

이번 문제는 카드 짝 맞추기 문제이다.

4x4 격자에 무작위로 배치된 카드를 짝을 맞추어 모든 카드를 사라지게 하는 게임이다.

규칙은 조금 복잡하다.

먼저 카드는 커서를 이용하여 선탤 할 수 있다.

커서는 Ctrl 키와 방향키 두개를 조작하여 이동하며, 방향키만 누를 경우 해당 방향으로 한 칸 이동한다.

하지만 Ctrl 키를 누르면 해당 방향에 있는 가장 가까운 카드로 한번에 이동한다. 만약 카드가 없다면 그 방향의 가장 마지막 칸으로 이동한다. 

그 다음 커서가 위치한 카드를 뒤집기 위해서는 Enter 키를 입력한다. 앞면이 보이는 카드가 2장이 된 경우 화면에서 사라진다.

이때 '베로니'는 카드 앞면의 그림을 알고 있으며, 남은 카드를 모두 제거하는데 필요한 키 조작 횟수의 최솟값을 구해보려고 한다.

방향키와 Enter 키를 누르는 동작을 각각 1회로 계산하며, Ctrl 키와 방향키를 함께 누르는 동작 또한 조작 횟수 1로 계산한다.

다행인지 불행인지, 시작 커서의 위치 역시 전달 된다.

(1,0)의 그림을 뒤집고(Enter, 1), 아래로 이동(1) Ctrl 키와 방향키 조합으로 이동(1) 후 Enter 키 입력(1) 으로 총 4회 조작으로 한쌍의 그림을 제거 하였다.

그 다음 Ctrl 이동(1)으로 그림으로 커서를 옮긴 후 Enter 뒤집기(1), 그 다음 Ctrl 이동(1) 다시 Ctrl (1) 으로 Enter 뒤집기(1) 로 총 5회 소요된다.

마지막은 커서 기준으로 위로 가나 옆으로 가나 횟수는 동일하게 5회 소요된다. 

따라서 모든 카드 짝을 맞추기 위한 최소 키 조작 횟수는 14회 이다.

제한 사항에 의해 전달받는 board 는 4X4 의 2차원 배열이며, r,c 에 의해 커서의 시작 위치가 결정 된다.(r,c)

위 그림은 입출력 예제 2를 설명한 그림이다.

시작 위치에는 카드가 없기 때문에 왼쪽 또는 오른쪽, 아래 3방향으로 이동하여 카드를 선택 할 수 있다.

먼저 어피치(0,0)을 선택하게 된다면 Ctrl 왼쪽 (1) + Enter 뒤집기(1) + Ctrl 오른쪽 or 아래(1) + Ctrl 아래 or 오른쪽(1) + Enter 뒤집기(1) 로 총 5회 조작하여 어피치를 제거 가능하다

그 다음 Ctrl 왼쪽 or 위쪽 (1) + Enter 뒤집기(1) + Ctrl 이동(기준점 기준 모서리를 타고 이동)(1) + Ctrl 이동(1) + Enter 뒤집기(1) 로 5회 조작하여 프로도를 제거 가능하다.

그 다음은 커서를 이용하여 이동(1) + 이동(1) + Enter 뒤집기(1) + 이동(1)+이동(1)+Enter 뒤집기(1) 로 마지막 라이언을 제거하게 되며, 이때 조작 횟수는 6회 이고, 따라서 총 조작 횟수는 16회 이다.

 

만약, 가운데 있는 라이언을 먼저 제거한다면 어떤 결과가 나올까?

Ctrl 아래(1) + 뒤집기(1) + 이동(1) + 이동(1) + 뒤집기(1) = 5 (라이언 제거 완료)

Ctrl 이동(1) + Ctrl 이동(1) = 아무카드나 선택 가능 그 이후 뒤집기 (1) + Ctrl 이동(1) + Ctrl 이동 (1) + 뒤집기(1) = 6 

마지막은 위와 동일하기 때문에 5회로 총 16회 이다.

 

이제 코드를 작성해야 하는데, 좀 막막하다....

1. 전달받은 2차원 배열에서 카드 번호를 확인해야 한다. 그래야 탐색 순서가 결정 된다

2. 각 카드의 좌표를 확인해야 한다.

3. Ctrl 이동 과 일반 이동을 구분하여야 한다. 

 

그리고 이 문제가 까다로운 이유는 온갖 경우의 수를 생각해야 한다는 점이다.

그림에서는 어디로 가야 할지가 명확히 눈에 보이지만, 코드로 명령을 수행할 때에는 그 부분이 애매하다.

다시 말해 A,B,C 3개의 카드 짝을 맞춘다고 가정할 때, A1->A2 를 먼저 맞추고 B1->B2 를 맞추는게 유리한지, 아니면 A1->A2를 맞추고 B2->B1을 맞추는게 유리한지에 대한 판단을 내리기가 복잡하다.

처음에 이 부분이 몰라서 3시간을 넘게 삽질을 했다.

 

먼저 solution() 함수를 작동시키기 위해 추가로 2가지의 함수를 정의하였다.

outrange()는 범위를 확인하는 함수이며... 사실 필요는 없다

bfs() 함수는 총 3개의 변수를 전달받아 작동하며, board 는 현재 짝을 맞출 board , currunt_pos 은 커서의 현재 위치, target_pos 는 목적지 좌표 이다.

다른 부분은 크게 신경 쓸 필요없이 Ctrl 이동만 설명을 남기고 넘어가면,

먼저 새로운 좌표 new_x, new_y 가 범위를 넘어가지 않고, boards[new_x][new_y] 값이 0 이라면 계속 한 방향으로 new_x와 new_y 값을 갱신시켜 나가며 조건을 확인하다. 

만약 board[new_x][new_y] 값이 0이 아니라면(카드를 만남), 해당 좌표와 조작횟수 k 값을 1 증가 시켜서 다시 q로 넣어주면 되고, 범위를 초과해서 while문을 탈출 했다면, 그 직전값인 [new_x-dx[i], new_y-dy[i]] 좌표값을 q에 넣어주면 된다.

solution() 함수도 내용이 길어서 2분할 했다...

먼저 전달받은 board 배열에서 각 카드의 위치 좌표와 종류를 확인해야 한다.

그 다음 permutaitons()를 이용해 탐색 순서를 결정할 순열들을 만들어 준다.

이제 만들어진 순열 comb 를 돌면서 카드짝을 맞춰줘야 한다.

여기서 다시 while문을 쓰는 이유는, 어떤 순서로 맞추느냐에 따라 최소값이 달라지기 때문이다.

위에서도 한번 언급했지만, A1->A2 를 먼저 하느냐 A2->A1 을 먼저 하느냐에 따라 최소값이 달라진다.

따라서 A1->A2 를 맞추는 경우를 다시 B1->B2 OR B2->B1 2가지를 봐야하고, 여기서 다시 다음 카드를 맞추를 경우의 수 2가지를 더 확인해 봐야 한다. 이렇게 보면 A 카드를 먼저 맞추는 기준 B,C카드를 맞출 때 총 8가지의 경우를 선택해야 하고, 총 24가지의 경우의 수가 나온다.

 

따라서 각 순서에 따라 A를 먼저 맞춘 play_board1,2 를 기준으로 다시 s 배열에 넣어주어 그 값을 가지고 B,C를 또 돌아주게 된다.

카드는 달랑 3장을 가지고 시작하는데, 이 3장을 맞추는 경우의 수는 24가지 이고, A,B,C로 생성 가능한 순열은 6가지 이므로 총 144개의 경우의 수가 생긴다.

 

설명도 길고, 코드도 길지만, 시간을 가지고 집중하면 충분히 풀이 가능한 문제이다.