[알고리즘] 삼성SW문제 유형 정리

Jihoon·2023년 3월 9일

알고리즘

목록 보기

8/14

배열 회전 및 배열의 인덱스 저장 방법 - 프로그래머스 퍼즐 조각 채우기 LV3

import copy

# 저장 함수
def dfs(graph, x, y, position, n, num):
    dic = {0:[-1, 0], 1:[0, 1], 2:[1, 0], 3:[0, -1]}
    
    ret = [position]
    
    for i in range(4):
        nx = x + dic[i][0]
        ny = y + dic[i][1]
        
        if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == num:
            graph[nx][ny] = 2
            ret = ret + dfs(graph, nx, ny, [position[0]+dic[i][0], position[1]+dic[i][1]], n, num)
    
    return ret

# 회전 함수
def rotate(lst):
    n = len(lst)
    
    ret = [[0]*n for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            ret[j][n-1-i] = lst[i][j]
    
    return ret

def solution(game_board, table):
    answer = 0
    game_board_copy = copy.deepcopy(game_board)
    
    n = len(game_board)
    block = []
    # 1. 게임보드 도형 자리 저장
    for i in range(n):
        for j in range(n):
            if game_board_copy[i][j] == 0:
                game_board_copy[i][j] = 2
                result = dfs(game_board_copy, i, j, [0, 0], n, 0)[1:]
                block.append(result)
                
    # 2. 테이블 도형 자리 저장 - 4 방향 회전          
    for r in range(4):
        table = rotate(table)
        table_rotate_copy = copy.deepcopy(table)

        for i in range(n):
            for j in range(n):
                if table_rotate_copy[i][j] == 1:
                    table_rotate_copy[i][j] = 2
                    result = dfs(table_rotate_copy, i, j, [0, 0], n, 1)[1:]
                    if result in block:
                        block.pop(block.index(result))
                        answer += (len(result) + 1)
                        
                        table = copy.deepcopy(table_rotate_copy)
                        
                    else:
                        table_rotate_copy = copy.deepcopy(table)
    return answer

[출처 : https://bladejun.tistory.com/164]

핵심 사고

'ㅗ' 4자리를 차지하는 모양이 있다치면, 각 자리 별(4번)로 DFS 실행해서 어느 방향으로 가는지를 리스트에 저장

정답지는 회전 시킬 필요가 없으니 회전을 시키지 않고, 도형에 대해서 4가지 방향으로 회전시킬 필요가 있음. 따라서, 이 역시 'ㅗ'가 있다면 각 자리별 방향 4번 X 회전 4번 해서 16가지의 경우가 나옴

이와 같이 모든 도형을 적용시키면 위의 코드 완성

회전 코드 - 시계방향 90도

# 회전 함수 
def rotate(lst):
    n = len(lst)
    
    ret = [[0]*n for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            ret[j][n-1-i] = lst[i][j]
    
    return ret