[카카오 2021 공채] 카드 짝 맞추기

2021년 카카오 공채 카드 짝 맞추기 해설입니다

---

최소한의 키 조작으로 카드들을 모두 제거하는 문제입니다.

카드를 선택하는 경우는 두 가지입니다.

1. 어떤 값을 지닌 카드를 선택해야 하는 가?
2. 같은 값을 지닌 두 개의 카드 중 어느 카드를 먼저 선택해야 하는 가?

1번의 경우는 board의 크기가 4*4 이며 카드 값의 범위가 1~6 이기 때문에 permutate를 통한 완전탐색으로 해결할 수 있습니다. 2번의 경우 출발점 -> 카드1 -> 카드2의 키 조작 횟수와 출발점 -> 카드2 -> 카드1의 키 조작 횟수 중 작은 것을 선택하면 됩니다. 최소한의 키 조작 횟수를 구해야하기 때문에 BFS 알고리즘을 사용할 수 있습니다.

자바에서는 카드의 위치를 저장할 자료구조를 Point Class로 하고 파이썬에서는 tuple로 합니다. 자바를 기준으로 설명합니다.

class Point {
    int row, col, count;
    Point(int row, int col, int count) {
        this.row = row;
        this.col = col;
        this.count = count;
    }
}

Point는 board 상의 자신의 위치와 키 조작 횟수를 저장합니다.

다음은 permutate() 입니다. permutate() 는 커서의 현재 위치를 인자로 받습니다.

private int permutate(Point src) {
    int result = INF;
    for (int num = 1; num <= 6; num++) {
        List<Point> points = new ArrayList<>();            
        for (int r = 0; r < 4; r++) {
            for (int c = 0; c < 4; c++) {
                if (Board[r][c] == num)
                    points.add(new Point(r, c, 0));
            }
        }
        if (points.isEmpty())
            continue;
}

num을 1 ~ 6까지 반복하고 board를 완전탐색하여 다음에 제거할 카드의 모든 경우를 고려합니다. 만약 points가 비어있을 경우 해당 값을 지닌 카드가 존재하지 않는 것이므로 다음 값으로 넘어 갑니다.

private int permutate(Point src) {
        ...

        int one = bfs(src, points.get(0)) + bfs(points.get(0), points.get(1)) + 2;
        int two = bfs(src, points.get(1)) + bfs(points.get(1), points.get(0)) + 2;

        ...

    }
    return result == INF ? 0 : result;
}

points에 저장된 두 개의 카드 중 먼저 선택할 카드를 선정하고 BFS를 통해 최소 키 조작 횟수를 구합니다. 어느 카드를 먼저 선택해야하는 지 알 수 없으므로 두 경우 모두 고려합니다. 그리고 카드를 뒤집을 때는 Enter를 입력해야 하므로 2회를 더합니다

private int permutate(Point src) {
        ...

        for (int j = 0; j < 2; j++) {
            Board[points.get(j).row][points.get(j).col] = 0;
        }

        result = Math.min(result, one + permutate(points.get(1)));
        result = Math.min(result, two + permutate(points.get(0)));

        for (int j = 0; j < 2; j++) {
            Board[points.get(j).row][points.get(j).col] = num;
        }
        ...

    }
    return result == INF ? 0 : result;
}

두 카드를 board에서 제거하고 나중에 선택한 카드를 출발 지점으로 넘기며 재귀적으로 반복합니다. one에서는 0 번 카드를 먼저 선택하여 1번 카드를 출발지점으로 넘깁니다. two도 동일한 논리로 0번 카드를 인자로 넘깁니다.

카드가 모두 제거된 경우 result에는 INF가 저장되어 있으므로 이때는 0을 반환하도록 합니다.

bfs()는 키 조작 횟수를 구할 출발 지점(src)와 도착 지점(dst)를 인자로 받습니다. 기본적인 bfs 내용은 모두 생략하고 방향키 이동 부분에 대한 코드만 보겠습니다.

...
// 일반 이동
if (!visited[nr][nc]) {
  q.add(new Point(nr, nc, point.count + 1));
  visited[nr][nc] = true;
}
...

일반적인 방향키 이동에 대한 부분입니다. 이동 지점을 방문한 적이 없는 경우 방문합니다.

for (int j = 0; j < 2; j++) {
    if (nr + dr[i] < 0 || nr + dr[i] > 3 || nc + dc[i] < 0 || nc + dc[i] > 3)
        break;

    if (Board[nr][nc] != 0)
        break;

    nr += dr[i];
    nc += dc[i];
}

if (!visited[nr][nc]) {
    q.add(new Point(nr, nc, point.count + 1));
    visited[nr][nc] = true;
}

Ctrl + 방향키 이동에 대한 부분입니다. j < 2는 board의 크기가 4*4이기 때문에 어느 지점에서도 추가적으로 2번 이상 이동할 수 없기 때문입니다.

다음에 이동할 지점이 범위를 벗어날 경우, 그리고 현재 새로운 지점에 카드가 존재할 경우 종료하고 큐에 추가합니다.

Java

import java.util.*;
class Solution {
    class Point {
        int row, col, count;
        Point(int row, int col, int count) {
            this.row = row;
            this.col = col;
            this.count = count;
        }
    }

    private int[][] Board;
    private static final int INF = Integer.MAX_VALUE;
    private int[] dr = {1, -1, 0, 0};
    private int[] dc = {0, 0, 1, -1};
    public int solution(int[][] board, int r, int c) {
        Board = board;
        return permutate(new Point(r, c, 0));
    }

    private int permutate(Point src) {
        int result = INF;
        for (int num = 1; num <= 6; num++) {
            List<Point> points = new ArrayList<>();            
            for (int r = 0; r < 4; r++) {
                for (int c = 0; c < 4; c++) {
                    if (Board[r][c] == num)
                        points.add(new Point(r, c, 0));
                }
            }
            if (points.isEmpty())
                continue;

            int one = bfs(src, points.get(0)) + bfs(points.get(0), points.get(1)) + 2;
            int two = bfs(src, points.get(1)) + bfs(points.get(1), points.get(0)) + 2;

            for (int j = 0; j < 2; j++) {
                Board[points.get(j).row][points.get(j).col] = 0;
            }

            result = Math.min(result, one + permutate(points.get(1)));
            result = Math.min(result, two + permutate(points.get(0)));


            for (int j = 0; j < 2; j++) {
                Board[points.get(j).row][points.get(j).col] = num;
            }

        }
        return result == INF ? 0 : result;
    }

    public int bfs(Point src, Point dst) {
        Queue<Point> q = new LinkedList<>();
        boolean[][] visited = new boolean[4][4];

        q.add(src);
        visited[src.row][src.col] = true;

        while (!q.isEmpty()) {
            Point point = q.poll();

            if (point.row == dst.row && point.col == dst.col) {
                return point.count;
            }

            for (int i = 0; i < 4; i++) {
                int nr = point.row + dr[i], nc = point.col + dc[i];

                if (nr < 0 || nr > 3 || nc < 0 || nc > 3)
                    continue;

                // 일반 이동
                if (!visited[nr][nc]) {
                    q.add(new Point(nr, nc, point.count + 1));
                    visited[nr][nc] = true;
                }

                // Ctrl + 방향키 이동
                for (int j = 0; j < 2; j++) {
                    if (nr + dr[i] < 0 || nr + dr[i] > 3 || nc + dc[i] < 0 || nc + dc[i] > 3)
                        break;

                    if (Board[nr][nc] != 0)
                        break;

                    nr += dr[i];
                    nc += dc[i];
                }

                if (!visited[nr][nc]) {
                    q.add(new Point(nr, nc, point.count + 1));
                    visited[nr][nc] = true;
                }
            }
        }

        return INF;
    }
}

Python

from collections import deque

_board = [[]]
INF = float('inf')
dr, dc = (1, -1, 0, 0), (0, 0, 1, -1)
def solution(board, r, c):
    global _board
    _board = board
    return permutate((r, c, 0))

def permutate(src):
    result = INF
    for num in range(1, 7):
        points = []
        for r in range(4):
            for c in range(4):
                if _board[r][c] == num:
                    points.append((r, c, 0))

        if not points:
            continue

        one = bfs(src, points[0]) + bfs(points[0], points[1]) + 2
        two = bfs(src, points[1]) + bfs(points[1], points[0]) + 2

        for i in range(2):
            _board[points[i][0]][points[i][1]] = 0

        result = min(result, one + permutate(points[1]))
        result = min(result, two + permutate(points[0]))

        for i in range(2):
            _board[points[i][0]][points[i][1]] = num

    return result if result != INF else 0

def bfs(src, dst):
    q = deque()
    visited = [[False for _ in range(4)] for _ in range(4)]

    q.append(src)
    visited[src[0]][src[1]] = True

    while q:
        row, col, count = q.popleft()

        if row == dst[0] and col == dst[1]:
            return count

        for i in range(4):
            nr, nc = row + dr[i], col + dc[i]

            if nr < 0 or nr > 3 or nc < 0 or nc > 3:
                continue

            if not visited[nr][nc]:
                q.append((nr, nc, count + 1))
                visited[nr][nc] = True

            for _ in range(2):
                if _board[nr][nc]:
                    break

                if nr + dr[i] < 0 or nr + dr[i] > 3 or nc + dc[i] < 0 or nc + dc[i] > 3:
                    break

                nr += dr[i]
                nc += dc[i]

            if not visited[nr][nc]:
                q.append((nr, nc, count + 1))
                visited[nr][nc] = True
    return INF