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

🥚문제

---

🥚입력/출력

---

🍳코드

from collections import deque
import sys
input = sys.stdin.readline

R, C = map(int, input().split())
arr = [list(input().strip()) for _ in range(R)]

moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# 물이 차는 시간을 기록
water = [[0]*C for _ in range(R)]


def water_bfs(row, col, water_visited):
    q = deque([(row, col)])
    water_visited[row][col] = True
    water[row][col] = 0
    while q:
        row, col = q.popleft()
        for move in moves:
            new_row = row + move[0]
            new_col = col + move[1]

            if 0 <= new_row < R and 0 <= new_col < C:
                if not water_visited[new_row][new_col]:
                    if arr[new_row][new_col] == '.':
                        # water에 물이 차는 시간 기록이 없을 때
                        if water[new_row][new_col] == 0:
                            water[new_row][new_col] = water[row][col] + 1
                        # water에 물이 차는 시간 기록이 있다면 min값으로 갱신한다
                        elif water[new_row][new_col] > 0:
                            water[new_row][new_col] = min(
                                water[new_row][new_col], water[row][col] + 1)
                        water_visited[new_row][new_col] = True
                        q.append((new_row, new_col))


# 고슴도치가 움직이는 시간을 기록
visited = [[0]*C for _ in range(R)]


def bfs(row, col):
    q = deque([(row, col)])
    visited[row][col] = 0

    while q:
        row, col = q.popleft()
        for move in moves:
            new_row = row + move[0]
            new_col = col + move[1]
            if 0 <= new_row < R and 0 <= new_col < C:
                if not visited[new_row][new_col]:
                    # 비어 있는 곳인가?
                    if arr[new_row][new_col] == '.':
                        # 다음 움직일 곳이 물이 차있지 않아야한다
                        # 아예 물이 들어와있지 않거나, 물이 들어오기 전에 고슴도치가 지나감
                        if water[new_row][new_col] == 0 or water[new_row][new_col] > visited[row][col] + 1:
                            visited[new_row][new_col] = visited[row][col] + 1
                            q.append((new_row, new_col))
                    # 비버의 굴인가?
                    elif arr[new_row][new_col] == 'D':
                        visited[new_row][new_col] = visited[row][col] + 1
                        q.append((new_row, new_col))


for r in range(R):
    for c in range(C):
        if arr[r][c] == '*':
            tmp_visited = [[False]*C for _ in range(R)]
            water_bfs(r, c, tmp_visited)

""" water 출력
for water_row in water:
    print(water_row)
"""

for r in range(R):
    for c in range(C):
        if arr[r][c] == 'S':
            bfs(r, c)

""" visited 출력
print('-'*15)
for visited_row in visited:
    print(visited_row)
"""

# 비버의 굴로 가는 시간 구하기
ans = 0
for r in range(R):
    for c in range(C):
        if arr[r][c] == 'D':
            ans = visited[r][c]
            break
if ans == 0:
    print("KAKTUS")
else:
    print(ans)

---

🧂아이디어

탐색 (BFS)

water_bfs(row, col, water_visited): 물이 차는 시간을 기록

• 물('*')은 여러 곳에 위치할 수 있다. 따라서 물이 어떻게 차오르는지 알기 위해서는 모든 물의 위치에서 BFS를 해야 한다.

• 물이 있는 위치(r1, c1)에서 BFS를 할 때, tmp_visited를 이용하여 현재 시행중인 BFS의 방문 기록을 저장한다. 이후 다시 다른 물이 있는 위치(r2, c2)에서 BFS를 하게 되면 tmp_visited는 초기화된다.

• water: 전체적으로 물이 차오르는 시간이 기록되는 리스트이다. water_bfs를 통해 정보가 갱신된다.

• 현재 위치를 (row, col)라고 하면 다음 이동할 위치는 (new_row, new_col)라고 한다.
  • water[new_row][new_col]가 0이면 아직 방문하지 않았으므로 water[row][col] + 1로 갱신 (시간 증가)
  • water[new_row][new_col]를 이미 방문한 경우(> 0)에는, 다음 이동에 걸리는 시간이 현재 water에 기록되어 있는 이동 시간보다 적을 때 갱신해준다. water[new_row][new_col] = min(water[new_row][new_col], water[row][col] + 1) = 최초로 그 지역에 물이 차는 시간을 기록한다.

bfs(row, col): 고슴도치가 움직이는 시간을 기록

• water 리스트를 이용하여 물이 차있는 곳인지 확인하는 것 외에는 일반적인 BFS와 같다.

• (new_row, new_col)이 빈칸일 때, 물이 차있는지 확인해야 한다.
  • water[new_row, new_col]의 값이 0이라면 물이 찬 적이 없으므로 지나갈 수 있다.
  • water[new_row, new_col]의 값이 고슴도치가 (new_row, new_col)로 이동했을 때 걸리는 시간인 visited[row][col] + 1 보다 크다면 고슴도치가 지나간 이후에 물이 차는 것이므로 고슴도치는 이 지역을 지나갈 수 있다.

---

🧐

다음 움직일 곳에 물이 차지 않았는지 확인하는 코드를

if water[new_row][new_col] != visited[row][col] + 1:

단순히 고슴도치가 new_row, new_col을 지나가는 시간과 같은지를 확인했기 때문에 틀렸다. 이를 고치고 통과!
물이 찬 적이 없거나, 물이 찬 적이 있더라도 고슴도치가 지나간 이후에 차는 것은 상관 없기 때문에 두 경우 다 고려했어야 한다.