프로그래머스 Lv3 | dfs/bfs | 퍼즐 조각 채우기

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

프로그래머스

 

1. 정규화하는 아이디어

2. 회전할 때 좌표 어떻게 되는지

이 두 부분에서 감을 못 잡아서 gpt한테 물어봤다

제대로 혼자 풀어내기를 거의 1시간 30분 걸렸다.. 너무 어려워 

 

def dfs(x, y, board, value, path):
    board[x][y] = 2 # 방문 표시
    path += [(x,y)]
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < len(board) and 0 <= ny < len(board):
            if board[nx][ny] == value:
                dfs(nx, ny, board, value, path)

def normalize(list_n):
    min_x, min_y = 100, 100
    for x, y in list_n:
        min_x = min(x,min_x)
        min_y = min(y,min_y)
    
    list_new = [(x-min_x, y-min_y) for x,y in list_n]
    
    return sorted(list_new)
    
    
def move(list_a, list_b):
    # normalization
    norm_list_a, norm_list_b = normalize(list_a), normalize(list_b)

    return (norm_list_a == norm_list_b)

def rotate(list_a, list_b):
    # normalization
    norm_list_a, norm_list_b = normalize(list_a), normalize(list_b)
    
    # 90도 회전: (x, y) -> (y, -x)
    # 180도 회전:(x, y) -> (-x, -y)
    # 270도 회전:(x, y) -> (-y, x)
    
    norm_list_b_90 = []
    norm_list_b_180 = []
    norm_list_b_270 = []
    for (x, y) in norm_list_b:
        norm_list_b_90.append((y,-x))
        norm_list_b_180.append((-x, -y))
        norm_list_b_270.append((-y, x))
    
    norm_list_b_90 = normalize(norm_list_b_90)
    norm_list_b_180 = normalize(norm_list_b_180)
    norm_list_b_270 = normalize(norm_list_b_270)

    return (norm_list_a == norm_list_b_90 or norm_list_a == norm_list_b_180 or norm_list_a == norm_list_b_270)
    

def find_answer(gb_list, table_list):
    answer = 0
    visited_gb = [False]*len(gb_list)
    visited_t = [False]*len(table_list)
    
    for idx_gb, gb in enumerate(gb_list):
        for idx_t, t in enumerate(table_list):
            if len(gb) == len(t):
                if (move(gb,t) or rotate(gb,t)) and (not visited_gb[idx_gb] and not visited_t[idx_t]): # 평행이동이 가능하거나 회전이 가능할 때, 그리고 방문 x
                    answer += len(gb)
                    visited_gb[idx_gb] = True; visited_t[idx_t] = True
                    break
    
    return answer
                
    
def solution(game_board, table):
    # 게임보드의 빈칸(0)에 table의 칸(1)을 넣는 과정
    # 아예 동일하게 채울 수도 있고
    # 조각을 여러개로 채울 수도 있음 <-- 이거까지 구현 못하겠음
        # 어떤 방법이 더 나은지는.. 실제 몇칸을 채웠는지 결과에 따라 다를 것 같음
    
    # 처음에 해야 할 일은, (dfs 접근)
        # game board >> 0 그룹 찾기
        # table >> 1 그룹 찾기
        # 일반적으로 game board의 그룹이 table 그룹보다 같거나 많을 것으로 예상
    gb_list = []
    for i in range(len(game_board)):
        for j in range(len(game_board)):
            if game_board[i][j] == 0:
                path = []
                dfs(i,j,game_board, 0, path) 
                gb_list.append(path)
                
    table_list = []
    for i in range(len(table)):
        for j in range(len(table)):
            if table[i][j] == 1:
                path = []
                dfs(i,j,table, 1, path)
                table_list.append(path)
    
    # 채울 수 있는지 어떻게 판단할 것인가
        # 단순히 평행이동이면 매우 쉬워짐,, 그 위치들을 동일한 값으로 x축 y축 평행이동 했을 때 도달하는지 확인하면 되니까
        # 근데 우리의 문제는 회전이 된다는 사실,, 그 좌표를 어떻게 구현할 것인가
        
    return find_answer(gb_list, table_list)