문제
접근
앞에서 풀었던 불 문제와 유사하다.
다른 점은 종료 조건이다.
앞에선 판을 벗어날 수 있으면 종료했지만, 여기서는 종료 지점이 정해져 있다.
주의할 점은 종료지점에는 물이 차지않는다!
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
from collections import deque
import sys
dx = [0,0,-1,1]
dy = [1,-1,0,0]
def waterBFS():
waterSize = len(waterQ)
while waterSize:
nowx, nowy = waterQ.popleft()
for x, y in zip(dx,dy):
nx = x+nowx
ny = y+nowy
if nx == end[0] and ny == end[1]:
continue
if nx < 0 or nx >= w or ny < 0 or ny >= h or board[ny][nx] == -1:
continue
if board[ny][nx] == 0:
board[ny][nx] = board[nowy][nowx] + 1
waterQ.append((nx,ny))
waterSize -= 1
def personBFS(start):
q = deque()
q.append(start)
visit[start[1]][start[0]] = 1
while q:
qSize = len(q)
while qSize:
nowx, nowy = q.popleft()
if nowx == end[0] and nowy == end[1]:
return visit[nowy][nowx] - 1
for x, y in zip(dx,dy):
nx = x + nowx
ny = y + nowy
if nx < 0 or nx >= w or ny < 0 or ny >= h or board[ny][nx] == -1:
continue
if board[ny][nx] == 0 and visit[ny][nx] == 0:
visit[ny][nx] = visit[nowy][nowx] + 1
q.append((nx,ny))
qSize -= 1
waterBFS()
return 'KAKTUS'
h, w = map(int,input().split(' '))
board = [[0] * (w) for _ in range(h)]
visit = [[0] * (w) for _ in range(h)]
waterQ = deque()
for i in range(h):
item = input()
for j in range(w):
if item[j] == 'X':
board[i][j] = -1
elif item[j] == '*':
board[i][j] = 1
waterQ.append((j,i))
elif item[j] == '.':
board[i][j] = 0
elif item[j] == 'S':
board[i][j] = 0
start = (j,i)
else:
board[i][j] = 0
end = (j,i)
waterBFS()
ans = personBFS(start)
print(ans)