[2021 KAKAO Blind Recruitment] Q6. 카드 짝 맞추기 (C++, Python, Java)

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/72415

 

예상 난이도

S2 - G5

 

알고리즘 분류

BFS, 시뮬레이션, 브루트 포스, DP

 

풀이

뭔가 삼성 A형스러운 문제입니다. 일단 카드의 종류가 최대 6가지이므로 제거할 종류의 순서를 정할 때 6!이고 각 카드는 종류별로 2장씩이므로 둘 중에서 어느 것을 먼저 제거할지 정해야하는데 일단은 이 부분을 무시하겠습니다.

 

다음으로 매번 현재 커서의 위치에서 카드까지 도달하기 위한 최단거리를 구해야 하는데, 코드 좀 치시는 분들은 2차원 배열에서 가중치가 1인 상황에서의 최단거리다 하면 바로 눈이 돌아가야합니다. 

 

대놓고 BFS입니다.

 

 

카드를 2번, 3번, 1번 순으로 지우겠다고 정했을 때 2L→2R →3L →3R →1L →1R 순으로 방문할 수도 있고 2R→2L →3L →3R →1L →1R 순으로 방문할 수도 있고, 2L→2R →3R →3L →1L →1R 순으로 방문할 수도 있고, ... 총 23가지의 가능한 순서가 존재합니다.

 

카드 종류는 총 6가지이니 이를 감안해 시간복잡도를 계산해보면 6! * 26개의 가능한 순서가 있고 각 순서에 대해 BFS를 총 12번, 각 BFS는 대충 O(16)이니 대략 O(107) 정도가 됩니다. 이렇게 짜면 C++, Java는 통과되는데 Python에서는 시간 초과가 발생합니다.

 

Python에서는 여기다가 DP까지 끼얹어야 합니다. 저 식을 그대로 따라치기가 너무 귀찮으니 알아서 위의 그림을 참고해주세요. 직전에 L에서 R로 갔는지, R에서 L로 갔는지를 가지고 DP를 돌려서 시간복잡도를 떨궈야합니다. C++, Java에서는 DP를 안해도 되지만 그냥 둘 다 DP까지 넣은 코드로 두었습니다.

 

코드(C++)

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define X first
#define Y second

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,-1,1};

bool OOB(int x, int y){
    return x < 0 || x > 3 || y < 0 || y > 3;
}

int dist(vector<vector<int>>& board, pii src, pii dst){
    int d[4][4];
    for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) d[i][j]=-1;
    d[src.X][src.Y] = 0;
    queue<pii> q;
    q.push(src);
    while(!q.empty()){
        auto cur = q.front(); q.pop();
        for(int dir = 0; dir < 4; dir++){
            int en = 0; // dir 방향으로 진행할 때 카드 혹은 마지막 까지의 거리
            while(true){
                int nx = cur.X+dx[dir]*en;
                int ny = cur.Y+dy[dir]*en;
                if(OOB(nx+dx[dir],ny+dy[dir]) || (en != 0 && board[nx][ny] != 0)) break;
                en++;
            }
            for(int z : {1, en}){
                int nx = cur.X+dx[dir]*z;
                int ny = cur.Y+dy[dir]*z;
                if(OOB(nx,ny)) continue;
                if(d[nx][ny] == -1)
                {
                  d[nx][ny] = d[cur.X][cur.Y]+1;
                  q.push({nx,ny});
                }               
            }
        }
    }    
    return d[dst.X][dst.Y];
}
int solution(vector<vector<int>> board, int r, int c) {
    vector<pii> occur[7];

    for(int i = 0; i < 4; i++) for(int j = 0; j < 4;j++){
        if(board[i][j]==0) continue;
        occur[board[i][j]].push_back({i,j});
    }

    vector<int> p;
    for(int i = 1; i <= 6; i++){
        if(!occur[i].empty()) p.push_back(i);
    }
    int n = p.size(); // 카드 종류의 개수
    int ans = 99999999;
    do{ // 제거할 종류의 순서에 대한 permutation
        vector<vector<int>> myboard = board;
        int d[6][2];
        d[0][0] = dist(myboard, {r, c}, occur[p[0]][0]) + dist(myboard, occur[p[0]][0], occur[p[0]][1]);
        d[0][1] = dist(myboard, {r, c}, occur[p[0]][1]) + dist(myboard, occur[p[0]][1], occur[p[0]][0]);
        myboard[occur[p[0]][0].X][occur[p[0]][0].Y] = 0;
        myboard[occur[p[0]][1].X][occur[p[0]][1].Y] = 0;
        for(int i = 1; i < n; i++){
             d[i][0] = min(d[i-1][0] + dist(myboard, occur[p[i-1]][1], occur[p[i]][0]), d[i-1][1] + dist(myboard, occur[p[i-1]][0], occur[p[i]][0])) + dist(myboard, occur[p[i]][0], occur[p[i]][1]);
            d[i][1] = min(d[i-1][0] + dist(myboard, occur[p[i-1]][1], occur[p[i]][1]), d[i-1][1] + dist(myboard, occur[p[i-1]][0], occur[p[i]][1])) + dist(myboard, occur[p[i]][1], occur[p[i]][0]);
            myboard[occur[p[i]][0].X][occur[p[i]][0].Y] = 0;
            myboard[occur[p[i]][1].X][occur[p[i]][1].Y] = 0;        
        }
        ans = min({ans, d[n-1][0], d[n-1][1]});        
    }while(next_permutation(p.begin(), p.end()));
    return ans + 2*n;
}

dist 함수에서 &를 이용해 매번 board를 복사하는 대신 reference로 이용했습니다. 6!의 순서를 정하는건 next_permutation을 사용했습니다.

 

코드(Python)

import collections, itertools, copy

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def OOB(x, y):
    return x < 0 or x > 3 or y < 0 or y > 3

def dist(board, src, dst):
    d = [[-1]*4 for i in range(4)]
    d[src[0]][src[1]] = 0
    q = collections.deque()
    q.append(src)
    while q:
        cur = q.popleft()
        for dir in range(4):
            en = 0
            while True:
                nx = cur[0] + dx[dir] * en
                ny = cur[1] + dy[dir] * en
                if OOB(nx+dx[dir], ny+dy[dir]) or (en != 0 and board[nx][ny]): break
                en += 1
            for z in (1, en):
                nx = cur[0] + dx[dir] * z
                ny = cur[1] + dy[dir] * z
                if OOB(nx, ny): continue
                if d[nx][ny] == -1:
                    d[nx][ny] = d[cur[0]][cur[1]] + 1
                    q.append((nx,ny))
    return d[dst[0]][dst[1]]
    
def solution(board, r, c):
    occur = [[] for i in range(7)]
    brute = []
    for i in range(4):
        for j in range(4):
            if board[i][j] == 0: continue
            if occur[board[i][j]]: brute.append(board[i][j])
            occur[board[i][j]].append((i,j))
    
    n = len(brute)
    ans = 99999999
    for p in itertools.permutations(brute):        
        myboard = copy.deepcopy(board)
        d = [[0]*2 for i in range(n)]
        d[0][0] = dist(myboard, (r, c), occur[p[0]][0]) + dist(myboard, occur[p[0]][0], occur[p[0]][1])
        d[0][1] = dist(myboard, (r, c), occur[p[0]][1]) + dist(myboard, occur[p[0]][1], occur[p[0]][0])
        myboard[occur[p[0]][0][0]][occur[p[0]][0][1]] = 0
        myboard[occur[p[0]][1][0]][occur[p[0]][1][1]] = 0        
        for i in range(1, n):
            d[i][0] = min(d[i-1][0] + dist(myboard, occur[p[i-1]][1], occur[p[i]][0]), d[i-1][1] + dist(myboard, occur[p[i-1]][0], occur[p[i]][0])) + dist(myboard, occur[p[i]][0], occur[p[i]][1])
            d[i][1] = min(d[i-1][0] + dist(myboard, occur[p[i-1]][1], occur[p[i]][1]), d[i-1][1] + dist(myboard, occur[p[i-1]][0], occur[p[i]][1])) + dist(myboard, occur[p[i]][1], occur[p[i]][0])
            myboard[occur[p[i]][0][0]][occur[p[i]][0][1]] = 0
            myboard[occur[p[i]][1][0]][occur[p[i]][1][1]] = 0            
        ans = min(ans, d[n-1][0], d[n-1][1])
        
    return ans + 2 * n;

itertools.permutations를 활용했습니다.

 

코드(Java)

import java.util.*;
class Solution {
    static class pair{
        public int x, y;
        pair(int x, int y){this.x = x; this.y = y;}
    }
    
    static int dx[] = {1,-1,0,0};
    static int dy[] = {0,0,1,-1};
    
    static boolean OOB(int x, int y){
        return x < 0 || x > 3 || y < 0 || y > 3;
    }
    
    static int dist(int[][] board, pair src, pair dst){
        int d[][] = new int[4][4];
        for(int i = 0; i < 4; i++)
            for(int j = 0; j < 4; j++)
                d[i][j] = -1;
        d[src.x][src.y] = 0;
        Queue<pair> q = new LinkedList<>();
        q.add(new pair(src.x, src.y));
        while(!q.isEmpty()){
            pair cur = q.poll();
            for(int dir = 0; dir < 4; dir++){
                int en = 0; // dir 방향으로 진행할 때 카드 혹은 마지막 칸까지의 거리
                while(true){
                    int nx = cur.x + dx[dir] * en;
                    int ny = cur.y + dy[dir] * en;
                    if(OOB(nx+dx[dir], ny+dy[dir]) || (en != 0 && board[nx][ny] != 0)) break;
                    en++;
                }
                for(int i = 0; i < 2; i++){
                    int z = 1;
                    if(i == 1) z = en;
                    int nx = cur.x + dx[dir] * z;
                    int ny = cur.y + dy[dir] * z;
                    if(OOB(nx, ny)) continue;
                    if(d[nx][ny] == -1){
                        d[nx][ny] = d[cur.x][cur.y] + 1;
                        q.add(new pair(nx, ny));
                    }
                }                
            }
        }
        return d[dst.x][dst.y];
    }
    
    static int p[] = new int[6];
    static boolean isused[] = new boolean[7];
    static int n = 0;
    static int ans = 9999999;
    static pair occur[][] = new pair[7][2];
    static int[][] bboard = new int[4][4];
    static int rr, cc;
    static void solve(int idx){
        if(idx == n){ // p[0], p[1], ... , p[n-1]에 permutation이 다 채워짐
            int myboard[][] = new int[4][4];
            for(int i = 0; i < 4; i++)
                for(int j = 0; j < 4; j++)
                    myboard[i][j] = bboard[i][j];
            int d[][] = new int[6][2];
            
            d[0][0] = dist(myboard, new pair(rr, cc), occur[p[0]][0]) + dist(myboard, occur[p[0]][0], occur[p[0]][1]);
            d[0][1] = dist(myboard, new pair(rr, cc), occur[p[0]][1]) + dist(myboard, occur[p[0]][1], occur[p[0]][0]);
            myboard[occur[p[0]][0].x][occur[p[0]][0].y] = 0;
            myboard[occur[p[0]][1].x][occur[p[0]][1].y] = 0;
            for(int i = 1; i < n; i++){
                d[i][0] = Math.min(d[i-1][0] + dist(myboard, occur[p[i-1]][1], occur[p[i]][0]), d[i-1][1] + dist(myboard, occur[p[i-1]][0], occur[p[i]][0])) + dist(myboard, occur[p[i]][0], occur[p[i]][1]);
                d[i][1] = Math.min(d[i-1][0] + dist(myboard, occur[p[i-1]][1], occur[p[i]][1]), d[i-1][1] + dist(myboard, occur[p[i-1]][0], occur[p[i]][1])) + dist(myboard, occur[p[i]][1], occur[p[i]][0]);
                myboard[occur[p[i]][0].x][occur[p[i]][0].y] = 0;
                myboard[occur[p[i]][1].x][occur[p[i]][1].y] = 0;    
            }
            ans = Math.min(Math.min(ans, d[n-1][0]), d[n-1][1]);
        }
        for(int i = 1; i <= 6; i++){
            if(occur[i][0].x == -1 || isused[i]) continue;
            p[idx] = i;
            isused[i] = true;
            solve(idx+1);
            isused[i] = false;            
        }
    }
    
    public int solution(int[][] board, int r, int c) {
        rr = r; cc = c;
        for(int i = 0; i < 4; i++)
            for(int j = 0; j < 4; j++)
                bboard[i][j] = board[i][j];
        for(int i = 0; i < 7; i++){
            occur[i][0] = new pair(-1, -1);
            occur[i][1] = new pair(-1, -1);      
        }
        for(int i = 0; i < 4; i++){
            for(int j = 0; j < 4; j++){
                if(board[i][j] == 0) continue;
                if(occur[board[i][j]][0].x == -1){
                    occur[board[i][j]][0] = new pair(i, j);
                    n++;
                }
                else
                    occur[board[i][j]][1] = new pair(i, j);
            }
        }
        solve(0);
        return ans + 2*n;
    }

Java에는 permutation 관련 라이브러리가 없기 때문에 직접 구현을 해야 합니다. 저는 백트래킹을 이용해 구현했습니다.

 

관련 강의

0x09강 - BFS

0x0C강 - 백트래킹

0x0D강 - 시뮬레이션

0x10강 - 다이나믹 프로그래밍

  Comments
댓글 쓰기