[백준 25173] 용감한 아리의 동굴 대탈출

https://www.acmicpc.net/problem/25173

25173번: 용감한 아리의 동굴 대탈출

그야말로 '빡구현'문제.

하나 하나 제대로 구현하면 되지만

구현해야할 것이 워낙 많은지라

체감 난이도가 높은 편.

 

제가 뻘짓했던 것으로 주의사항을 적어보자면

 

1. 아리,보스는 

체력이 0'이하'가 되면 패배.

즉, 0이거나 0보다 작을 때를 봐준다.

 

2. 문제에서는 '전투중'이라고 애매하기 표현했지만

어떤 상황이든 체력이 0이 되면 패배.

아리같은 경우엔, 방향을 돌리다가 체력이 -1씩 깍이는데

사방이 막혀있다면

빙빙 돌다가 패배할 수 있다.

 

이 문제에서 어렵게 느낀 부분은

석순을 시계방향으로 회전하면서 찾는 것.

시계방향 탐색을 어떻게 구현할까 고민을 많이 했었죠.

 

또 헷갈리는 부분이

아리가 움직이는 방향.

위의 주의할 점 2에 적었지만

아리가 회전할수록 체력이 -1깍입니다.

만약 4바퀴 다 회전했는데 제자리여도

-4로 깍입니다.

문제를 잘못 이해하면

'가만히 있으니깐 체력은 유지가 되겠네'

라고 잘못 생각하실 수 있으니 주의하시면 좋겠습니다.

#백준 25173번 용감한 아리의 동굴 대탈출
from heapq import heappop,heappush

N,M=map(int,input().split())
room=[]
dx=[-1,0,1,0]
dy=[0,1,0,-1]

sx,sy=-1,-1
bx,by=-1,-1
for x in range(N):
    tmp=list(map(int,input().split()))
    for y in range(M):
        if tmp[y]==2:
            tmp[y]=0
            sx,sy=x,y
        elif tmp[y]==3:
            tmp[y]=0
            bx,by=x,y
    room.append(tmp)

A,D,B,E=map(int,input().split())
s_life=A
s_attack=D
B_life=B
B_attack=E
if bx-1==sx and by==sy:
    B_direct=0
elif bx==sx and by+1==sy:
    B_direct=1
elif bx+1==sx and by==sy:
    B_direct=2
elif bx==sx and by-1==sy:
    B_direct=3
s_direct=B_direct

def check():
    for i in range(N):
        if 0 in visited[i]:
            return True
    return False


while True:

    #1. 아리 공격 시작
    B_life-=s_attack
    if B_life<=0:
        print("VICTORY!")
        break

    #2. 아리 이동 시작
    nsx=sx
    nsy=sy

    tsx=sx
    tsy=sy


    cnt=0
    flag=False
    while cnt<4:
        nsx=tsx+dx[s_direct]
        nsy=tsy+dy[s_direct]

        if 0<=nsx<N and 0<=nsy<M and room[nsx][nsy]!=1 and not [nsx,nsy]==[bx,by]:
            flag=True
            break
        s_direct=(s_direct+1)%4
        cnt+=1
    #아리의 이동여부를 flag로 처리해줌
    if flag:
        sx,sy=nsx,nsy
    s_life-=cnt
    if s_life<=0:
        print("CAVELIFE...")
        break



    #3. 보스 공격
    # 석순을 찾는다
    visited=[[0]*M for _ in range(N)]
    nbx=bx
    nby=by
    cnt=0
    next_max=0
    max_move=1
    b_d=B_direct
    mon=False
    visited[nbx][nby]=1
    while check():
        nbx+=dx[b_d]
        nby+=dy[b_d]

        cnt+=1
        if cnt>=max_move:
            cnt=0
            next_max+=1
            b_d=(b_d+1)%4

        if next_max==2:
            max_move+=1
            next_max=0

        if 0<=nbx<N and 0<=nby<M:
            visited[nbx][nby]=1
            if room[nbx][nby]==1:
                mon=True
                break

    #괴물을 발견했다면 괴물을 보고 공격시작
    if mon==True:
        mx=nbx
        my=nby
        q=[]
        m_visited=[[False]*M for _ in range(N)]
        m_visited[mx][my]=True
        heappush(q,[0,mx,my])
        m_move=1e9
        while q:
            cnt,x,y=heappop(q)
            if cnt>=B_attack:
                continue

            if x==sx and y==sy:
                m_move=min(m_move,cnt)
                continue

            for d in range(4):
                nx=x+dx[d]
                ny=y+dy[d]

                if nx<0 or nx>=N or ny<0 or ny>=M:
                    continue
                if [nx,ny]==[bx,by]:
                    continue
                if m_visited[nx][ny]==True:
                    continue
                if room[nx][ny]==0:
                    q.append([cnt+1,nx,ny])
                    m_visited[nx][ny]=True


        if m_move!=1e9:
            m_life=B_attack-m_move

            s_life-=m_life

        if s_life<=0:
            print("CAVELIFE...")
            break
    #4 보스 이동
    #아리가 이동해야 이동한다.
    if flag==True:
        bx,by=tsx,tsy
        B_direct=s_direct

 

문제 85%에서 틀려서 낑낑댈 때,

정답 맞추신 분께 메일까지 드려서

반례를 찾을 수 있었습니다.

정성스럽게 답변주신 분. 감사합니다.

https://www.acmicpc.net/board/view/99746#comment-158948

글 읽기 - 85%에서 틀렸다고 뜨네요...고수분들의 도움이 필요합니다