삼성 #17070 파이프 옮기기1

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

17070번: 파이프 옮기기 1

 

 

 

 

오답 풀이 1

import sys

# N = int(sys.stdin.readline())
# board = [ list(sys.stdin.readline().rstrip()) for _ in range(N)]

stdin = open('input.txt', 'r')
N = int(stdin.readline())
board = [list(map(int, stdin.readline().split())) for _ in range(N)]
res = 0

s_right, s_down, s_diag = 'right', 'down', 'diag'
d_right = (1, 0, s_right)
d_down = (0, 1, s_down)
d_diag = (1, 1, s_diag)


def _get_available_dirs(pipe_dir):
    # check available directions from current pipe state
    if pipe_dir == s_right: # if pipe is horizontal
        return [d_right, d_diag] # can go right and diagonal

    elif pipe_dir == s_diag: # if pipe is diagonal
        return [d_right, d_diag, d_down] # right, down, diagonal

    else: # if pip is vertical
        return [d_down, d_diag] # can go down and diagonal


def _is_boundary(x, y):
    # check is point outside of board
    if x >= N or y >= N:
        return True
    else:
        return False


def _is_avail(x, y, s):
    if s == s_right: # if right cell is wall
        if board[y][x + 1] == 1:
            return False
    elif s == s_diag: # if around cell is wall
        if board[y][x + 1] == 1 or board[y + 1][x + 1] ==1 or board[y + 1][x] == 1:
            return False
    else:
        if board[y + 1][x] == 1: # if down cell is wall
            return False

    return True # everything is okay


def gogo(pipe):
    global res
    # Note that pipe is defined with start-point ~ end-point.

    ap, bp, d = pipe  # start-point, end-point, pipe-state

    if bp[0] == N - 1 and bp[1] == N - 1: # if pipe reaches to the destination
        res += 1
        return

    avail_dirs = _get_available_dirs(d)

    for direction in avail_dirs:
        dx, dy, d_state = direction
        bpx, bpy = bp # end-point

        nx, ny = bpx + dx, bpy + dy # next-point defined by available direction

        if _is_boundary(nx, ny):
            continue

        if _is_avail(bpx, bpy, d_state):
            npipe = [bp, (nx, ny), d_state]
            gogo(npipe)


_pipe = [(0, 0), (1, 0), s_right]
gogo(_pipe)
print(res)

도저히 어디서 틀린지 모르겠다..

 

 

오답풀이 2

import sys
stdin = open('input.txt', 'r')
N = int(stdin.readline())
board = [list(map(int, stdin.readline().split())) for _ in range(N)]

res = 0


# shape 0 ->right, 1 -> down, 2-> diag
def dfs(x, y, shape):
    global res

    if x == N - 1 and y == N - 1:
        res += 1
        return

    if shape == 0 or shape == 2:  # Move right
        if x + 1 < N:  # inside the board
            if board[y][x + 1] != 1:
                dfs(x + 1, y, shape=0)

    if shape == 1 or shape == 2:  # Move down
        if y + 1 < N:
            if board[y + 1][x] != 1:
                dfs(x, y + 1, shape=1)

    if shape == 0 or shape == 1 or shape == 2:
        if x + 1 < N and y + 1 < N:
            if board[y + 1][x] == 0 and board[y + 1][x + 1] == 0 and board[y][x + 1] == 0:
                dfs(x + 1, y + 1, shape=2)


dfs(1, 0, 0)
print(res)

DP 동적할당법으로 풀었으니 시간초과당했다..

 

오답풀이 3

import sys
stdin = open('input.txt', 'r')
N = int(stdin.readline())

board =  [ [0]*(N+2) ]
for _ in range(N):
    board.append([0]+list(map(int, stdin.readline().split()))+[0])
board.append([0]*(N+2))


res = [ [[0,0,0] for _ in range(N+2)] for _ in range(N+2)]
res[1][2][2] = 1

for y in range(1,N+1):
    for x in range(3,N+1):
        if board[y][x] ==0:
            #  horizontal이
            res[y][x][0] = res[y-1][x][0] + res[y-1][x][1]
            res[y][x][2] = res[y][x-1][2] + res[y][x-1][1]

            if board[y-1][x] ==0 and board[y][x-1] ==0:
                res[y][x][1] = sum(res[y-1][x-1])

        # print(np.array(res).sum(axis=2)[1:-1, 1:-1])
print(sum(res[N][N]))

 

DP 에는 recursive(재귀)  그리고 iteration(반복) 둘다 사용가능하다!! 

대개 반복문은 오랜 시간이 걸리지만 일부 경우에선 Tablulation 방법을 통해 빠르게 처리할수있다.