[백준] 1944 복제 로봇

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

열쇠의 위치에서 로봇이 분열하여 새로운 로봇으로 이동이 가능합니다.

그로 인해 로봇의 위치와 열쇠의 모든 위치들의 상호 거리를 구한 후 해당 위치를 노드로 하는 최소 신장 트리를 구해야했습니다.

 

BFS 를 이용하여 특정 위치(로봇 시작 위치, 열쇠의 위치)를 시작으로 하여 다른 지점까지의 거리를 모두 구했습니다.

거리의 정보는 딕셔너리 형태로 관리하였으며, 키는 특정 위치의 좌표를 값은 거리와 다른 노드의 좌표를 기록하였습니다.

2) 알고리즘

• BFS
• MST (최소신장트리)

3) 풀이 코드

사용 언어 - Python

import sys
import heapq
from collections import deque
sys.stdin = open('input.txt')


# 특정 좌표에서 다른 로봇 또는 열쇠 좌표까지의 거리 구하기
def bfs(y, x):
    visited = [[0] * N for _ in range(N)]
    q = deque([(y, x)])
    visited[y][x] = 1

    while q:
        r, c = q.popleft()
        visit = visited[r][c]

        for k in range(4):
            nr = r + dr[k]
            nc = c + dc[k]

            if 0 <= nr < N and 0 <= nc < N and not visited[nr][nc] and maze[nr][nc] != '1':
                # 다음 좌표가 다른 로봇 또는 열쇠 좌표인 경우, 딕셔너리에 추가
                if maze[nr][nc] in {'K', 'S'}:
                    nodes[(nr, nc)] = nodes.get(
                        (nr, nc), []) + [(visit, (y, x))]
                visited[nr][nc] = visit + 1
                q.append((nr, nc))


# 로봇과 열쇠의 최단 거리를 연결하여 움직인 횟수의 최솟값 구하기
def solution(y, x):
    h = [(0, (y, x))]
    ans = 0
    visited = set()

    while h:
        weight, coor = heapq.heappop(h)
        if coor not in visited:
            visited.add(coor)
            ans += weight
            for next in nodes[coor]:
                heapq.heappush(h, next)

    return ans


# 위, 오른쪽, 아래, 왼쪽
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

# 입력 데이터
N, M = map(int, sys.stdin.readline().split())
maze = [list(sys.stdin.readline().strip()) for _ in range(N)]

# 로봇 또는 열쇠들의 각 좌표간 거리 정보
nodes = {}

for i in range(N):
    for j in range(N):
        # 로봇이거나 열쇠인 좌표일때만 BFS 탐색
        if maze[i][j] in {'S', 'K'}:
            bfs(i, j)

            # 모두 연결되어 있는게 아니라면, -1 출력 및 종료
            if len(nodes.keys()) < M:
                print(-1)
                exit(0)

# 최소 거리 구하기
print(solution(*list(nodes.keys())[0]))

---

🔗 문제 링크

- https://www.acmicpc.net/problem/1944

1944번: 복제 로봇

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다