[백준] 30689 파이썬

문제

---

• 백준 30689 (골드 3)

백준 30689

미로가 주어졌을 때, 미로의 어느 칸에서 시작하더라도 탈출할 수 있도록 적절하게 점프대를 설치하는 문제였다.
여기서 문제의 조건은 각 칸마다 설치대를 설치하는 비용을 입력으로 주고 최소의 비용으로 설치대를 설치하는 것이였다.

내 코드

---

dfs를 활용하여서 코드를 구현하였다.
모든 칸에서 탈출이 가능해야 하므로 모든 칸을 돌면서 dfs를 돌아주었다.
여기서 각 dfs에서 거쳤던 칸들은 다시 체크하지 않아도 되므로 만약에 방문한 칸이라면 스킵해주었다.
만약 탈출하지 못하고 순환하는 경우가 생긴다면 그 중 최소 비용인 곳에 점프대를 설치해주었다.

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n, m = map(int, input().split())

maze = [list(input().strip()) for _ in range(n)]
cost = [list(map(int, input().strip().split())) for _ in range(n)]
result = 0
visited = [[False] * m for _ in range(n)]
queue = deque()

dic = {}
dic['U'] = (-1, 0)
dic['D'] = (1, 0)
dic['R'] = (0, 1)
dic['L'] = (0, -1)


def dfs(x, y) :
    global result

    nx = x + dic[maze[x][y]][0]
    ny = y + dic[maze[x][y]][1]

    if 0 <= nx < n and 0 <= ny < m :
        if not visited[nx][ny]:
            visited[nx][ny] = True
            queue.append((nx, ny))
            dfs(nx, ny)
            queue.pop()
        else :
            min_cost = float('inf')
            index = len(queue) - 1

            while index >= 0 and (queue[index][0] != nx or queue[index][1] != ny) :
                i, j = queue[index]
                min_cost = min(min_cost, cost[i][j])
                index -= 1

            if index >= 0 and queue[index][0] == nx and queue[index][1] == ny :
                result += min(min_cost, cost[queue[index][0]][queue[index][1]])

for i in range(n) :
    for j in range(m) :
        if not visited[i][j]:
            visited[i][j] = True
            queue.append((i, j))
            dfs(i, j)
            queue.pop()

print(result)