글 읽기 - visited를 빨간색만 한정지으면 안되는 이유?

crucialzint 1년 전 0

수정해서 정답을 맞추긴했지만

이전 코드에서 의문이 있어서 질문남깁니다.

저는 처음에는 빨간색이 방문한 곳만 고려를 해줬습니다.

이유는 어처퍼 빨간색이 들어가는지 여부만 판단하면 되는 부분이니

파란색이 방문하는 건 고려하지 않아도

빨간색이 움직이는 것만 확인하면 되겠다 싶었습니다.

그런데 아래와 같이 빨간색만 고려하는 케이스는

8%에서 틀렸다고 떴습니다.

굳이 파란색이 방문하는 것도 고려해야하는 이유가 뭔지

곰곰히 생각해도 아직 확실하게 알지 못해서

질문을 드립니다.

#백준 13459 구슬탈출
from heapq import heappop,heappush

dx=[0,0,1,-1]
dy=[1,-1,0,0]

N,M=map(int,input().split())
room=[[0]*M for _ in range(N)]
rx,ry=0,0
bx,by=0,0
r_visited=[[False]*M for _ in range(N)]
for i in range(N):
    tmp=input().rstrip()
    for j in range(M):
        if tmp[j]=='#':
            room[i][j]=1
        elif tmp[j]=='.':
            room[i][j]=0
        elif tmp[j]=='R':
            room[i][j]=0
            rx,ry=i,j
            r_visited[rx][ry]=True
        elif tmp[j]=='B':
            room[i][j]=0
            bx,by=i,j
        elif tmp[j]=='O':
            room[i][j]=-1

q=[]
heappush(q,[0,rx,ry,bx,by])
answer=0

def move(rx,ry,bx,by,d):
    #붉은거 이동
    nrx=rx
    nry=ry
    r_move=0
    while True:
        nrx+=dx[d]
        nry+=dy[d]
        if room[nrx][nry]==1:
            nrx-=dx[d]
            nry-=dy[d]
            break
        if room[nrx][nry]==-1:
            r_move+=1
            break
        r_move+=1
    #파란거 이동
    nbx=bx
    nby=by
    b_move=0
    while True:
        nbx+=dx[d]
        nby+=dy[d]
        if room[nbx][nby]==1:
            nbx-=dx[d]
            nby-=dy[d]
            break
        #파란색이 구멍에 들어가는 경우-->실패한 케이스이므로 다 -1를 return해준다
        if room[nbx][nby]==-1:
            return -1,-1,-1,-1
        b_move+=1

    if nrx==nbx and nry==nby:
        if r_move>b_move:
            nrx-=dx[d]
            nry-=dy[d]

        elif r_move<b_move:
            nbx-=dx[d]
            nby-=dy[d]

    return nrx,nry,nbx,nby
while q:
    cnt,rx,ry,bx,by=heappop(q)
    if cnt>10:
        continue

    if room[rx][ry]==-1 and room[bx][by]!=-1:
        answer=1
        break

    for d in range(4):
        nrx,nry,nbx,nby=move(rx,ry,bx,by,d)
        if nrx==-1:
            continue
        if r_visited[nrx][nry]==False:
            r_visited[nrx][nry]=True
            heappush(q,[cnt+1,nrx,nry,nbx,nby])

print(answer)

lcr7324 1년 전 0

반례 드립니다.

입력
10 10
##########
#........#
#.....B..#
#..#.R.#.#
#...#....#
#........#
#....#...#
#........#
#....O#..#
##########

출력
0

정답
1

비고
1) 아래쪽으로 기울이기
2) 오른쪽으로 기울이기
3) 아래쪽으로 기울이기
4) 왼쪽으로 기울이기
5) 아래쪽으로 기울이기
6) 오른쪽으로 기울이기

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

visited를 빨간색만 한정지으면 안되는 이유?

crucialzint 1년 전 0

lcr7324 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말