등굣길

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

문제요약:

고등학교 수학문제에서 좌표에서 목표지점까지 가는데 그중 웅덩이가 있는케이스는 못지나가는, 딱 그 문제 입니다.

 

소요시간:

15분

난이도3

 

코딩:

def solution(m, n, puddles):
	arr = [[0] * m for _ in range(n)]
	puddles = set(map(tuple,puddles))
	for x in range(m):
		if (x+1,1) not in puddles:
			arr[0][x] = 1
		else:
			break
	for y in range(n):
		if (1,y+1) not in puddles:
			arr[y][0] = 1
		else:
			break
	for y in range(1,n):
		for x in range(1,m):
			if (x+1,y+1) not in puddles:
				arr[y][x] = arr[y-1][x] +arr[y][x-1]
	return arr[-1][-1]%1000000007

사실 매우 반가웠습니다. 고등학교때 자주나오는 쉬운 문제였는데 , 방법 역시 똑같이 구현해주었습니다. 

웅덩이는 갈수있는방법이 0 으로 고정시키고, 왼쪽과 아래를 더하면(두방법의 합이 이곳을 갈수있는 방법) 그지점인것으로 구현해주었습니다. 

다만 시간이 생각보다 더 걸린 이유는 첫번째로 set함수는 안에 문자열, 숫자 튜플 만 가능한 점을 몰랐어서 해맨점, 그리고 x 또는 y값이 0 인 점을 시작할때 1로 깔아주었는데,(갈 수 있는 방법이 1가지밖에 없음) 만약 중간에 물웅덩이가 있다면, 그 뒤는 가지 못하는 케이스를 생각하지 못해 시간을 소비하였습니다.

결국 저렇게 길게 1을 추가시켰는데, 패딩을 통해 위 아래로 0을 깐다면 다음과같이 훨씬 깔금하게 코딩할 수 있습니다.

 

def solution(m, n, puddles):
	arr = [[0] * (m+1) for _ in range(n+1)]
	puddles = set(map(tuple,puddles))
	arr[0][1] = 1
	for y in range(1,n+1):
		for x in range(1,m+1):
			if (x,y) not in puddles:
				arr[y][x] = arr[y-1][x] +arr[y][x-1]
	return arr[-1][-1]%1000000007