[백준 1938번] 통나무 옮기기(파이썬)

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

1938번: 통나무 옮기기

이 문제를 들었던 생각들.

'통나무를 어떻게 옮기지???'

3개를 한번에 옮겨?

3개를 deque에 받고 옮겨?

 

이렇게 생각하니 문제가 전혀 안풀렸습니다.

그러다가 질문하기 글을 봤는데

의외로 간단한 해결책이 있었습니다.

 

'중앙점을 중심으로 옮긴다'

중앙점 x,y를 기준으로

가로,세로인지 확인해주고

그걸 옮긴다는 개념이었습니다.

그렇게 머릿속에 박고 다시 시작하니

문제가 체감상 쉬워졌습니다.

 

구현한 함수는

1. 이동이 가능한지

2. 이동시 어떤 좌표인지

 

두 가지입니다.

 

이동이 가능한지 여부를 확인할 때

통나무의 모든 것을 다 볼필요가 없는 케이스가 있습니다.

이 경우처럼, 가로 뉘워있는 통나무가

왼쪽으로 움직인다고 가정할 때,

1.y-2>=0인지

2. room[x][y-2]가 벽인지 아닌지(1인지 아닌지)

2를 보면 점 하나만 체크해주면 됩니다.

"통나무가 이동했는데

y-1,y도 봐야하는 거 아닌가요??"

이건 굳이 그럴 필요가 없습니다.

이미 이동하기 전에

y-1 y 에 통나무가 있었잖아요?

그말은 

'해당 좌표들은 벽이 아닙니다'

라는 의미.

물론 안전하게 한다면 다 비교할 수 있지만

이 케이스에서는 저렇게 특정 한 케이스만 고려하면

시간을 좀 더 줄일 수 있습니다.

#백준 1938 통나무 옮기기
from collections import deque

dx=[0,0,1,-1]
dy=[1,-1,0,0]
moving=['U','D','L','R','T']
N=int(input())
room=[[0]*N for _ in range(N)]
tmp=[input().rstrip()for _ in range(N)]

visited=[[[1e9]*N for _ in range(N)] for _ in range(3)]
fcenter_x=0
fcenter_y=0
f_state=-1
ecenter_x=0
ecenter_y=0
e_state=-1


for x in range(N):
    for y in range(N):
        if tmp[x][y]=='B':
            room[x][y]=0
            if f_state==-1:
                fcenter_x=x
                fcenter_y=y
                f_state=0
            #가로
            elif f_state==0 and y==fcenter_y+1:
                fcenter_x=x
                fcenter_y=y
                f_state=1
            #새로
            elif f_state==0 and x==fcenter_x+1:
                fcenter_x=x
                fcenter_y=y
                f_state=2
        elif tmp[x][y]=='E':
            room[x][y]=0
            if e_state==-1:
                ecenter_x=x
                ecenter_y=y
                e_state=0
            #가로
            elif e_state==0 and y==ecenter_y+1:
                ecenter_x=x
                ecenter_y=y
                e_state=1
            #세로
            elif e_state==0 and x==ecenter_x+1:
                ecenter_x=x
                ecenter_y=y
                e_state=2
        else:
            room[x][y]=int(tmp[x][y])


answer=1e9

def move(x,y,state,m):
    if m=='U':
        return x-1,y,state
    elif m=='D':
        return x+1,y,state
    elif m=='L':
        return x,y-1,state
    elif m=='R':
        return x,y+1,state
    elif m=='T':
        if state==1:
            state=2
        else:
            state=1
        return x,y,state

#움직이는게 가능한지 각 동작마다 판단하는 함수
def go_ok(x,y,m,state):

    flag=True
    if m=='U':
        #가로
        if state==1:
            if x-1<0:
                return False
            for j in range(y-1,y+2):
                if room[x-1][j]==1:
                    flag=False
        #세로
        elif state==2:
            if x-2<0:
                return False
            if room[x-2][y]==1:
                flag=False

    elif m=='D':
        # 가로
        if state == 1:
            if x +1>=N:
                return False
            for j in range(y - 1, y + 2):
                if room[x +1][j] == 1:
                    flag=False

        # 세로
        elif state == 2:
            if x +2 >= N:
                return False
            if room[x+2][y]==1:
                flag=False

    elif m=='L':
        # 가로
        if state == 1:
            if y-2<0:
                return False
            if room[x][y-2]==1:
                flag=False
        # 세로
        elif state == 2:
            if y-1< 0:
                return False
            for i in range(x-1 , x+2):
                if room[i][y-1] == 1:
                    flag=False

    elif m=='R':
        # 가로
        if state == 1:
            if y + 2 >= N:
                return False
            if room[x][y+2]==1:
                flag=False

        # 세로
        elif state == 2:
            if y + 1 >=N:
                return False
            for i in range(x - 1, x + 2):
                if room[i][y + 1] == 1:

                    flag=False

    elif m=='T':
        if x-1<0 or x+1>=N:
            return False
        if y-1<0 or y+1>=N:
            return False

        for i in range(x-1,x+2):
            for j in range(y-1,y+2):
                if room[i][j]==1:
                    flag=False
    return flag
q=deque()

q.append([fcenter_x,fcenter_y,f_state])
visited[f_state][fcenter_x][fcenter_y]=0
while q:
    x,y,state=q.popleft()
    if x==ecenter_x and y==ecenter_y and state==e_state:
        answer=min(answer,visited[state][x][y])
        break

    for d in range(5):
        go=moving[d]
        #1. 이동가능여부 확인
        if go_ok(x,y,go,state):
            #2 이동후 간 거리가 이미 간 곳인지 아닌지 확인
            nx,ny,n_state=move(x,y,state,go)
            if visited[n_state][nx][ny]!=1e9:continue
            visited[n_state][nx][ny]=visited[state][x][y]+1
            q.append([nx,ny,n_state])
if answer==1e9:
    answer=0
print(answer)

 

문제를 볼 때

'어려운데...'싶다면

쉽게 최대한 풀어쓸 수 있음을 배웠던 좋은 문제입니다.