[백준] 1035번 : 조각움직이기

1035번: 조각 움직이기

1035번: 조각 움직이기

📄 문제개요

• 5x5 크기의 보드가 주어졌을때, 모든 조각을 움직여서 연결 요소를 만드려고 한다.
• 조각을 최소로 움직여서 연결요소를 만들 수 있는 값을 구하시오.

🤔 문제분석

• 문제의 범위가 5x5이니, 완전탐색으로 문제를 접근해야한다.
• 우선은 연결요소가 될 수 있는 모든 경우의 수를 구한다.
• 연결요소를 순열로 현재 peice와 거리 계산을 하여 최소값을 갱신한다.

📝 의사코드

1. 별의 개수로 만들 수 있는 모든 조합의 경우의 수를 구한다.
2. 해당 조합이 연결요소인지 판별하여 조합을 줄인다.
   1. 그룹핑의 개수를 계산하는 너비 우선탐색을 계산한다.
3. 해당 조합을 다시 순열로 만들어서 현재 놓여진 peice값과 최소값을 갱신하며 계산한다.

💻 코드

import sys
from itertools import combinations
from itertools import permutations

from collections import deque

moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
input = sys.stdin.readline
graph = list(input().strip() for _ in range(5))

empty = []
peice = []
for i in range(5):
    for j in range(5):
        empty.append((i, j))
        if graph[i][j] == '*':
            peice.append((i, j))
            

def check(i, j):
    return 5 > i >= 0 and 5 > j >=0
            
def bfs(i, j, group):
    queue = deque()
    queue.append((i, j))
    new_graph = [['.' for _ in range(5)] for _ in range(5)]
    for g_y, g_x in group:
        new_graph[g_y][g_x] = '*'
        
    new_group = []
    new_group.append((i, j))
    visited = [[False for _ in range(5)] for _ in range(5)]
    visited[i][j] = True
    while queue:
        y, x = queue.popleft()
        for dy, dx in moves:
            ny, nx  = dy + y, dx + x
            if check(ny, nx) and not visited[ny][nx] and new_graph[ny][nx] == '*':
                visited[ny][nx] = True
                queue.append((ny, nx))
                new_group.append((ny, nx))
                
    return len(new_group) == len(group)

def isGroup(i, j, group):
    return bfs(i, j, group)

groups = list(combinations(empty, len(peice)))
groups = [new_g for new_g in groups if isGroup(new_g[0][0], new_g[0][1], new_g)]

def checkdif(source, target):
    return abs(source[0] - target[0]) + abs(source[1] - target[1])

ans = 10000

peice.sort()

for group in groups:
    for p_group in list(permutations(group, len(peice))):
        cost = 0
        for i in range(len(peice)):
            cost += checkdif(peice[i], p_group[i])    
            
        ans = min(cost, ans)
    
print(ans)

🎯 피드백 및 개선사항

• 해당문제는 5x5 배열이 주어졌으므로, 모든 경우의 수를 다 탐색해보아야하는 완전탐색으로 문제를 접근해야한다.
• 완전탐색으로 접근하지 않았을때, 문제의 접근이 조금 어려워진다.

❓다른사람은 어떻게 풀었을까?

• 나와 비슷하게 문제를 해결하신 분이 있다. 2차원 배열을 1차원 형태로 나타내어 풀어내셨다.

from itertools import combinations,permutations
from collections import deque
dR=[0,0,-1,1]
dC=[1,-1,0,0]
INF=9876543210

def calDist(A,B):
    return abs(A[0]-B[0])+abs(A[1]-B[1])

def isConnect(nowL):
    visited=[[0 for j in range(5)] for i in range(5)]
    tempL=[[0 for j in range(5)] for i in range(5)]
    for r,c in nowL:
        tempL[r][c]=1
    visited[nowL[0][0]][nowL[0][1]]=1
    cntCon=1
    q=deque([[nowL[0][0],nowL[0][1]]])
    while(q):
        r,c=q.popleft()
        for k in range(4):
            tempR=r+dR[k]
            tempC=c+dC[k]
            if 0<=tempR<5 and 0<=tempC<5 and visited[tempR][tempC]==0 and tempL[tempR][tempC]==1:
                visited[tempR][tempC]=1
                q.append([tempR,tempC])
                cntCon+=1
    if cntCon==size:
        return True
    else:
        return False

L=[]
for i in range(5):
    L.append(list(input()))
loc=[]
for i in range(5):
    for j in range(5):
        if L[i][j]=="*":
            loc.append([i,j])
size=len(loc)

comb=list(combinations([i for i in range(25)],size))
ans=INF
for numL in comb:
    # 번호->행렬
    nowLoc=[]
    for i in numL:
        r=i//5
        c=i%5
        nowLoc.append([r,c])

    # 연결여부확인
    if not isConnect(nowLoc):
        continue

    # 거리확인
    nowAns=INF
    per=list(permutations([i for i in range(size)],size))
    for myTuple in per:
        temp=0
        for i in range(size):
            temp+=calDist(loc[i],nowLoc[myTuple[i]])
        if temp<nowAns:
            nowAns=temp

    if nowAns<ans:
        ans=nowAns

print(ans)

• 서로 연결되어있는지 확인하는 방법을 DFS로 풀으셨다.

from itertools import combinations, permutations

def D(c):
    global res
    for per in permutations(c, N):
        dis = 0
        for idx, p in enumerate(per):
            dis += abs(Z[idx][0] - p[0]) + abs(Z[idx][1] - p[1])
        res = min(res, dis)
        

def DFS(x, y, n):
    global cnt
    cnt += 1
    ch[n]=1
    for k in range(4):
        xx, yy = dx[k]+x, dy[k]+y
        if (xx, yy) in com and ch[com.index((xx, yy))] == 0:
            DFS(xx, yy, com.index((xx, yy)))
        

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

gra = [list(map(str, input())) for _ in range(5)]
Z = []
arr = []
for i in range(5):
    for j in range(5):
        if gra[i][j] == '*':
            Z.append((i, j))
        arr.append((i, j))

N = len(Z) #조각수
res = 2147000000
for com in combinations(arr, N):
    cnt = 0
    ch = [0]*(N)
    DFS(com[0][0], com[0][1], 0)
    if cnt != N: continue
    D(com)

print(res)