[BOJ] 1938 통나무 옮기기 - Python

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

1938번: 통나무 옮기기

 

 

상당히 까다로운(?) 구현 문제였다.

구현 문제라 설명은 주석으로 대체

from collections import deque
N = int(input())
arr = [[0]*N for _ in range(N)]
visit = set() # 방문한 부분을 tuple을 저장한 set 자료구조에 저장
dx = [-1,1,0,0]
dy = [0,0,-1,1]

start = []
end = []
for i in range(N):
    line = input()
    for j in range(N):
        arr[i][j] = line[j]
        if line[j] == "B":
            start.append((i,j))
        if line[j] == "E":
            end.append((i,j))
q = deque() # BFS로 탐색
# visit set에는 (x1,y1,x2,y2,x3,y3) 형태로 저장
visit.add((start[0][0], start[0][1],start[1][0], start[1][1],start[2][0], start[2][1]))
start.append(0) # append를 해주는 이유는 좌표 3개에다가 카운트 까지 q에 넣으려고
q.append(start)
check = False
res = 0
while q:
    now = q.popleft()
    # 각 좌표 따로 부름
    ax, ay = now[0][0], now[0][1]
    bx, by = now[1][0], now[1][1]
    cx, cy = now[2][0], now[2][1]
    cnt = now[3] # 카운트도 봄
    # end에 도착했으면 끝
    if (ax, ay) == end[0] and (bx, by) == end[1] and (cx, cy) == end[2]:
        check = True
        res = cnt
        break
    # 먼저 상하좌우 네 방향으로 통나무를 옮김.
    for i in range(4):
        axx = ax + dx[i]
        ayy = ay + dy[i]
        bxx = bx + dx[i]
        byy = by + dy[i]
        cxx = cx + dx[i]
        cyy = cy + dy[i]

		# 옮겨진 좌표가 격자를 벗어나지 않으면
        if 0<=axx<N and 0<=ayy<N and 0<=bxx<N and 0<=byy<N and 0<=cxx<N and 0<=cyy<N:
        	# visit 안에 없으면
            if (axx,ayy,bxx,byy,cxx,cyy) not in visit:
            	# 옮기려는 곳에 통나무가 없으면
                if arr[axx][ayy] != "1" and arr[bxx][byy] != "1" and arr[cxx][cyy] != "1":
                	# visit에 추가해주고
                    visit.add((axx,ayy,bxx,byy,cxx,cyy))
                    # q에 cnt+1 해서 append
                    q.append([(axx,ayy),(bxx,byy),(cxx,cyy),cnt+1])
    # 현재 통나무가 세로일 때 가로로 회전
    if bx-1 == ax:
    	# 돌린 가로가 격자를 벗어나지 않으면
        if 0<=ay-1<N and 0<=ay+1<N and 0<=by-1<N and 0<=by+1<N and 0<=cy-1<N and 0<=cy+1<N:
        	# 세로일 때 양 옆 6칸에 통나무가 있으면 안됨
            if arr[ax][ay-1] != "1" and arr[ax][ay+1] != "1" and arr[bx][by-1] != "1" and arr[bx][by+1] != "1" and arr[cx][cy-1] != "1" and arr[cx][cy+1] != "1":
                axx = ax +1
                ayy = ay -1
                bxx = bx
                byy = by
                cxx = cx -1
                cyy = cy +1
                # 위 이동하는 로직과 같음
                if 0<=axx<N and 0<=ayy<N and 0<=bxx<N and 0<=byy<N and 0<=cxx<N and 0<=cyy<N:
                    if (axx,ayy,bxx,byy,cxx,cyy) not in visit:
                        if arr[axx][ayy] != "1" and arr[bxx][byy] != "1" and arr[cxx][cyy] != "1":
                            visit.add((axx, ayy, bxx, byy, cxx, cyy))
                            q.append([(axx,ayy),(bxx,byy),(cxx,cyy),cnt+1])
    # 현재 통나무가 가로일 때 세로로 회전
    else:
        if 0<=ax-1<N and 0<=ax+1<N and 0<=bx-1<N and 0<=bx+1<N and 0<=cx-1<N and 0<=cx+1<N:
            if arr[ax-1][ay] != "1" and arr[ax+1][ay] != "1" and arr[bx-1][by] != "1" and arr[bx+1][by] != "1" and arr[cx-1][cy] != "1" and arr[cx+1][cy] != "1" :
                axx = ax - 1
                ayy = ay + 1
                bxx = bx
                byy = by
                cxx = cx + 1
                cyy = cy - 1
                if 0 <= axx < N and 0 <= ayy < N and 0 <= bxx < N and 0 <= byy < N and 0 <= cxx < N and 0 <= cyy < N:
                    if (axx,ayy,bxx,byy,cxx,cyy) not in visit:
                        if arr[axx][ayy] != "1" and arr[bxx][byy] != "1" and arr[cxx][cyy] != "1":
                            visit.add((axx, ayy, bxx, byy, cxx, cyy))
                            q.append([(axx, ayy), (bxx, byy), (cxx, cyy), cnt + 1])

print(res)