백준 17070번: 파이프 옮기기 1 (삼성 A형 기출 문제)

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

17070번: 파이프 옮기기 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를 실행시킬 것이라고 착각하여 오랜 시간을 낭비하였다.

 

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문을 정돈하였더니 시간이 약간 줄어들었다.

 

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 크기만큼의 계산만을 필요로 한다. 따라서 재귀를 이용한 풀이가 항상 능사는 아니라는 것을 명심해야 할 것이다.