[파이썬] 백준 1035 : 조각 움직이기 (골드1)

[파이썬] 백준 1035 : 조각 움직이기 (골드1)

1035번: 조각 움직이기

---

문제

---

풀이

0. 방향성 생각

• array 상태가 * . 두개만 존재  + 5*5 : 2^25 -> bitmask
• 조각이 상태를 int로 변환해준 후, bitmask로 연산을 줄여준다.
• list로 변환하지 않고 bitstream을 이용해주면 더 빨리 풀 수 있지만, TLE안나고 충분히 가능할거라 생각해서 현재 상태를 2차원 array로 바꿔서 연결요소 개수를 체크한다.

1. 입력

from collections import deque

start,p,count = 0,0,0
for _ in range(5):
    for s in input():
        if s == '*':
            start += 2**p
            count += 1
        p += 1
dire = [(1,0),(0,1),(-1,0),(0,-1)]

• power는 0부터 시작하나 24부터 시작하나 상관x. 어짜피 대칭형이라 상관없다.
• 현재 시작 array 형태를 int로 바꿔서 start에 넣는다.

2. list변환, BFS, update 함수 정의

def to_5x5(integer):
    string = bin(integer)[2:].rjust(25,'0')
    arr = [list(string[5*i:5*i+5]) for i in range(5)]
    return arr

def bfs(x,y):
    cnt = 1
    visited = [[False]*5 for _ in range(5)]
    visited[y][x] = True
    q = deque([(x,y)])
    while q:
        x,y = q.popleft()
        for dx,dy in dire:
            nx,ny = x+dx, y+dy
            if 0<=nx<5 and 0<=ny<5 and not visited[ny][nx] and x_list[ny][nx] == '1':
                q.append((nx,ny))
                visited[ny][nx] = True
                cnt += 1
    return cnt

def update(nxt):
    global visit,q
    if nx not in visit:
        visit.add(nx)
        q.append((nx,t+1))

• 현재 상태를 2차원 array로 바꿔주는 to_5x5
• 2차원 array에서 1을 만났을 때, 연결요소의 개수를 반환하는 BFS
• 비트연산을 해준 결과를 업데이트 할지 말지 결정해주는 update

3. 출력

if count == 1:
    print(0)
else:
    visit = set()
    visit.add(start)
    q = deque([(start,0)])
    while q:
        x,t = q.popleft()
        x_list = to_5x5(x)
        connect = False
        for i in range(5):
            for j in range(5):
                if x_list[i][j] == '1' and bfs(j,i) == count:
                    connect = True
                    break

        if connect:
            print(t)
            break

        for i in range(25):
            if (x>>i)&1:
                if i<20 and not x&(1<<(i+5)):
                    nx = x^(1<<i)
                    nx = nx^(1<<(i+5))
                    update(nx)

                if i>4 and not x&(1<<(i-5)):
                    nx = x^(1<<i)
                    nx = nx^(1<<(i-5))
                    update(nx)

                if i%5 != 0 and not x&(1<<(i-1)):
                    nx = x^(1<<i)
                    nx = nx^(1<<(i-1))
                    update(nx)

                if i%5 != 4 and not x&(1<<(i+1)):
                    nx = x^(1<<i)
                    nx = nx^(1<<(i+1))
                    update(nx)

• visit에 현재 상태를 출력한다. list로 하면 배열 크기가 320만이라 딕셔너리로 저장
• 현재 상태 x를 x_list로 바꿔서 BFS시킨다.
• BFS 반환값으로 연결유무를 파악한다.
• 연결되지 않았으면 bit연산을 통해 업데이트
• 2차원 array 형태로 생각하면 된다. (x>>i)&1로 조각 유무를 판단한다.
• 맨 윗줄은 위로 이동 못하므로 i <20 조건을 걸어준다. 또한 이동하려는 자리에 조각이 없어야한다.
• 상하우좌 순서대로 움직이는 if문을 줘서 업데이트 했다.

 

---

전체코드

from collections import deque

start,p,count = 0,0,0
for _ in range(5):
    for s in input():
        if s == '*':
            start += 2**p
            count += 1
        p += 1
dire = [(1,0),(0,1),(-1,0),(0,-1)]

def to_5x5(integer):
    string = bin(integer)[2:].rjust(25,'0')
    arr = [list(string[5*i:5*i+5]) for i in range(5)]
    return arr

def bfs(x,y):
    cnt = 1
    visited = [[False]*5 for _ in range(5)]
    visited[y][x] = True
    q = deque([(x,y)])
    while q:
        x,y = q.popleft()
        for dx,dy in dire:
            nx,ny = x+dx, y+dy
            if 0<=nx<5 and 0<=ny<5 and not visited[ny][nx] and x_list[ny][nx] == '1':
                q.append((nx,ny))
                visited[ny][nx] = True
                cnt += 1
    return cnt

def update(nxt):
    global visit,q
    if nx not in visit:
        visit.add(nx)
        q.append((nx,t+1))

if count == 1:
    print(0)
else:
    visit = set()
    visit.add(start)
    q = deque([(start,0)])
    while q:
        x,t = q.popleft()
        x_list = to_5x5(x)
        connect = False
        for i in range(5):
            for j in range(5):
                if x_list[i][j] == '1' and bfs(j,i) == count:
                    connect = True
                    break

        if connect:
            print(t)
            break

        for i in range(25):
            if (x>>i)&1:
                if i<20 and not x&(1<<(i+5)):
                    nx = x^(1<<i)
                    nx = nx^(1<<(i+5))
                    update(nx)

                if i>4 and not x&(1<<(i-5)):
                    nx = x^(1<<i)
                    nx = nx^(1<<(i-5))
                    update(nx)

                if i%5 != 0 and not x&(1<<(i-1)):
                    nx = x^(1<<i)
                    nx = nx^(1<<(i-1))
                    update(nx)

                if i%5 != 4 and not x&(1<<(i+1)):
                    nx = x^(1<<i)
                    nx = nx^(1<<(i+1))
                    update(nx)

 

코멘트

비트마스킹도 풀다보니까 많이 빨라진듯

풀고보니까 마지막 주변 조각 이동하는 논리랑 똑같이 개수세는 BFS 시켜도 됐네...