[백준 14947번] 상자배달

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

14947번: 상자 배달

처음에는 중간점을 x,y로 두고

1x1 1x3나누는 건 생각했지만

1x3을 가로,세로로 구현하는 부분이 제대로 되지 않았습니다.

제대로 구현하기 위해서

state==0-->1x1

state==1-->1x3(가로)

state==2-->1x3(세로)

 

이렇게 나눠서 상자가 움직일때를 구현했습니다.

#백준 14947번 상자배달
from collections import deque

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

N,M=map(int,input().split())
room=[[0]*M for _ in range(N)]
sx,sy=-1,-1
ex,ey=-1,-1
for i in range(N):
    tmp=input().rstrip()
    tmp=list(tmp)
    for j in range(M):
        if tmp[j]=='2':
            room[i][j]=1
            sx,sy=i,j
        elif tmp[j]=='3':
            room[i][j]=1
            ex,ey=i,j
        elif tmp[j]=='1':
            room[i][j]=1

visited=[[[False]*3 for _ in range(M)] for _ in range(N)]
visited[sx][sy][0]=True
q=deque()
q.append([sx,sy,0,0])
answer=1e9

def check(state,x,y):
    if [x,y]==[ex,ey]:
        return True

    elif state==1:
        if [x,y+1]==[ex,ey] or [x,y-1]==[ex,ey]:
            return True

    elif state==2:
        if [x+1,y]==[ex,ey] or [x-1,y]==[ex,ey]:
            return True

    return False
def valid_board(state,x,y):
    if room[x][y]==1:
        return True

    elif state==1:
        if room[x][y-1]==1 and room[x][y+1]==1:
            return True

    elif state==2:
        if room[x+1][y]==1 and room[x-1][y]==1:
            return True

    return False

while q:
    x,y,state,cnt=q.popleft()
    if check(state,x,y):
        answer=cnt
        break
    #state==0-->1x1
    #state==1-->1x3(가로)
    #state==2-->1x3(세로)
    #각 상태에서 상하좌우로 굴릴때 어떻게 되는지 구현한다
    if state==0:
        #상
        if x-3>=0 and valid_board(2,x-2,y):
            if visited[x-2][y][2]==False:
                visited[x-2][y][2]=True
                q.append([x-2,y,2,cnt+1])
        #하
        if x+3<N and valid_board(2,x+2,y):
            if visited[x+2][y][2]==False:
                visited[x+2][y][2]=True
                q.append([x+2,y,2,cnt+1])
        #좌
        if y-3>=0 and valid_board(1,x,y-2):
            if visited[x][y-2][1]==False:
                visited[x][y-2][1]=True
                q.append([x,y-2,1,cnt+1])
        #우
        if y+3<M and valid_board(1,x,y+2):
            if visited[x][y+2][1]==False:
                visited[x][y + 2][1]=True
                q.append([x,y+2,1,cnt+1])
    elif state==1:
        #상
        if x-1>=0 and valid_board(1,x-1,y):
            if visited[x-1][y][1]==False:
                visited[x-1][y][1]=True
                q.append([x-1,y,1,cnt+1])
        #하
        if x+1<N and valid_board(1,x+1,y):
            if visited[x+1][y][1]==False:
                visited[x+1][y][1]=True
                q.append([x+1,y,1,cnt+1])
        #좌
        if y-2>=0 and valid_board(0,x,y-2):
            if visited[x][y-2][0]==False:
                visited[x][y-2][0]=True
                q.append([x,y-2,0,cnt+1])
        #우
        if y+2<M and valid_board(0,x,y+2):
            if visited[x][y+2][0]==False:
                visited[x][y+2][0]=True
                q.append([x,y+2,0,cnt+1])
    elif state==2:
        #상
        if x-2>=0 and valid_board(0,x-2,y):
            if visited[x-2][y][0]==False:
                visited[x-2][y][0]=True
                q.append([x-2,y,0,cnt+1])
        #하
        if x+2<N and valid_board(0,x+2,y):
            if visited[x+2][y][0]==False:
                visited[x+2][y][0]=True
                q.append([x+2,y,0,cnt+1])
        #좌
        if y-1>=0 and valid_board(2,x,y-1):
            if visited[x][y-1][2]==False:
                visited[x][y-1][2]=True
                q.append([x,y-1,2,cnt+1])
        #우
        if y+1<M and valid_board(2,x,y+1):
            if visited[x][y+1][2]==False:
                visited[x][y+1][2]=True
                q.append([x,y+1,2,cnt+1])

if answer==1e9:
    answer=-2
print(answer)

 

이 문제를 풀 때

좌표 돌리는 부분에서

입력 하나 잘못해서 오랜 시간동안 해매었습니다.

이런 구현문제는 입력 하나 하나 할 때마다

제대로 내가 구현한 게 맞는지

일일이 다 체크를 해야겠네요.

(1시간동안 샷건치고 입에 거품물다가

발견하고 개허탈....)