[BOJ] 13460
me
- 동시에 만나는 것을 처리하지 못했다
- visited는 고려하지 않았다
dfs를 생각했던 것 같다. 죄다 도는.. - 입력을 받으면서 red,blue를 처리해줬더니 위치를 못찾았다.
입력 처리 후에 다시 red,blue를 탐색하니 제대로 위치를 찾았다. - move와 dfs 처리는 잘했지만 bfs..였다는 점
- 조건 분석을 잘해야겠다.
solution
import sys
from collections import deque
input = sys.stdin.readline
N,M= map(int,input().split())
box=[list(input().strip()) for _ in range(N)]
visited = [[[[False]*M for _ in range(N)] for _ in range(M)] for _ in range(N)]
rx,ry,bx,by=[0]*4
for i in range(N):
for j in range(len(box)):
if box[i][j]=='R': rx=i; ry=j;
elif box[i][j]=='B': bx=i; by=j;
for b in box: print(b)
visited[rx][ry][bx][by] = True
print(rx,ry,bx,by)
def move(dx,dy,x,y):
# 도착 위치 반환
count=0
while box[x+dx][y+dy]!="#" and box[x][y]!="O":
x+=dx
y+=dy
count+=1
return x,y,count
q=deque([[0,rx,ry,bx,by]])
dx=[-1,0,+1,0]
dy=[0,+1,0,-1]
while q:
cnt,rx,ry,bx,by=q.popleft()
print('start---',cnt,rx,ry,bx,by)
for i in range(4):
nrx,nry,rcnt=move(dx[i],dy[i],rx,ry)
nbx,nby,bcnt=move(dx[i],dy[i],bx,by)
print(i,nrx,nry,nbx,nby)
if box[nbx][nby] == "O":
# 파랑색이 구멍에 빠져 버린 것
continue
if box[nrx][nry] == "O":
# 빨간색 도착!
print(cnt+1)
sys.exit()
if nrx==nbx and nry==nby:
if rcnt>bcnt:
nrx-=dx[i]
nry-=dy[i]
else:
nbx-=dx[i]
nby-=dy[i]
if not visited[nrx][nry][nbx][nby]:
visited[nrx][nry][nbx][nby] = True
q.append([cnt+1,nrx, nry, nbx, nby])
print(-1)
Author And Source
이 문제에 관하여([BOJ] 13460), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kinnyeri/BOJ-13460저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)