BOJ 17070 - 파이프 옮기기 1

BOJ 17070 - 파이프 옮기기 1

17070번: 파이프 옮기기 1Baekjoon Online Judge

파이프의 방향이 →, ↘, ↓ 세 가지가 있다고 합니다. 파이프를 놓을 때 본문 그림과 같이 놓을 수 있는 공간에 벽이 없어야 하는데, 이때 파이프를 연결하는 방법의 경우의 수를 모두 구하는 문제입니다.

주의할 점

1. → 모양은 이전 파이프의 방향이 →, ↘ 일 때만 사용할 수 있음

2. ↘ 모양은 이전 파이프의 방향이 어느 방향이든 상관없음

3. ↓ 모양은 이전 파이프의 방향이 ↘, ↓ 일 때만 사용할 수 있음

이 문제는 총 5번으로 나눠서 문제를 풀어보겠습니다.

1. 입력값 받기

2. 재귀 함수 1(만들기, 종료 구현)

3. 재귀 함수 2(→ 구현)

4. 재귀 함수 3(↘ 구현)

5. 재귀 함수 4(↓ 구현)

1. 입력값 받기

정답을 출력할 값 ans = 0을 추가로 만들어주면 됩니다.

n = int(input())
arr = list(list(map(int,input().split())) for _ in range(n))
ans = 0

2. 재귀 함수 1(만들기, 종료 구현)

재귀 함수 이름은 go라고 합니다. 우리는 파이프 끝이 (n-1, n-1)에 도착하면 파이프가 끝나는 것이니 우리는 파이프의 위치를 파이프 끝 위치를 기준으로 하겠습니다. 그러므로 시작 위치는 (0, 0)이 아닌 파이프 끝이 있는 (0, 1)에서 시작하는 것이죠.

그리고 이전 파이프의 방향에 따라 파이프를 놓을 수 있는 종류의 개수가 다르기 때문에 파이프의 방향을 나타내는 변수도 필요합니다.

이렇게 해서 go()함수에 필요한 파라미터는 현재 위치를 나타내는 x, y와 파이프의 종류를 나타내는 z를 넣어주면 됩니다. z의 값은 → = 1, ↘ = 2, ↓= 3으로 하겠습니다.

그러면 일단 main함수에서는 go(0, 1, 1)이 되겠습니다.

def go(x, y, z):
    blah blah


n = int(input())
arr = list(list(map(int,input().split())) for _ in range(n))
ans = 0
go(0, 1, 1)

먼저 종료 조건은 (n-1, n-1)에 도착하거나 (x, y)가 배열의 범위를 넘어서는 것입니다.

(n-1, n-1)에 도착하면 파이프를 연결하는 방법의 수가 1가지가 있다는 것이므로 global 키워드를 사용하고, ans += 1을 해주면 됩니다.

def go(x, y, z):
    global ans
    if x == n-1 and y == n-1:
        ans += 1
        return

n = int(input())
arr = list(list(map(int,input().split())) for _ in range(n))
ans = 0
go(0, 1, 1)

우리는 if문 3개를 이용하여 →, ↘, ↓를 만들 것입니다. 그래서 배열의 범위를 넘어서면 →, ↘, ↓ 파이프를 못 만들기 때문에 그냥 if문을 통과하면 됩니다.

3. 재귀 함수 2( → 구현)

z = 1일 때, 이전 파이프의 방향이 → 이므로 이번에 파이프를 놓을 수 있는 방향은 →, ↘입니다.

먼저 (x, y+1), (x+1, y+1), (x+1, y)가 범위 내에 있는지, 벽이 없는지 확인하는 함수를 만들어줍니다.

def check(x, y):
    if 0 <= x < n and 0 <= y < n and arr[x][y] == 0: return True
    else: return False

→는 (x, y) - (x, y+1)로 파이프를 이어주는 것이므로 check(x, y+1)이 True이면 파이프를 놓아도 된다는 뜻입니다.

↘는 (x, y) - (x + 1, y + 1)로 파이프를 이어주는 것이므로 check(x, y+1), check(x+1, y), check(x+1, y+1)이 전부 True이면 파이프를 이어주면 됩니다.

def check(x, y):
    if 0 <= x < n and 0 <= y < n and arr[x][y] == 0: return True
    else: return False

def go(x, y, z):
    global ans
    if x == n-1 and y == n-1:
        ans += 1
        return
    if z == 1:
        if check(x, y+1): go(x, y+1, 1)
        if check(x, y+1) and check(x+1, y) and check(x+1, y+1):
            go(x+1, y+1, 2)

n = int(input())
arr = list(list(map(int,input().split())) for _ in range(n))
ans = 0
go(0, 1, 1)

4. 재귀 함수 3( ↘ 구현)

이전 파이프의 방향이 ↘이면 다음 파이프의 방향은 →, ↘, ↓중 아무것이나 돼도 상관없습니다.

재귀 함수 2와 마찬가지로 check()함수를 이용하여 범위내에 있는 좌표인지, 벽이 없는지 확인해주면 됩니다.

def check(x, y):
    if 0 <= x < n and 0 <= y < n and arr[x][y] == 0: return True
    else: return False

def go(x, y, z):
    global ans
    if x == n-1 and y == n-1:
        ans += 1
        return
    if z == 1: # →
        if check(x, y+1): go(x, y+1, 1)
        if check(x, y+1) and check(x+1, y) and check(x+1, y+1):
            go(x+1, y+1, 2)
    elif z == 2: # ↘
        if check(x, y+1): go(x, y+1, 1)
        if check(x, y+1) and check(x+1, y) and check(x+1, y+1):
            go(x+1, y+1, 2)
        if check(x+1, y): go(x+1, y, 3)

n = int(input())
arr = list(list(map(int,input().split())) for _ in range(n))
ans = 0
go(0, 1, 1)

5. 재귀 함수 4( ↓ 구현)

이전 파이프의 방향이 ↓가 된다면 다음 파이프의 방향은 ↘, ↓만 가능합니다.

재귀 함수 2, 3과 같이 check() 함수를 이용하여 범위 내에 있는 좌표인지, 벽이 없는지 확인해주시면 됩니다.

def check(x, y):
    if 0 <= x < n and 0 <= y < n and arr[x][y] == 0: return True
    else: return False

def go(x, y, z):
    global ans
    if x == n-1 and y == n-1:
        ans += 1
        return
    if z == 1:
        if check(x, y+1): go(x, y+1, 1)
        if check(x, y+1) and check(x+1, y) and check(x+1, y+1):
            go(x+1, y+1, 2)
    elif z == 2:
        if check(x, y+1): go(x, y+1, 1)
        if check(x, y+1) and check(x+1, y) and check(x+1, y+1):
            go(x+1, y+1, 2)
        if check(x+1, y): go(x+1, y, 3)
    else:
        if check(x, y + 1) and check(x + 1, y) and check(x + 1, y + 1):
            go(x+1, y+1,2)
        if check(x+1, y): go(x+1, y, 3)

n = int(input())
arr = list(list(map(int,input().split())) for _ in range(n))
ans = 0
go(0, 1, 1)

이제 재귀 함수를 다 만들었으므로 ans를 출력해주면 됩니다.

def check(x, y):
    if 0 <= x < n and 0 <= y < n and arr[x][y] == 0: return True
    else: return False

def go(x, y, z):
    global ans
    if x == n-1 and y == n-1:
        ans += 1
        return
    if z == 1:
        if check(x, y+1): go(x, y+1, 1)
        if check(x, y+1) and check(x+1, y) and check(x+1, y+1):
            go(x+1, y+1, 2)
    elif z == 2:
        if check(x, y+1): go(x, y+1, 1)
        if check(x, y+1) and check(x+1, y) and check(x+1, y+1):
            go(x+1, y+1, 2)
        if check(x+1, y): go(x+1, y, 3)
    else:
        if check(x, y+1) and check(x+1, y) and check(x+1, y+1):
            go(x+1, y+1, 2)
        if check(x+1, y): go(x+1, y, 3)

n = int(input())
arr = list(list(map(int,input().split())) for _ in range(n))
ans = 0
go(0, 1, 1)
print(ans)