삼성 sw 역량 테스트 문제이다
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for _ in range(n):
graph.append(list(input().strip()))
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
for i in range(n):
for j in range(n):
if graph[i][j] == 'B':
bx = i
by = j
elif graph[i][j] == 'R':
rx = i
ry = j
q = deque([(rx, ry, bx, by)])
visited = [(rx,ry,bx,by)] #
cnt = 0
while q:
for _ in range(len(q)): #
rx, ry, bx, by = q.popleft()
if graph[rx][ry] == 'O':
print(cnt)
exit()
if cnt > 10:
print(-1)
exit()
for i in range(4):
rnx = rx
rny = ry
bnx = bx
bny = by
while True: #
rnx += dx[i]
rny += dy[i]
if graph[rnx][rny] == '#': # 벽을만나면 다시 그전으로 롤백
rnx -= dx[i]
rny -= dy[i]
break
if graph[rnx][rny] == 'O': #구멍에 빠지면 break
break
while True:
bnx += dx[i]
bny += dy[i]
if graph[bnx][bny] == '#':
bnx -= dx[i]
bny -= dy[i]
break
if graph[bnx][bny] == 'O':
break
if graph[bnx][bny] == 'O': #파란공이 구멍에 빠지면
continue
if rnx == bnx and rny == bny: # 두공이 같은 위치에 있을 경우
if abs(rnx-rx) + abs(rny-ry) > abs(bnx-bx) + abs(bny-by):
rnx -= dx[i]
rny -= dy[i]
else:
bnx -= dx[i]
bny -= dy[i]
if (rnx,rny,bnx,bny) not in visited:
visited.append((rnx,rny,bnx,bny))
q.append((rnx, rny, bnx, bny))
cnt += 1
print(-1)
for _ in range(len(q)):
~~
cnt += 1
이런 방식을 통해서도 bfs를 통해서도 depth를 구할수 있다는 점을 알게되었다.