[프로그래머스, 파이썬] 퍼즐 조각 채우기 - 레벨 3 | 깊이/너비 우선 탐색(DFS/BFS), 시뮬레이션 문제

PoemSilver·2023년 1월 1일
0

Algorithm

목록 보기
8/30

📌 프로그래머스 Level 3 : 퍼즐 조각 채우기

시뮬레이션 문제!

풀어본 프로그래머스 문제 중에 가장 삼성전자 코딩테스트 유형이랑 비슷해보인다.

아이디어는 간단하지만 구현이 까다롭다.

game borad의 빈공간 배열 만들고,
able에서 퍼즐 조각 배열 만들고,
퍼즐 조각을 90도 회전을 최대 3번 시켜보면서 game board의 빈공간 배열과 일치하면
해당 퍼즐 조각 갯수를 answer에 더해준다.

구현이 까다로워서 오래걸렸지만, 생각 외로 한 번에 통과되어 신기했다..ㅋㅋ

이런 시뮬레이션 문제는 한 번에 얼마나 꼼꼼하게 구현하는가가 제일 중요한 것 같다.. 구현 끝냈는데 통과 못하는 테스트케이스가 생기면 어디서 문제가 발생했는지 찾기 어렵기 때문이다.


📋 내 답안

from collections import defaultdict, deque
def solution(game_board, table):
    answer = 0
    #game_boar용
    q1 = deque([(0,0)])
    #table용
    q2 = deque([(0,0)])
    MAX_X = len(game_board)
    MAX_Y = len(game_board[0])
    #방문용도
    visit_g = [[0 for _ in range(MAX_X)] for _ in range(MAX_Y)]
    visit_t = [[0 for _ in range(MAX_X)] for _ in range(MAX_Y)]
	
    """
    game_board 기준, 현재 위치가 비어있지 않으면(1) 방문되지 않았고,
    빈공간인 시작 지점 찾기(target = 0)
    
    table 기준, 현재 위치가 비어있으면(0) 방문되지 않았고, 
    채워져있는 시점 찾기(target = 1)
    """
    def findzero(board, p, visit,target):
        for x in range(MAX_X):
            for y in range(MAX_Y):
                if visit[x][y] == 0 and board[x][y] == target:
                    visit[x][y] = 2
                    return (x,y)
                elif visit[x][y] == 0:
                    visit[x][y] = 1
        return 0

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

	# gameboard의 비어있는 조각, 혹은 table의 채워져있는 퍼즐 조각 찾기
    def findempty(board,q,empty,visit,target):
        t = []
        while q:
            x1, y1 = q.popleft()

            if board[x1][y1] != target:
                temp = findzero(board,(x1, y1),visit,target)
                if temp != 0:
                    q.append(temp)

            else:
                # 빈공간 첫 시작
                if t == []:
                    t.append((x1, y1))
                    visit[x1][y1] = 2
                cnt = 0
                for i in range(4):
                    nx = x1 + dx[i]
                    ny = y1 + dy[i]

                    if 0 <= nx < MAX_X and 0 <= ny < MAX_Y and visit[nx][ny] == 0 and board[nx][ny] == target:
                        visit[nx][ny] = 2
                        cnt += 1
                        t.append((nx, ny))
                        q.append((nx, ny))

                # 빈 공간의 끝이고 q1에 남아있는 것이 없음
                if cnt == 0 and not q:
                    xx = [t[i][0] for i in range(len(t))]
                    yy = [t[i][1] for i in range(len(t))]
                    p_x = max(xx) - min(xx)
                    p_y = max(yy) - min(yy)

                    p = [[0 for _ in range(p_y+1)] for _ in range(p_x+1)]
                    cx,cy = 0,0
                    for i in range(min(xx),max(xx)+1):
                        for j in range(min(yy),max(yy)+1):
                            if (i,j) in t:
                                p[cx][cy] = 1
                            cy += 1
                        cy = 0
                        cx += 1

                    empty.append(p)
                    t = []
                    temp = findzero(board, (x1, y1),visit,target)
                    if temp != 0:
                        q.append(temp)
        return empty


    list_g = findempty(game_board,q1,list_g,visit_g,0)
    list_t = findempty(table,q2,list_t,visit_t,1)

	# 퍼즐 조각을 90도 회전시킴
    def rotate_90(l2):
        x = len(l2)
        y = len(l2[0])
        result = [[0 for _ in range(x)] for _ in range(y)]

        for i in range(x):
            for j in range(y):
                result[j][x-1-i] = l2[i][j]

        return result

	# 퍼즐 조각 갯수 count
    def counter(l):
        xl = len(l)
        yl = len(l[0])
        cnt = 0

        for i in range(xl):
            for j in range(yl):
                if l[i][j] == 1:
                    cnt += 1

        return cnt

    for l in list_g:
        for i in range(len(list_t)):
            l2 = list_t[i]
            if l2 != 0 and ((len(l) == len(l2) and len(l[0]) == len(l2[0])) or (len(l) == len(l2[0]) and len(l[0]) == len(l2))):
                if l == l2:
                    answer += counter(l)
                    list_t[i] = 0
                    break
                elif l == rotate_90(l2):
                    answer += counter(l)
                    list_t[i] = 0
                    break
                elif l == rotate_90(rotate_90(l2)):
                    answer += counter(l)
                    list_t[i] = 0
                    break
                elif l == rotate_90(rotate_90(rotate_90(l2))):
                    answer += counter(l)
                    list_t[i] = 0
                    break
    return answer

0개의 댓글

관련 채용 정보