[99클럽/파이썬 챌린저/13일차] 미로 보수

백준 30689번 미로 보수 G3

 

문제
각 칸에 '상', '하', '좌', '우' 중 하나가 표시되어 있고 세로로 N칸, 가로로 M칸인 N×M크기의 미로가 있다. 해당 칸으로 도착한 모든 사람은 미로에 표시된 방향으로 한 칸 이동한다. 이를 반복해 미로 밖으로 벗어나면 미로에서 탈출할 수 있다. 해당 그림의 파란색 경로는 미로에서 탈출하는 예시이다. 하지만 운이 나쁘다면 그림의 빨간색 경로와 같이 영원히 미로에서 탈출하지 못할 수도 있다! 영원히 탈출하지 못하는 상황을 막기 위해, 형진이는 미로를 보수하기로 했다.형진이는 미로에 원하는 만큼 점프대를 설치할 수 있다. 점프대를 설치하면 해당 위치에 도착한 사람들은 점프를 통해 바로 미로 밖으로 빠져나올 수 있다. 점프대를 설치하기 위해서는 해당 칸의 지리적 조건 등을 고려해야 하므로, 어느 칸에 설치하냐에 따라 점프대의 비용이 달라진다. 정확하게는 i행 j열의 칸에 점프대를 설치하는 것은 Costi,j만큼의 비용이 필요하다. 주어진 미로에서 최소한의 비용을 사용해 점프대를 설치해, 미로의 어느 칸에서 시작하더라도 탈출할 수 있도록 만들고 싶다. 필요한 최소한의 비용을 구해보자.

입력
첫째 줄에 미로의 행의 수 N, 열의 수 M이 공백을 사이에 두고 주어진다. 이어 N개의 줄에 걸쳐 미로판 B를 표현한 길이가 M인 문자열이 주어진다. 문자열은 대문자 알파벳 U, D, L, R만으로 이루어져 있다. 각각의 알파벳은 '상', '하', '좌', '우'를 뜻한다. 이어 N개의 줄에 걸쳐 미로의 각 칸에서 점프대를 설치하는 비용 정보 Cost가 공백을 사이에 두고 주어진다.


출력
미로의 어느 칸에서 시작하더라도 탈출할 수 있도록 하는 최소 비용을 출력한다.

 

 

그래프 이론, 그래프 탐색, 깊이 우선 탐색, 함수형 그래

 

사이클 내에서 최솟값을 찾아내는 문제이다.

깊이 우선 탐색으로 구현하였다.

 

 

import sys
sys.setrecursionlimit(10**6)

col, row = map(int, sys.stdin.readline().split())

maze = [sys.stdin.readline().rstrip() for _ in range(col)]
cost = [list(map(int, sys.stdin.readline().split())) for _ in range(col)]

move_y = {"D":1, "U":-1, "L":0, "R":0}
move_x = {"D":0, "U":0, "L":-1, "R":1}
visit = [[0] * row for _ in range(col)]
# 0 탐색 안함, -1 탐색 중, -2 탈출 가능

def dfs(i, j):
    global result
    visit[i][j] = -1
    
    dy, dx = i + move_y[maze[i][j]], j + move_x[maze[i][j]]

    if dy<0 or dx<0 or dy>=col or dx>=row:
        visit[i][j] = -2
        return

    if visit[dy][dx] == -2:
        visit[i][j] = -2
        return
    
    if visit[dy][dx] == -1:
        cy, cx = dy, dx
        min_cost = min(cost[dy][dx], cost[i][j])
        d = maze[dy][dx]
        dy, dx = dy + move_y[d], dx + move_x[d]
        while dy != cy or dx != cx:
            min_cost = min(min_cost, cost[dy][dx])
            d = maze[dy][dx]
            dy, dx = dy + move_y[d], dx + move_x[d]
        result += min_cost
    elif visit[dy][dx] == 0:
        dfs(dy, dx)

    visit[i][j] = -2
    
result = 0
for i in range(col):
    for j in range(row):
        if visit[i][j] == 0: dfs(i, j)
        
print(result)

 

---

 

while 문 내에서 min_cost 업데이트 순서로 인해 실패를 좀 많이 했다. 다음에는 주의하면서 풀어야겠다.