파이프의 방향이 →, ↘, ↓ 세 가지가 있다고 합니다. 파이프를 놓을 때 본문 그림과 같이 놓을 수 있는 공간에 벽이 없어야 하는데, 이때 파이프를 연결하는 방법의 경우의 수를 모두 구하는 문제입니다.
주의할 점
→ 모양은 이전 파이프의 방향이 →, ↘ 일 때만 사용할 수 있음
↘ 모양은 이전 파이프의 방향이 어느 방향이든 상관없음
↓ 모양은 이전 파이프의 방향이 ↘, ↓ 일 때만 사용할 수 있음
이 문제는 총 5번으로 나눠서 문제를 풀어보겠습니다.
입력값 받기
재귀 함수 1(만들기, 종료 구현)
재귀 함수 2(→ 구현)
재귀 함수 3(↘ 구현)
재귀 함수 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)
