https://www.acmicpc.net/problem/30689

미로가 있고, 각 칸에는 어디로 가야하는지 방향이 표시되어 있을때 미로를 탈출하지 못하는 경로가 있다면 해당 경로에 탈출지점을 넣어두려고 한다. 이때 설치 비용이 각 칸 별로 있을 때 설치비용을 최소화하라는 문제이다.

Python

1차 실패 - BFS

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

maze = [list(input().strip()) for _ in range(n)]

cost = [list(map(int, input().split())) for _ in range(n)]

visited = [["N"] * m for _ in range(n)] # 방문 안 했으면 N, 탈출할 수 있으면 O, 사이클이면 C


def findNext(y, x, maze):
  dir = {"L": [0, -1], "R": [0, 1], "U": [-1, 0], "D":[1, 0]}
  dy, dx = dir[maze[y][x]]
  return [y + dy, x + dx]

cycles = []

for i in range(n):
  for j in range(m):
    if visited[i][j] == "N":
      que = [(i, j)]
      idx = 0
      visited[i][j] = "O"
      
      v = set()
      v.add((i, j))
      
      cycle = False
      
      while idx < len(que):
        y, x = que[idx]
        idx += 1
        ny, nx = findNext(y, x, maze)
        
        if 0 <= ny < n and 0 <= nx < m:
          if visited[ny][nx] == "N" and (ny, nx) not in v:
            que.append((ny, nx))
            visited[ny][nx] = "O"
            v.add((ny, nx))
          elif (ny, nx) in v: # 탐색 중 사이클이 생김
            circle = [(ny, nx)]
            y, x = findNext(ny, nx, maze)
            while y != ny or x != nx:
              circle.append((y, x))
              y, x = findNext(y, x, maze)
            cycles.append(circle)
            cycle = True
            
          elif visited[ny][nx] == "C": # 사이클이 있는 코스랑 만남
            cycle = True
      
      if cycle:
        for y, x in que:
          visited[y][x] = "C"

ans = 0
for c in cycles:
  minCost = 1000
  for y, x in c:
    minCost = min(minCost, cost[y][x])
  ans += minCost
  
print(ans)

사이클을 찾아야한다고 생각해서 BFS로 접근했다. 전체 칸을 돌면서 방문하지 않은 칸일 때 BFS를 시작한다.

BFS를 위해 전체 visited와 현재 탐색중인 경로를 저장할 v라는 집합을 만들었고, 만약 방문하지 않은 칸이라면 que에 추가해주고, 방문하지 않은 칸인데 v 안에 있다면 사이클이 있다는 뜻이므로 해당 칸부터 사이클을 다시 탐색하면서 전체 사이클을 구하였다.
만약 방문한 칸이고 그 표시가 C라면 이는 사이클이 있는 경로라는 뜻이므로 cycle을 true로 만들어주고 visited에는 C로 표시해주었다.

마지막으로 찾은 사이클들을 모아서 각 사이클의 최소 비용을 구하고 답을 도출했다.

그리고 시간초과로 실패했다. 아마 최악의 경우가 2000의 3제곱이라서 그런 것 같다.

2차 시도 - DFS

다른 사람의 코드를 참고해서 해결했다.

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

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

maze = [list(input().strip()) for _ in range(n)]

cost = [list(map(int, input().split())) for _ in range(n)]

visited = [[True] * m for _ in range(n)] # 방문 안 했으면 N, 탈출할 수 있으면 O, 사이클이면 C


def findNext(y, x):
  dir = {"L": [0, -1], "R": [0, 1], "U": [-1, 0], "D":[1, 0]}
  dy, dx = dir[maze[y][x]]
  return [y + dy, x + dx]

stack = []

answer = 0

def dfs(y, x):
  global answer
  
  ny, nx = findNext(y, x)
  
  if 0 <= ny < n and 0 <= nx < m:
    if visited[ny][nx]:
      visited[ny][nx] = False
      stack.append((ny, nx))
      dfs(ny, nx)
      stack.pop()
    else:
      minCost = 1000
      idx = len(stack) - 1
      
      # 방문 했다면 stack을 거꾸로 돌면서 minCost 계산, 만약 탈출가능이라면 idx가 -1일 것이고 사이클이라면 idx >= 0인 상태에서 stack[idx] == (ny, nx)일 것
      while idx >= 0 and stack[idx] != (ny, nx):
        i, j = stack[idx]
        minCost = min(minCost, cost[i][j])
        idx -= 1
    
      # 그래서 사이클로 판명되면 
      if idx >= 0 and stack[idx] == (ny, nx):
        answer += min(minCost, cost[ny][nx])

for i in range(n):
  for j in range(m):
    if visited[i][j]:
      stack.append((i, j))
      dfs(i, j)
      stack.pop()

print(answer)

DFS로 탐색을 대체하였는데 방문하지 않은 칸이라면 DFS를 다시 호출하고, 방문한 칸이라면 탐색중이던 경로인 stack을 거꾸로 돌면서 minCost를 계산했다.
만약 minCost 계산하는 while의 탈출이 stack[idx] == (ny, nx)라면 이는 사이클이 있다는 뜻이 되므로 answer에 계산한 minCost를 더해주었다.

이렇게 하니까 RecursionError의 위험이 있긴 했으나 통과할 수 있었다.

시도 3 - BFS 수정

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
maze = [list(input().strip()) for _ in range(n)]
cost = [list(map(int, input().split())) for _ in range(n)]
visited = [[True] * m for _ in range(n)]

def findNext(y, x, maze):
  dir = {"L": [0, -1], "R": [0, 1], "U": [-1, 0], "D":[1, 0]}
  dy, dx = dir[maze[y][x]]
  return [y + dy, x + dx]

ans = 0

for i in range(n):
  for j in range(m):
    if visited[i][j]:
      que = [(i, j)]
      idx = 0
      visited[i][j] = False
      
      while idx < len(que):
        y, x = que[idx]
        idx += 1
        ny, nx = findNext(y, x, maze)
        
        if 0 <= ny < n and 0 <= nx < m:
          if visited[ny][nx]:
            que.append((ny, nx))
            visited[ny][nx] = False
          else:
            ci = idx - 1
            minCost = cost[ny][nx]
            while ci >= 0 and que[ci] != (ny, nx):
              cy, cx = que[ci]
              minCost = min(minCost, cost[cy][cx])
              ci -= 1
            
            if ci >= 0 and que[ci] == (ny, nx):
              ans += minCost

print(ans)

DFS에서 사이클 탐지의 논리를 그대로 가져와서 BFS에 적용시켰다. 그리고 400ms 정도 줄어든 것을 확인했다.