[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)

좋은 웹페이지 즐겨찾기