from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
r, c = map(int, input().split())
g = [list(input()) for _ in range(r)]
spread = [[-1] * c for _ in range(r)]
q = deque()
for i in range(r):
for j in range(c):
if g[i][j] == '*':
q.append((i, j))
spread[i][j] = 0
while q:
x, y = q.popleft()
for d in range(4):
nx, ny = x + dx[d], y +dy[d]
if nx < 0 or nx >= r or ny < 0 or ny >= c:
continue
if spread[nx][ny] == -1 and g[nx][ny] != 'X' and g[nx][ny] != 'D':
q.append((nx, ny))
spread[nx][ny] = spread[x][y] + 1
find = [[-1] * c for _ in range(r)]
for i in range(r):
for j in range(c):
if g[i][j] == 'S':
sx, sy = i, j
elif g[i][j] == 'D':
ddx, ddy = i, j
q = deque()
q.append((sx, sy))
find[sx][sy] = 0
while q:
x, y = q.popleft()
for d in range(4):
nx, ny = x + dx[d], y +dy[d]
if nx < 0 or nx >= r or ny < 0 or ny >= c:
continue
if find[nx][ny] == -1 and g[nx][ny] != 'X':
if g[nx][ny] == 'D':
q.append((nx, ny))
find[nx][ny] = find[x][y] + 1
if spread[nx][ny] > find[x][y] + 1:
q.append((nx, ny))
find[nx][ny] = find[x][y] + 1
if find[ddx][ddy] == -1:
print("KAKTUS")
else:
print(find[ddx][ddy])코드 1번 : 밑의 반례 (게시판에서 주움) 와 같이 애초에 물과 관련 없이 이동 가능한 경우를 놓침
10 15
........X......
..XXXXX.X.....
X.....X.X.....
.X.S..X.X......
D.X...X.XXXXXXX
.X....X........
.X....X.XXXXXXX
.XXXXXX.X......
........X......
XXXXXXXXX...*..
from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
r, c = map(int, input().split())
g = [list(input()) for _ in range(r)]
spread = [[-1] * c for _ in range(r)]
q = deque()
for i in range(r):
for j in range(c):
if g[i][j] == '*':
q.append((i, j))
spread[i][j] = 0
while q:
x, y = q.popleft()
for d in range(4):
nx, ny = x + dx[d], y +dy[d]
if nx < 0 or nx >= r or ny < 0 or ny >= c:
continue
// 밑의 조건 부분은 아니고 밑에 고슴도치 이동 부분이 틀린듯
if spread[nx][ny] == -1 and g[nx][ny] != 'X' and g[nx][ny] != 'D':
q.append((nx, ny))
spread[nx][ny] = spread[x][y] + 1
find = [[-1] * c for _ in range(r)]
for i in range(r):
for j in range(c):
if g[i][j] == 'S':
sx, sy = i, j
elif g[i][j] == 'D':
ddx, ddy = i, j
q = deque()
q.append((sx, sy))
find[sx][sy] = 0
while q:
x, y = q.popleft()
for d in range(4):
nx, ny = x + dx[d], y +dy[d]
if nx < 0 or nx >= r or ny < 0 or ny >= c:
continue
if find[nx][ny] == -1 and g[nx][ny] != 'X':
if g[nx][ny] == 'D' or g[nx][ny] == '.':
q.append((nx, ny))
find[nx][ny] = find[x][y] + 1
if spread[nx][ny] > find[x][y] + 1:
q.append((nx, ny))
find[nx][ny] = find[x][y] + 1
if find[ddx][ddy] == -1:
print("KAKTUS")
else:
print(find[ddx][ddy])이건 왜 틀렸는지 사실 잘 모르겠음 반례 못찾음
from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
r, c = map(int, input().split())
g = [list(input()) for _ in range(r)]
spread = [[-1] * c for _ in range(r)]
q = deque()
for i in range(r):
for j in range(c):
if g[i][j] == '*':
q.append((i, j))
spread[i][j] = 0
while q:
x, y = q.popleft()
for d in range(4):
nx, ny = x + dx[d], y +dy[d]
if nx < 0 or nx >= r or ny < 0 or ny >= c:
continue
if spread[nx][ny] == -1 and g[nx][ny] == '.':
q.append((nx, ny))
spread[nx][ny] = spread[x][y] + 1
find = [[-1] * c for _ in range(r)]
for i in range(r):
for j in range(c):
if g[i][j] == 'S':
sx, sy = i, j
elif g[i][j] == 'D':
ddx, ddy = i, j
q = deque()
q.append((sx, sy))
find[sx][sy] = 0
while q:
x, y = q.popleft()
for d in range(4):
nx, ny = x + dx[d], y +dy[d]
if nx < 0 or nx >= r or ny < 0 or ny >= c:
continue
if find[nx][ny] == -1 and g[nx][ny] != 'X':
// 이동을 못하는 곳 (X인부분)도 아닌데 물이 이동하지 못한 곳 = 애초에 물이 닿지 않는 곳 -> 이동 가능하다
// if g[nx][ny] == 'D' or g[nx][ny] == '.': 이거랑 무슨 차이일까? g에서는 . 이어도 나중에 물이 이동할 가능성이 있다...? -> 모르겠음
if spread[nx][ny] == -1:
q.append((nx, ny))
find[nx][ny] = find[x][y] + 1
// 물보다 고슴도치가 먼저 도착한 경우 이동이 가능하다
elif spread[nx][ny] > find[x][y] + 1:
q.append((nx, ny))
find[nx][ny] = find[x][y] + 1
if find[ddx][ddy] == -1:
print("KAKTUS")
else:
print(find[ddx][ddy])정답이 나온 코드 : 먼저 bfs로 물을 이동시켜주고, 고슴도치를 이동시켜주는데
고슴도치가 이동 가능한 조건은 1. 돌이 놓인 곳이 아님 2. 물이 없거나 물보다 고슴도치가 먼저 이동가능한 경우
^^~