[파이썬] 백준 1938 : 통나무 옮기기 (골드2)

[파이썬] 백준 1938 : 통나무 옮기기 (골드2)

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

---

풀이

방향성 생각

• 다차원 그래프 문제
• 통나무의 상태에 따라서 위치 이외에 state를 추가해서 V[state][y][x]로 배열 생성하기.
• 범위 조건 체크하기 -> 통나무 회전 시 주변 모든 좌표 탐색해야함

 

---

파이썬

from collections import deque

inside = lambda x,y : 0<=x<N and 0<=y<N
dires = [(1,0),(0,1),(-1,0),(0,-1)]

# move/rotate validation
def check(x,y,state,rotation):

    # 회전 시, 9칸 탐색
    if rotation:
        locs = [(j,i) for j in [x-1,x,x+1] for i in [y-1,y,y+1]]
    # 이동 시 이동위치 + state에 따라서 3칸 탐색
    else:
        if state:
            locs = [(x-1,y),(x,y),(x+1,y)]
        else:
            locs = [(x,y-1),(x,y),(x,y+1)]

    # 유효성 검사사
    if all(inside(xx,yy) and arr[yy][xx]==0 for xx,yy in locs):
        return True
    return False

# read input
N = int(input())
arr = [list(input()) for _ in range(N)]

# find location
starts,ends = [],[]
for y in range(N):
    for x in range(N):
        if arr[y][x] == 'B':
            starts.append((x,y))
            arr[y][x] = '0'
        elif arr[y][x] == 'E':
            ends.append((x,y))
            arr[y][x] = '0'

# convert map
for y in range(N):
    for x in range(N):
        arr[y][x] = 0 if arr[y][x] == '0' else 1

# init state(hor==1 ver==0)
ss = 0 if len(set(start[0] for start in starts)) == 1 else 1
es = 0 if len(set(end[0] for end in ends)) == 1 else 1
sx,sy = starts[1]
ex,ey = ends[1]

# bfs
V = [[[-1]*N for _ in range(N)] for _ in range(2)]
V[ss][sy][sx] = 0
Q = deque([(sx,sy,ss)])
while Q:
    x,y,s = Q.popleft()
    for dx,dy in dires:
        nx,ny = x+dx,y+dy
        # move
        if check(nx,ny,s,False) and V[s][ny][nx] == -1:
            Q.append((nx,ny,s))
            V[s][ny][nx] = V[s][y][x] + 1
        # rotate
        if check(x,y,s^1,True) and V[s^1][y][x] == -1:
            Q.append((x,y,s^1))
            V[s^1][y][x] = V[s][y][x] + 1

print(V[es][ey][ex] if V[es][ey][ex] != -1 else 0)

---

코멘트

• 하드코딩은 원트했는데....
• x y 인덱스 바꿔쓰는거 잘 찾기