Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 |
Tags
- 코딩테스트
- 구현
- 가상메모리 관리
- 프로그래머스
- 다익스트라
- MYSQL
- 힙
- DP
- 딕셔너리
- level3
- 백준
- 그리디
- 재귀
- level1
- 다이나믹 프로그래밍
- N과M
- 브루트포스
- dict
- programmers
- BFS
- 파이썬
- 운영체제
- BOJ
- python
- 스택
- level0
- level2
- 가상메모리
- dfs
- 수학
Archives
- Today
- Total
동캄의 코딩도장
프로그래머스 level3 [등굣길] 파이썬 본문
https://programmers.co.kr/learn/courses/30/lessons/42898
코딩테스트 연습 - 등굣길
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m =
programmers.co.kr
#프로그래머스 등굣길
def solution(m, n, puddles):
answer = 0
field=[[0]*(m) for _ in range(n)]
field[0][0]=1
for puddle in puddles:
y=puddle[0]
x=puddle[1]
field[x-1][y-1]=-1
i=0
while i<m:
if field[0][i]==-1:
break
else:
field[0][i]=1
i+=1
i=0
while i<n:
if field[i][0]==-1:
break
else:
field[i][0]=1
i+=1
if n==1:
if field[0][m-1]==1:
answer=1
return answer
else:
answer=0
return answer
elif m==1:
if field[n-1][0]==1:
answer=1
return answer
else:
answer=0
return answer
else:
for i in range(1,n):
for j in range(1,m):
if field[i][j]!=-1:
if field[i-1][j]==-1 and field[i][j-1]==-1:
pass
elif field[i-1][j]==-1:
field[i][j]=field[i][j-1]%1000000007
elif field[i][j-1]==-1:
field[i][j]=field[i-1][j]%1000000007
else:
field[i][j]=(field[i-1][j]+field[i][j-1])%1000000007
answer=field[n-1][m-1]
return answer
우리가 수학시간에 풀었던 최단경로 개수 찾기 문제이다.
문제가 정말 뭐 같다... 행과 열을 반대로 두고 풀어야한다. (m이 열, n이 행이다. puddle에서도 마찬가지)
'코테 > 프로그래머스' 카테고리의 다른 글
프로그래머스 level3 [단속카메라] 파이썬 (0) | 2022.01.11 |
---|---|
프로그래머스 level4 [도둑질] 파이썬 (0) | 2022.01.10 |
프로그래머스 level2 [n^2 배열 자르기] 파이썬 (0) | 2021.12.24 |
프로그래머스 level2 [수식 최대화] 파이썬 (0) | 2021.12.23 |
프로그래머스 level2 [메뉴 리뉴얼] 파이썬 (0) | 2021.12.23 |