파이썬으로 풀어보는 백준 17070번: 파이프 옮기기 1

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

2020.1.18

내 풀이 1:

N = int(input())
result = 0
 
def move(y,x,style):
    global result
    if y == N-1 and x == N-1:
        result += 1
        return
 
    if style == 1:
        if x == N-1:
            return
 
        if table[y][x+1] == 0:
            move(y,x+1,1)
            if table[y+1][x+1] == 0 and table[y+1][x] == 0:
                move(y+1,x+1,2)
            return
 
    elif style == 2:
        if x == N-1:
            for check in range(y, N):
                if table[check][x] == 1:
                    return
            result += 1
            return
 
 
        elif y == N-1:
            for check in range(x, N):
                if table[y][check] == 1:
                    return
            result += 1
            return
 
        if table[y][x+1] == 0:
            move(y,x+1,1)
            if table[y+1][x+1] == 0 and table[y+1][x] == 0:
                move(y+1,x+1,2)
                move(y+1,x,3)
                return
            elif table[y+1][x] == 0:
                move(y+1, x, 3)
                return
 
        elif table[y+1][x] == 0:
            move(y+1,x,3)
            return
 
    elif style == 3:
        if y == N-1:
            return
        if table[y+1][x] == 0:
            move(y+1,x,3)
            if table[y+1][x+1] == 0 and table[y][x+1] == 0:
                move(y+1,x+1,2)
        return
 
 
table = []
for i in range(N):
    table_mini = list(map(int, input().split()))
    table.append(table_mini)
 
move(0,1,1)
print(result)

932ms, pypy
style 1을 오른쪽, style 2를 대각선, style 3을 아래쪽 방향으로 구분하였다. 이번 코딩에서 발생한 문제로는 첫 번째로 벽에 도착했을 때 처리하는 방식을 if문으로 해결하다 보니 이동하는 모든 경우에 있어서 벽인가를 체크하여 시간이 지연된다. for문 안에 if문이 많을 경우 시간이 기하급수적으로 오래 걸리기 때문에 가능하면 for문 밖에서 해결하거나 아예 다른 방식으로 접근하는 습관을 들여야 한다. 또한 if문에서 첫 조건만을 통과하고 그 이후로 모든 조건을 통과하지 못했을 때의 상황은 return과 같이 해석을 해야 했는데 그다음 elif를 실행시킬 것이라고 착각하여 오랜 시간을 낭비하였다.

내 풀이 2:

N = int(input())
result = 0
 
def move(y,x,style):
    global result
    if y == N-1 and x == N-1:
        result += 1
        return
 
    if style == 1:
        if x == N-1:
            return
 
        if table[y][x+1] == 0:
            move(y,x+1,1)
            if table[y+1][x+1] == 0 and table[y+1][x] == 0:
                move(y+1,x+1,2)
            return
 
    elif style == 2:
        if x == N-1:
            for check in range(y, N):
                if table[check][x] == 1:
                    return
            result += 1
            return
 
 
        elif y == N-1:
            for check in range(x, N):
                if table[y][check] == 1:
                    return
            result += 1
            return
 
        if table[y + 1][x + 1] == 0 and table[y + 1][x] == 0 and table[y][x + 1] == 0:
            move(y, x + 1, 1)
            move(y + 1, x + 1, 2)
            move(y + 1, x, 3)
            return
 
        if table[y][x+1] == 0:
            move(y, x + 1, 1)
 
        if table[y+1][x] == 0:
            move(y + 1, x, 3)
 
 
    elif style == 3:
        if y == N-1:
            return
        if table[y+1][x] == 0:
            move(y+1,x,3)
            if table[y+1][x+1] == 0 and table[y][x+1] == 0:
                move(y+1,x+1,2)
        return
 
 
table = []
for i in range(N):
    table_mini = list(map(int, input().split()))
    table.append(table_mini)
 
move(0,1,1)
print(result)

844ms, pypy
style 2에서 if문을 정돈하였더니 시간이 약간 줄어들었다.

내 풀이 3:

N = int(input())
result = 0
 
def move(y,x,style):
    global result
    if y == N-1 and x == N-1:
        result += 1
        return
 
    if style == 1:
        if table[y][x+1] == 0:
            move(y,x+1,1)
            if table[y+1][x+1] == 0 and table[y+1][x] == 0:
                move(y+1,x+1,2)
            return
 
    elif style == 2:
        if table[y + 1][x + 1] == 0 and table[y + 1][x] == 0 and table[y][x + 1] == 0:
            move(y, x + 1, 1)
            move(y + 1, x + 1, 2)
            move(y + 1, x, 3)
            return
 
        if table[y][x+1] == 0:
            move(y, x + 1, 1)
 
        if table[y+1][x] == 0:
            move(y + 1, x, 3)
 
 
    elif style == 3:
        if table[y+1][x] == 0:
            move(y+1,x,3)
            if table[y+1][x+1] == 0 and table[y][x+1] == 0:
                move(y+1,x+1,2)
        return
 
 
table = []
for i in range(N):
    table_mini = list(map(int, input().split()))
    table_mini.append(1)
    table.append(table_mini)
table.append([1] * (N + 1))
move(0,1,1)
print(result)

1000ms, pypy
벽을 만났을 때 처리해주기 위한 별도의 if문들을 모두 없애고 바깥쪽에 1을 둘러싸서 알고리즘으로 해결하였다. 이렇게 하면 if문의 개수가 줄어들기 때문에 시간도 줄어들 것이라 기대했는데 오히려 늘어났다. 이 말은 즉, 벽에 도달한 경우에 바로 result를 1 올려주고 return 하는 대신 계속해서 재귀를 돌리게 되어 시간이 오래 걸렸다는 것을 말한다. 시간을 줄이기 위해서는 몇 개의 조건문을 추가하여 불필요한 재귀가 발생하는 것을 줄이는 게 오히려 시간 단축에 더 도움이 된다는 얘기이다.

jeonsewallse님 풀이:

# DP를 이용해서 풀이
N = int(input())
 
field = [input().split() + ['1'] for _ in range(N)]
field.append(['1'] * (N + 1))
wall = '1'
road = '0'
# 도착했을 때 방향을 고려하여 경우의 수 분리
arrive_right = [[0]*N for _ in range(N)]
arrive_down = [[0]*N for _ in range(N)]
arrive_cross = [[0]*N for _ in range(N)]
 
# 첫 줄의 경우의 수 갱신
for c in range(1, N):
    if field[0][c] == '0':
        arrive_right[0][c] = 1
    else:
        break
 
# 행 마다 경우의 수 갱신
for r in range(1, N):
    for c in range(1, N):
        if field[r][c] == road and field[r-1][c] == road and field[r][c-1] == road:
            # 대각선으로 도착할 수 있는 경우의 수 갱신
            arrive_cross[r][c] = arrive_right[r-1][c-1] + arrive_down[r-1][c-1] + arrive_cross[r-1][c-1]
        if field[r][c] == road:
            # 가로로 도착한 경우, 세로로 도착할 수 있는 경우의 수 갱신
            arrive_right[r][c] = arrive_right[r][c-1] + arrive_cross[r][c-1]
            arrive_down[r][c] = arrive_down[r-1][c] + arrive_cross[r-1][c]
 
ans = arrive_right[N-1][N-1] + arrive_down[N-1][N-1] + arrive_cross[N-1][N-1]
 
print(ans)

64ms, python3
Dynamic Programing(동적 계획법)을 이용한 풀이. 기존의 내 코딩과 이 코딩의 차이점은 어릴 때 많이 풀어보았던 길찾기 문제를 떠올리면 된다. 내 코드는 모든 경로를 직접 탐색해서 총 100가지가 나온다면 100개의 경로 그 이상을 탐색해야 하지만 길 찾기 문제를 몇 번의 덧셈으로 풀곤 하였는데 이 코드가 그러한 방식과 동일하다고 생각하면 된다. 이 풀이는 N이 20이라 할지라도 20*20 이라는 field 크기만큼의 계산만을 필요로 한다. 따라서 재귀를 이용한 풀이가 항상 능사는 아니라는 것을 명심해야 할 것이다.

2020.11.27

내 풀이 1:

# 2020.11.27
# 16:07 ~ 16:23

N = int(input())
field = []
for _ in range(N):
    row = list(map(int, input().split()))
    field.append(row)

stack = [(0, 1, 0)]
ry = (0, 1, 1)
rx = (1, 1, 0)


def check(y, x, dirc):
    for dy in range(ry[dirc] + 1):
        for dx in range(rx[dirc] + 1):
            ny = y + dy
            nx = x + dx
            if field[ny][nx]:
                return False
    return True


answer = 0
while stack:
    y, x, last_dirc = stack.pop()
    for dirc in range(3):
        if abs(dirc - last_dirc) <= 1:
            ny = y + ry[dirc]
            nx = x + rx[dirc]
            if 0 <= ny < N and 0 <= nx < N:
                if check(y, x, dirc):
                    if ny == N - 1 and nx == N - 1:
                        answer += 1
                    else:
                        stack.append((ny, nx, dirc))

print(answer)

시간초과, python3
최대 16*16이고 각 지점에서 3가지 방법이 존재한다고 할 때, 못해도 330가지 이상의 방법이 존재한다. 때문에 당연하게도 DFS를 이용한 방법은 사용해서는 안됐는데 구현 과정이 너무 명확하다보니 스택을 이용한 DFS방법을 이용하였고 시간초과가 났다. 이동 방법이 단 3가지 밖에 없기 때문에 좌표와 방향을 이용한 DP로 풀어야 한다.

내 풀이 2:

# 2020.11.27
# 16:07 ~ 16:37

N = int(input())
field = []
for _ in range(N):
    row = list(map(int, input().split()))
    field.append(row)

DP = [[[0, 0, 0] for _ in range(N)] for _ in range(N)]
DP[0][1][0] = 1
for i in range(N):
    for j in range(1, N):
        if not field[i][j]:
            if j > 0:
                DP[i][j][0] += DP[i][j-1][0] + DP[i][j-1][1]
                if i > 0:
                    if not field[i-1][j] and not field[i][j-1]:
                        DP[i][j][1] += sum(DP[i-1][j-1])
            if i > 0:
                DP[i][j][2] += DP[i-1][j][1] + DP[i-1][j][2]

answer = sum(DP[N-1][N-1])
print(answer)

76ms, python3
DP를 이용할 때, 분기를 최대한 깔끔하게 짜고 싶었는데, y와 x좌표에 분기를 걸어주다보니 생각보다는 지저분하게 코드가 작성된 것 같아서 아쉽다. 반복문이 돌면서 분기를 계속 지나야하기 때문에 비효율적이라는 느낌도 지울수가 없었다. 때문에 차라리 첫 줄만 따로 처리해주고 i>0, j>0 에 대해서만 코드를 진행시키는게 더 좋았을 것 같다. 해당 변경 내용은 위의 jeonsewallse님의 풀이를 참고하면 될 것 같다.