[프로그래머스] 2021 카카오 공채 - 카드 짝 맞추기 (파이썬)

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

코딩테스트 연습 - 카드 짝 맞추기

※ 다른 블로그에서 좋은 코드가 있어서 관련 코드를 공부해보며 풀었습니다. 관련 블로그는 링크를 참조하시기 바랍니다. 

 

이번 문제는 혼자 해결이 어려워 다른분의 코드를 빌려 문제를 풀었다. 

 

문제 접근법부터 어떤 방식으로 풀었는지 사부작사부작 따라가 보려고 한다. 

 

1. 문제 접근법

1) 처리해야할 Data양에 대한 대략적인 추측

2) 움직일 수 있는 경우에 대해서 정리 및 구현

 

 문제를 보고 어떤 방향으로 문제를 고민하는데 있어, 내가 얼마만큼의 연산이 필요할지 생각하면 더 나은 아이디어를 얻을 수 있을 것 같다. 그리고 내가 구현해야할 행동이 뭘지 논리적으로 고민이 필요할 것 같다. 

 

2. 풀이

1) 카드판 정리 :

Card 종류가 2자리가 안되기 때문에 String으로 바꿔서 진행이 가능

    for i in range(4):
        for j in range(4):
            b+=str(board[i][j])

2) queue 정의 :

(현 y위치, 현 x위치, 카드판 string, 횟수, 카드선택)

q.append((r,c,b,cnt,enter))

3) While문을 통하여 경우의 수 확인하고 s(set)에 기존에 이동한 루트가 있다고 하면 Skip하는 방식으로 정리

    while q:
        y,x,b,c,e=q.popleft()
        pos = 4*y+x
        
        if (y,x,b,e) in s:
            continue
        s.add((y,x,b,e))

4) 4방향으로 한 칸씩 이동 :

현재 좌표(x,y)에서 상하좌우(d) 4방향으로 이동하고, 만약 이동 후에도 Board안에 남아 있다면 Queue에 추가하여 그 다음 좌표도 확인 할 수 있도록 정의(동일 위치로 돌아갈 경우 s(set)과 비교하여 Skip됨)

        #1칸씩 4방향 이동
        for (dy,dx) in d:
            ny,nx=y+dy,x+dx
            if (4>ny>=0) and (4>nx>=0):
                q.append((ny,nx,b,c+1,e))

5) Ctrl누른 후 커서 이동 :

재귀 함수(move_ctrl)를 이용하여 새로운 카드를 만나거나, 보드 밖으로 나가지 않는 좌표를 return하여 구현

        #ctrl 사용 4방향 이동
        for (dy,dx) in d:
            ny,nx = move_ctrl(y,x,dy,dx,b)
            if (y==ny) and (x==nx):
                continue
            q.append((ny,nx,b,c+1,e))
            
            
            
def move_ctrl(y,x,dy,dx,b):
    ny, nx = y+dy, x+dx
    if (4>ny>=0) and (4>nx>=0) and (b[4*ny+nx]=='0'): # &로 And를 대체 할 경우 error 발생
        return move_ctrl(ny,nx,dy,dx,b)
    
    elif (4>ny>=0) and (4>nx>=0) and (b[4*ny+nx]!='0'):
        return (ny,nx)
    else:
        return (y,x)

6) enter 누르기 : 

현재 커서 위치에 Card가 있으면 그 카드에 위치에 e(enter)값에 pos를 입력하여 queue에 추가되고, 위에 4), 5)번을 반복하다 다른 위치에 동일한 카드를 만나면 제거

        #enter누르기 
        if b[pos] != 0:
            if e == -1:
                q.append((y,x,b,c+1,pos))
            else :
                if e!=pos and b[e]==b[pos]: #e: 신규 위치,pos: 이전 card위치
                    b=b.replace(b[e],'0')
                    q.append((y,x,b,c+1,-1))

 

Full code

def move_ctrl(y,x,dy,dx,b):
    ny, nx = y+dy, x+dx
    if (4>ny>=0) and (4>nx>=0) and (b[4*ny+nx]=='0'): # &로 And를 대체 할 경우 error 발생
        return move_ctrl(ny,nx,dy,dx,b)
    
    elif (4>ny>=0) and (4>nx>=0) and (b[4*ny+nx]!='0'):
        return (ny,nx)
    else:
        return (y,x)
        
def solution(board, r, c):
    from collections import deque
    import copy
    
    d=[(0,1),(0,-1),(-1,0),(1,0)]
    b=''
    cnt = 0
    enter = -1
    q = deque()    
    answer=0
    
    for i in range(4):
        for j in range(4):
            b+=str(board[i][j])
            
    q.append((r,c,b,cnt,enter))
    s=set()
    
    while q:
        y,x,b,c,e=q.popleft()
        pos = 4*y+x
        
        if (y,x,b,e) in s:
            continue
        s.add((y,x,b,e))

        if b.count('0')==16:
            return c
        
        #1칸씩 4방향 이동
        for (dy,dx) in d:
            ny,nx=y+dy,x+dx
            if (4>ny>=0) and (4>nx>=0):
                q.append((ny,nx,b,c+1,e))
        
        #ctrl 사용 4방향 이동
        for (dy,dx) in d:
            ny,nx = move_ctrl(y,x,dy,dx,b)
            if (y==ny) and (x==nx):
                continue
            q.append((ny,nx,b,c+1,e))
    
        #enter누르기 
        if b[pos] != 0:
            if e == -1:
                q.append((y,x,b,c+1,pos))
            else :
                if e!=pos and b[e]==b[pos]: #e: 신규 위치,pos: 이전 card위치
                    b=b.replace(b[e],'0')
                    q.append((y,x,b,c+1,-1))
    return answe

 

 

 

참조 내용 : walwal234.tistory.com/37

[프로그래머스] 카드 짝 맞추기 / 파이썬