[시뮬레이션+DFS] (코드트리) 고대 문명 유적 탐사

✅ 풀이시간: 3시간 (14:37~17:36)

 

✅ 헤맨 부분:

 

1️⃣ 함수 return 문제:

• return값을 안적어줘서 TypeError: 'NoneType' object is not subscriptable (key 0) 에러가 떴음
• return을 rotate된 격자로 해야하는데 입력값을 해서 회전이 안되었음

 

2️⃣ 마지막에 최종 그래프를 그래프로 변환 안해줘서 (graph = f_test_graph를 안해서) 벽에 있는 유적이 없는데 자꾸 popleft()한다고 에러뜸 

 

 

3️⃣ 회전할때 -90도로 잘못 회전했음 

• 90도 코드는  rotate[j][len(data)-1-i] = data[i][j] *j는 깨끗하다로 외우자
• -90도 코드는  rotate[len(data)-1-j][i] = data[i][j]

 

4️⃣ DFS에서 path 부분을 path+[(r,c)] 로 재귀해서 최종으로 거친 모든 path값을 반환하지 못했음path.append((r,c))로 한후 dfs(~,path)로 순환해야 path를 최종적으로 반환시킬 수 있음 [관련 코드]

def dfs(r,c,visited,test_graph,path):
    for d in range(4):
        nr,nc = r+dr[d],c+dc[d]
        if not(0<=nr<5 and 0<=nc<5):
            continue
        if visited[nr][nc]==1:
            continue
        if test_graph[nr][nc]!=test_graph[r][c]:
            continue
        visited[nr][nc]=1
        path.append((nr,nc))
        dfs(nr,nc,visited,test_graph,path)


def get_ujuk(test_graph):
    visited = [[0]*5 for _ in range(5)]
    result= 0
    path_list = []
    for r in range(5):
        for c in range(5):
            if visited[r][c]!=1:
                path = [(r,c)]
                visited[r][c]=1
                dfs(r,c,visited,test_graph,path)
                if len(path)>=3:
                    result+=len(path)
                    path_list+=path

    return (result, path_list)

 

✅ 총평:

 

이전과 달리 문제를 글로 정확히 적고 풀었더니 문제 이해를 못해서 삽질한 시간을 줄일 수 있었고, 우선순위 문제도 잘 해결할 수 있었다. 힙에서 우선순위는 원소 순서대로 이뤄진다는 것도 확실히 알 수 있었다.

 

✅ 전체 코드

from heapq import heappush, heappop
from collections import deque
import copy
K,M = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(5)]
ujuk = list(map(int,input().split()))
ujuk = deque([u for u in ujuk])
dr = [-1,0,1,0]
dc = [0,1,0,-1]

def rotate(data):
    rotated = [[0]*len(data) for _ in range(len(data[0]))]
    for i in range(len(data)):
        for j in range(len(data[0])):
            rotated[j][len(data)-1-i]=data[i][j]
    return rotated

def filltodata(r,c):
    data = [[0]*3 for _ in range(3)]
    for i in range(r-1,r+2):
        for j in range(c-1,c+2):
            data[i-r+1][j-c+1]=graph[i][j]
    return data

def filltograph(test_graph,rotated,r,c):
    for i in range(r-1,r+2):
        for j in range(c-1,c+2):
            test_graph[i][j]=rotated[i-r+1][j-c+1]
    return test_graph


def dfs(r,c,visited,test_graph,path):
    for d in range(4):
        nr,nc = r+dr[d],c+dc[d]
        if not(0<=nr<5 and 0<=nc<5):
            continue
        if visited[nr][nc]==1:
            continue
        if test_graph[nr][nc]!=test_graph[r][c]:
            continue
        visited[nr][nc]=1
        path.append((nr,nc))
        dfs(nr,nc,visited,test_graph,path)


def get_ujuk(test_graph):
    visited = [[0]*5 for _ in range(5)]
    result= 0
    path_list = []
    for r in range(5):
        for c in range(5):
            if visited[r][c]!=1:
                path = [(r,c)]
                visited[r][c]=1
                dfs(r,c,visited,test_graph,path)
                if len(path)>=3:
                    result+=len(path)
                    path_list+=path

    return (result, path_list)

def insert_new_ujuk(path_list,ujuk,f_test_graph):
    path_hq = []
    for p_r,p_c in path_list:
        heappush(path_hq,(p_c,-1*p_r))
    while path_hq :
        p_c,p_r = heappop(path_hq)
        p_r = -1*p_r
        f_test_graph[p_r][p_c]=ujuk.popleft()
    return f_test_graph


while K>0:
    hq=[]
    for i in range(1,4):
        for j in range(1,4):
            rotated = filltodata(i,j)
            for k in range(3):
                rotated = rotate(rotated)
                test_graph = copy.deepcopy(graph)
                test_graph = filltograph(test_graph,rotated,i,j)
                result, path_list = get_ujuk(test_graph)
                heappush(hq,(-1*result,k,j,i,path_list,test_graph))
    f_result,f_k,f_j,f_i,f_path_list,f_test_graph = heappop(hq)
    f_result = -1*f_result
    if f_result == 0:
        break
    
    f_test_graph = insert_new_ujuk(f_path_list,ujuk,f_test_graph)


    while True:
        result, path_list = get_ujuk(f_test_graph)
        if result == 0:
            break
        else:
            f_result+=result
            f_test_graph = insert_new_ujuk(path_list,ujuk,f_test_graph)
    graph = f_test_graph
    print(f_result, end = " ")


    K-=1