[백준] 3055번 : 탈출

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

3055번: 탈출

해당 문제는 너비우선탐색으로 문제를 해결 하였습니다.

1. Water와 Bacoon을 너비우선탐색하여 업데이트합니다.

2. Water와 Baccon을 비교하여 방문 가능한 그래프를 업데이트합니다.

3. 다시 그래프를 너비우선탐색으로 탐색하여 최소값을 구합니다.

from copy import deepcopy
from collections import deque
from pprint import pprint
R ,C = map(int, input().split()) # R행 C열
move = ((0,1), (0,-1), (1,0), (-1,0))
graph = []
start = [0,0]
end = [0,0]
for i in range(R):
    char = list(input())
    for j in range(C):
        if char[j] =='D': # 비버 동굴 위치
            end = [i,j]
        elif char[j] == 'S': # 너구리 위치
            start = [i,j]
            
    graph.append(char)
    

def bfs(arr, queue):
    while queue:
        y,x, cost = queue.popleft()
        for dy, dx in move:
            ny = dy + y
            nx = dx + x
            if R > ny >=0 and C > nx >= 0 and not visited[ny][nx] and graph[ny][nx] == '.':
                queue.append((ny,nx, cost + 1))
                arr[ny][nx] = cost + 1
                visited[ny][nx] = True
INF = int(10e6)
water = [[INF for _ in range(C)] for _ in range(R)]
baccon = [[INF for _ in range(C)] for _ in range(R)]

visited = [[False for _ in range(C)] for _ in range(R)]
queue = deque()
for i in range(R):
    for j in range(C):
        if graph[i][j] == '*':
                visited[i][j] = True
                queue.append([i,j,0])

bfs(water, queue)
visited = [[False for _ in range(C)] for _ in range(R)]
queue = deque()
for i in range(R):
    for j in range(C):
        if graph[i][j] == 'S':
                visited[i][j] = True
                queue.append((i,j,0))
                
bfs(baccon, queue)

for i in range(R):
    for j in range(C):
        if water[i][j] > baccon[i][j]:
            graph[i][j] = '.'
        else:
            graph[i][j] = '*'
                
                
y1,x1 = start
y2, x2 = end
graph[y1][x1] = '.'
graph[y2][x2] = '.'

visited = [[False for _ in range(C)] for _ in range(R)]
visited [y1][x1] = True
queue.append((y1, x1, 0))
bfs(graph, queue)
if graph[y2][x2] == '.':
    print('KAKTUS')
else:
    print(graph[y2][x2])

시간복잡도와 공간복잡도를 줄 일 수 있는 방법으로는 너비우선탐색을 단 한번으로 문제를 해결 할 수 있습니다.

너비우선탐색은 Queue 형태이기 때문에 너구리를 큐에 먼저 넣고 그다음에 물을 넣음으로서 물부터 방문해가면서 그래프를 업데이트 한다면 너비우선탐색을 단 한번으로 최대의 거리값을 구 할 수 있겠습니다.