https://www.acmicpc.net/problem/1577
난이도: G5
문제
준이가 살고 있는 도시는 신기하게 생겼다. 이 도시는 격자형태로 생겼고, 직사각형이다. 도시의 가로 크기는 N이고, 세로 크기는 M이다. 또, 세준이의 집은 (0, 0)에 있고, 세준이의 학교는 (N, M)에 있다.
따라서, 아래 그림과 같이 생겼다.
세준이는 집에서 학교로 가는 길의 경우의 수가 총 몇 개가 있는지 궁금해지기 시작했다.
세준이는 항상 최단거리로만 가기 때문에, 항상 도로를 정확하게 N + M개 거친다. 하지만, 최근 들어 이 도시의 도로가 부실공사 의혹으로 공사중인 곳이 있다. 도로가 공사 중일 때는, 이 도로를 지날 수 없다.
(0, 0)에서 (N, M)까지 가는 서로 다른 경로의 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자연수이다. 셋째 줄부터 K개 줄에는 공사중인 도로의 정보가 a b c d와 같이 주어진다. a와 c는 0보다 크거나 같고, N보다 작거나 같은 자연수이고, b와 d는 0보다 크거나 같고, M보다 작거나 같은 자연수이다. 그리고, (a, b)와 (c, d)의 거리는 항상 1이다.
출력
첫째 줄에 (0, 0)에서 (N, M)까지 가는 경우의 수를 출력한다. 이 값은 0보다 크거나 같고, 263-1보다 작거나 같은 자연수이다.
예제 입력
6 6
2
0 0 0 1
6 6 5 6예제 출력
252풀이
DP를 이용한 문제이다.
DFS나 BFS로는 중복방문이 복잡해서 DP로 푸는게 쉽다.
특정 위치 i,j로 올 수 있는 경우의 수는 i-1,j에서 오는방법 i,j-1에서 오는 방법 2가지가 있다.
반복문으로 모든 지역을 돌면서, i-1,j ->i,j 도로가 안막히고, i-1>=0인 경우와 i,j-1->i,j 도로가 안막히고 j-1>=0인 경우를 합쳐
dp[i][j]를 채워주면 된다.
※ 주의사항
제출코드
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
def check(a,b,c,d):
if (a,b,c,d) in r:
return False
return True
K=int(input())
r=set()
for _ in range(K):
a,b,c,d=map(int,input().split())
r.add((a,b,c,d))
r.add((c,d,a,b))
dp=[[0]*(M+1) for _ in range(N+1)]
dp[0][0]=1
for i in range(N+1):
for j in range(M+1):
if i==0 and j==0:
continue
if i>0 and check(i-1,j,i,j):
dp[i][j]+=dp[i-1][j]
if j>0 and check(i,j-1,i,j):
dp[i][j]+=dp[i][j-1]
print(dp[N][M])
틀린 부분이 있거나 인용한 부분에 대해 문제가 있을 시
댓글로 알려주시면 감사하겠습니다.