17070. 파이프 옮기기 - DP + 비트마스킹. 파이썬

17070. 파이프 옮기기 1

사용한 알고리즘, 자료구조 및 기법

1. 다이나믹 프로그래밍
2. 비트마스킹
3. 델타를 이용한 2차원 배열 탐색

접근한 방식

1. 파이프의 '머리'는 우, 하, 대각으로 움직일 수 있다.
    1) 파이프의 '꼬리'는 신경 쓸 필요가 없는 변수다. 머리가 갈 수 있는 곳은 꼬리도 무조건 갈 수 있다.
    2) 단, 기둥이 있는 곳에는 파이프를 놓을 수 없다.

2. visited[row][column]에는 '이 지점에 방문할 수 있는 방법의 수'를 저장한다.
    1) 파이프가 '어디 방향에서 오는지'에 따라서 방법의 수가 달라진다.
    2) visited[row][column]은 세 개의 정수를 가진 리스트로 구성한다.[0, 0, 0]
    3) 0번 idx에는 '가로에서 접근한 방법의 수',
    4) 1번 idx에는 '세로에서 접근한 방법의 수',
    5) 2번 idx에는 '대각선에서 접근한 방법의 수'를 저장할 것이다.

3. 2차원 배열을 행 우선 순회한다.
    대각선 이동의 필요조건 == 가로 이동의 충분조건 & 세로 이동의 충분조건.
    가로 이동이 가능했는지, 세로 이동이 가능했는지를 기록해두면
    대각선 이동 가능 여부 조회 시 시간을 아낄 수 있다.

    1) 현재 지점의 좌표를 y, x라고 하자.
    2) 현재 지점의 가로, 세로 지점의 정보를 차례대로 읽는다.
    3) index overflow 발생시 아무 연산도 하지 않는다.
    4) index가 정상일 때, house_map (지도) 에 벽이 있다면 접근 불가능하다는 정보를 기록한다.
    5) 접근이 가능하다면
    6) 현재 지점에 가로 상태로 도착한 경우의 수 + 현재 지점에 대각선 상태로 도착한 경우의 수를
    7) 다음 지점의 '가로' 상태로 도착할 수 있다고 저장한다.
    8) 세로 또한 상동.

    9) 대각선으로 갈 수 있는 경우를 확인한다.
    10) 만약 가로로 도착할 수 없거나 세로로 도착할 수 없으면
    11) 문제 조건상 대각선 지점은 고려할 필요 없으므로
    12) 연산을 생략한다.

    13) 가로, 세로 지점 모두 비어있다면
    14) 대각선 자리도 비어있는지 확인 후
    15) 이전 지점까지 올 수 있는 모든 경우의 수를
    16) '대각선 형태로 도착 가능하다'고 표시.

4. 출력

어려웠던 점

3차원 visited 배열을 구상하기 난해했다. 이 아이디어를 떠올리고 나니 그렇게 어렵지 않게 풀렸다. BFS로 풀다가 구현이 잘 되지 않았는데, 덕분에 이전까지 시도하지 않았던 방식의 풀이를 구현할 수 있었다.

 

 

실행시간, 메모리, 언어

1) 일반적인 비트마스킹 풀이

72ms, 29200kb, Python3

 

2) 방의 형태도 비트로 입력받는 풀이

72ms, 29200kb, Python3

 

1) 일반적인 비트마스킹 풀이

import sys
input = sys.stdin.readline

# 1. 입력

N = int(input()) # 방의 크기
house_map = [list(map(int, input().split())) for _ in range(N)] # 방의 모습. True: wall 이 있다.

# 2. 선언

dp_house = [[[0, 0, 0] for _ in range(N)] for _ in range(N)] # visited배열. 3차원 배열. 각각 1) 가로 2) 세로 3) 대각선.
dp_house[0][1][0] = 1 # 초기값 선언. 첫 열 두번째 행에 머리가 있고, 가로방향이므로.

# 2-1 델타 배열 선언
dx = (1, 0, 1) # 우, 하, 대각
dy = (0, 1, 1) # 우, 하, 대각

# 3. 연산
for y in range(N): # 행 우선으로 모든 좌표들을 순회한다.
    for x in range(N):

        is_possible = 7 # bin(7)[2:] == 111. 자릿수는 각각 대각선, 세로, 가능 여부를 나타냄.

        for k in range(3): # 0일때 가로, 1일때 세로, 2일때 대각선 체크.

            if k == 2 and is_possible & 3 != 3: # 대각선 지점을 살펴보는데
                break # 가로 혹은 세로 접근이 불가능하면 더 이상 연산을 하지 않음.

            nx = x + dx[k] # 이동 가능성이 있는 x 좌표.
            ny = y + dy[k] # 이동 가능성이 있는 y 좌표

            if nx >= N or ny >= N: # 만약 인덱스가 초과된다면
                is_possible &= ~(1 << k) # 해당 지점을 '진행 불가능' 으로 선언.
                continue # 다음 방향을 확인.

            # 만약 벽이 있다면(house_map[ny][nx] == True)
            is_possible &= ~(house_map[ny][nx] << k) # is_possible 에 '불가능' 이라고 기록.

            if is_possible & (1 << k): # 갈 수 있고
                if not k: # k == 0이면 == 가로 이동이면
                    dp_house[ny][nx][0] += dp_house[y][x][0] + dp_house[y][x][2] # 이전 좌표에서 가로, 대각에서 온 경우의 수를 추가.

                elif k == 1:  # k == 1이면 == 세로 이동이면
                    dp_house[ny][nx][1] += dp_house[y][x][1] + dp_house[y][x][2] # 이전 좌표 중 세로, 대각에서 온 경우의 수를 추가.

                else: # k == 2, 대각선 이동이면
                    dp_house[ny][nx][2] += sum(dp_house[y][x]) # 모든 경우의 수를 추가.

# 4. 출력
# N, N 좌표에
# 1) 가로 방향 2) 세로 방향 3) 대각선 방향
# 에서 도착하는 모든 경우의 수의 총합.
print(sum(dp_house[N-1][N-1]))

 

2) 방의 상태도 비트 형태로 입력받는 풀이.

from sys import stdin

# 1. 입력

N = int(stdin.readline())  # 방의 크기
house_bit = [int(stdin.readline().strip().replace(' ', '')[::-1], 2) for _ in range(N)]  # 방의 모습. 1: wall 이 있다.

# 2. 선언

dp_house = [[[0, 0, 0] for _ in range(N)] for _ in range(N)]  # visited 배열. 3차원 배열. 각각 1) 가로 2) 세로 3) 대각선.
dp_house[0][1][0] = 1  # 초기값 선언. 첫 열 두번째 행에 머리가 있고, 가로방향이므로.

# 2-1 델타 배열 선언
dx = (1, 0, 1)  # 우, 하, 대각
dy = (0, 1, 1)  # 우, 하, 대각

# 3. 연산
for y in range(N):  # 행 우선으로 모든 좌표들을 순회한다.
    for x in range(N):

        is_possible = 7  # bin(7)[2:] == 111. 자릿수는 각각 대각선, 세로, 가로 가능 여부를 나타냄.

        for direction in range(3):  # 0일때 가로, 1일때 세로, 2일때 대각선 체크.

            if direction == 2 and is_possible & 3 != 3:  # 대각선 지점을 살펴보는데
                break  # 가로 혹은 세로 접근이 불가능하면 더 이상 연산을 하지 않음.

            nx = x + dx[direction]  # 이동 가능성이 있는 x 좌표.
            ny = y + dy[direction]  # 이동 가능성이 있는 y 좌표

            if nx >= N or ny >= N:  # 만약 인덱스가 초과된다면
                is_possible &= ~(1 << direction)  # 해당 지점을 '진행 불가능' 으로 선언.
                continue  # 다음 방향을 확인.

            # 만약 벽이 있다면(house_map[ny][nx] == True)
            is_possible &= ~(bool(house_bit[ny] & (1 << nx)) << direction)  # is_possible 에 '불가능' 이라고 기록.

            if is_possible & (1 << direction):  # 갈 수 있고
                if not direction:  # direction == 0이면 == 가로 이동이면
                    dp_house[ny][nx][0] += dp_house[y][x][0] + dp_house[y][x][2]    # 이전 좌표에서 가로, 대각에서 온 경우의 수를 추가.

                elif direction == 1:  # direction == 1이면 == 세로 이동이면
                    dp_house[ny][nx][1] += dp_house[y][x][1] + dp_house[y][x][2]    # 이전 좌표 중 세로, 대각에서 온 경우의 수를 추가.

                else:  # direction == 2, 대각선 이동이면
                    dp_house[ny][nx][2] += sum(dp_house[y][x])  # 모든 경우의 수를 추가.

# 4. 출력
# N, N 좌표에
# 1) 가로 방향 2) 세로 방향 3) 대각선 방향
# 에서 도착하는 모든 경우의 수의 총합.
print(sum(dp_house[N-1][N-1]))