[BOJ/백준] 1944 복제 로봇

문제 링크 : https://www.acmicpc.net/problem/1944

1944번: 복제 로봇

 

접근법이 떠오르지 않아 밑에 알고리즘 분류를 보고 해결한 문제이다.

 

MST로 해결하였다.

 

출발점과 모든 열쇠점을 연결하는데 이때 가중치가 최소가 되어야한다. 그러므로 MST로 해결하면 된다.

이때 주어진 미로를 그래프로 변환해야한다.

이것은 각 지점별로 다른 지점까지 최단경로를 계산해서 만들어주면 된다.

 

그래서 나는 미로를 좀 수정했다.

S를 1로, K를 2부터 번호를 쭉 번호를 매기고 벽은 -1, 빈칸은 0으로 수정했다.

그러면 아래와 같을 것이다.

-1 -1 -1 -1 -1
-1  1  0  0 -1
-1  0  0  0 -1
-1  2 -1  3 -1
-1 -1 -1 -1 -1

 

그러면 양수인 부분이 방문해야하는 점들이 된다.

 

다음 각 점에서 최단경로를 구해야한다. 이는 가중치가 1인 그래프이므로 BFS로 해결했다.

그래서 양수인 점에서 BFS를 시작해서 시작점이 아닌 다른 양수가 있는 점을 방문하면 간선 정보를 생성했다.

이때 생성된 간선은 중복이 발생하는데 상관없다. MST를 수행할때 이미 연결된 것이라면 지나가기 때문이다.

 

이제 간선정보들을 모아서 이제 MST를 수행후 가중치의 합을 출력하면 된다.

MST는 크루스칼을 사용했다.

 

from sys import stdin
from collections import deque

input = stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]

n,m = map(int, input().split())
board = []
visited = [[0] * n for _ in range(n)]
visited_num = 0

index = 2
targets = []
for x in range(n):
    board.append(list(input().strip()))
    for y in range(n):
        if board[x][y] == '1':
            board[x][y] = -1
        elif board[x][y] == '0':
            board[x][y] = 0
        elif board[x][y] == 'S':
            board[x][y] = 1
            targets.append((x,y))
        elif board[x][y] == 'K':
            board[x][y] = index
            index += 1
            targets.append((x,y))

parent = [i for i in range(index)]

def solv():
    edges = set_edges()
    edges.sort(key=lambda x:x[2])
    print(kruskal(edges))

def kruskal(edges):
    edge_count = 0
    cost = 0
    for a,b,c in edges:
        if not is_same_parent(a,b):
            union(a,b)
            edge_count += 1
            cost += c
            if edge_count == index-2:
                return cost
    return -1
def find(target):
    global parent
    if parent[target] == target:
        return target
    parent[target] = find(parent[target])
    return parent[target]

def union(a,b):
    a = find(a)
    b = find(b)

    if a != b:
        parent[a] = b

def is_same_parent(a,b):
    return find(a) == find(b)

def set_edges():
    edges = []
    for x,y in targets:
        edges.extend(bfs(x,y))

    return edges
def bfs(sx,sy):
    global visited,visited_num
    start = board[sx][sy]

    q = deque([(sx,sy,0)])

    visited_num += 1
    visited[sx][sy] = visited_num

    edge = []
    while q:
        x,y,cnt = q.pop()

        if board[x][y] > 0 and board[x][y] != start:
            edge.append((start,board[x][y],cnt))
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if point_validator(nx,ny):
                visited[nx][ny] = visited_num
                q.appendleft((nx,ny,cnt+1))
    return edge
def point_validator(x,y):
    if x < 0 or y < 0 or x >= n or y >= n:
        return False
    elif visited[x][y] == visited_num:
        return False
    elif board[x][y] == -1:
        return False
    return True

solv()