[프로그래머스] 퍼즐 조각 채우기 (Python)

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

코딩테스트 연습 - 퍼즐 조각 채우기

dfs로 풀이했다.

알고리즘은 다음과 같다.

 

1. 게임보드의 모양을 구한다.

    모양은 2차원 배열의 좌표 순서대로 찾으며, 방문하지 않고 해당 값이 0일 때의 좌표를 기준으로 (0,0)로 모양을 찾음

    시작점을 찾고 나면 U, D, R, L 좌표를 더해보며 이동할 수 있는지 확인(좌표가 값을 넘어가는지, 방문했는지, 값이 0)

    이동할 수 있으면  값을 추가해줌

2. 퍼즐 조각의 모양을 구한다.

    로직은 동일하며 퍼즐 조각은 회전할 수 있으므로 4번 회전시켜보며 조각 값을 구한다.

3. 게임보드 빈공간의 모양과 퍼즐 조각의 모양이 일치하면 해당 퍼즐 조각은 테이블에서 차있는 것으로 초기화

 

나의 풀이

def rotate(table):
    return list(map(list,zip(*table[::-1])))

def dfs(condition,table,key,value,visited):
    i, j, x, y, target = condition
    visited[i][j] = 1
    key.append((i,j))
    value.append((x,y))
    moves = [(-1,0),(1,0),(0,1),(0,-1)] # U D R L
    for move in moves:
        dx, dy = move
        move_x, move_y = i + dx, j + dy
        if move_x < 0 or move_y < 0 or move_x >= len(table) or move_y >= len(table):
            continue
        elif table[move_x][move_y] == target and visited[move_x][move_y] == 0:
            key,value,visited = dfs([move_x, move_y, x+dx, y+dy, target], table, key, value, visited)
    return key, value, visited

def puzzle(table,target):
    visited = [[0]*len(table) for _ in range(len(table))]
    pieces = {} if target == 1 else []
    for i in range(len(table)):
        for j in range(len(table)):
            if table[i][j] == target and visited[i][j] == 0:
                key, value, v = dfs([i,j,0,0,target],table,[],[],visited)
                if target == 1:
                    pieces[tuple(key)] = value
                else:
                    pieces.append(value)
                visited = v
    return pieces

def solution(game_board,table):
    answer = 0
    board = puzzle(game_board,0)
    for _ in range(4):
        table = rotate(table)
        pieces = puzzle(table,1)
        for key,value in pieces.items():
            if value in board:
                board.remove(value)
                answer += len(value)
                for cod in key:
                    i, j  = cod
                    table[i][j] = 0
    return answer