-
[동적 계획법] 등굣길코딩 테스트/프로그래머스 2023. 3. 31. 18:52
문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/42898
문제 풀이
- 좌표 (1,1)에서 출발 해서 (n,m)으로 도착하는 최단 경로의 개수를 구하는 문제(문제에서는 m,n 이라 했는데 평소 n,m으로 습관이 되어있어서 n,m으로 도착하는 걸로 설정해서 품)
- 최단 경로로 도착하는 거리가 아닌 경로의 개수를 구하는거임
- visited 그래프에서 웅덩이인 부분은 -1로 미리 표시 (못 건넘)
- 오른쪽과 아래로만 이동 하니 이전 경로로 빠질 경우 x
- 1,1 에서 출발하면 어느 경로든 1가지는 생기는 것이므로 visited[1][1]=1로 설정
- 방문한 적 없는 장소라면 visited[x][y]의 값을 넣어주고 , 큐에 다음 위치를 넣어 줌
- 방문한 적 있는 장소라면 visited[nx][ny] + visited[x][y] , 이미 그 위치 값은 큐에 담겨져 있으므로 또 넣을 필요x
소스 코드
from collections import deque dx = [0,1] dy = [1,0] def solution(m, n, puddles): # m은 가로, n이 세로 visited =[ [0]*(m+1) for i in range(n+1)] for ip in puddles: a,b=ip visited[b][a]=-1 q = deque() q.append([1,1]) visited[1][1]=1 while(q): x,y = q.popleft() for i in range(2): nx = x + dx[i] ny = y + dy[i] if(nx>n or ny>m): continue if(visited[nx][ny]==-1): continue if(visited[nx][ny]==0): visited[nx][ny]=visited[x][y] q.append([nx,ny]) else: visited[nx][ny]+=visited[x][y] return visited[n][m]%(int(1e9)+7) #1,000,000,007 로 나눴을 때의 나머지를 출력해야함 print(solution(4,3,[[2,2]]))
'코딩 테스트 > 프로그래머스' 카테고리의 다른 글
[우선순위 큐] 야근 지수 *** (0) 2023.04.03 [그리디] 단속 카메라 (0) 2023.04.03 [DFS/BFS] 단어 변환 (0) 2023.03.30 [DFS/BFS] 네트워크 (0) 2023.03.30 [연습 문제] 최고의 집합 (0) 2023.03.29