🔎 문제
🧩 구현과정 및 코드
개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.
사용할 데이터 구조와 풀이 방향성
적용할 알고리즘 혹은 메서드
수영
구현
- dp
- [1, 1]에서 아래, 오른쪽으로 가는 길은 모두 1, 중간이 문제!
- [x, y] 기준에서 x-1 + y-1 = [x, y]
코드
function solution(m, n, puddles) { // 편의상 n+1, m+1로 table 초기화 const table = Array.from(Array(n + 1), () => new Array(m + 1).fill(0)); for(let i = 1; i < n; i++) { for(let j = 1; j < m; j++) { if(i === 1 && j === 1) { // 맨 왼쪽 맨 위쪽 줄 1로 변경 table[1][1] = 1; continue; } if(isPuddle(j, i, puddles)) continue; table[i][j] = (table[i-1][j] + table[i][j-1]) % 1000000007; } } return table[n][m]; } const isPuddle = (x, y, puddles) => { for(const puddle of puddles) { if(puddle[0] === y && puddle[1] === x) return true; } return false; }
정은
구현
- JS로는 안 풀린다길래, 파이썬으로 풀었습니다.
dp[i][j] = (i,j)로 갈 수 있는 경로의 수
- 2차원 배열을 0으로 초기화 한 후, 첫 위치를 1로 지정하고 dp를 진행합니다.
- 현재 위치로 올 수 있는 경우는 왼쪽과 위쪽에서 온 경우 밖에 없으므로, 두 경로의 수를 더해주면 됩니다.
- 처음 이동은 둘 중 한 경우만 존재하므로, 하나만 더해줍니다.
- m,n까지 진행합니다.
코드
def is_puddle(x,y,puddles): #웅덩이인지 확인하는 함수 for px,py in puddles: if x == px and y == py: return True return False def solution(m, n, puddles): dp = [[0]*(n+1)]*(m+1) #두번째 칸의 계산을 수월하게 하기 위해 (m+1)*(n*1) 배열 선언 후 0으로 초기화 dp[1][1]=1 for i in range(1,m+1): for j in range(1,n+1): if i==1 and j==1: #처음은 초기화 해줬으므로 넘어감(처리 안해주면 값이 다시 0이 됨) continue if is_puddle(i,j,puddles): dp[i][j]=0 #웅덩이로부터 다음칸을 이동할 수 없으므로, 0 할당 continue dp[i][j] = dp[i-1][j] + dp[i][j-1] #위와 왼쪽으로 부터 오는 경우밖에 없어서 두 경로를 더한다 return dp[m][n]% 1000000007
종혁
구현
- 1,000,000,007로 나눈 값을 리턴하라고 했기 때문에 수가 엄청 커질거라고 예상했고, 상하좌우가 아닌 우하 만 가능했기 때문에 bfs 방식보다는 다른 방식으로 풀어야겠다고 생각함
- dp[i][j] - dp[i-1][j] + dp[i][j-1] / 웅덩이가 있을 경우 0
코드
function solution(m, n, puddles) { const dp = Array.from({ length: n }, () => Array(m).fill(0)); dp[0][0] = 1; for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { if (i === 0 && j === 0) continue; if (puddles.some(([x, y]) => x === j + 1 && y === i + 1)) { dp[i][j] = 0; } else { dp[i][j] = ((i > 0 ? dp[i - 1][j] : 0) + (j > 0 ? dp[i][j - 1] : 0)) % 1000000007; } } } return dp[n - 1][m - 1]; }
재웅
구현
- DP를 이용한 최단경로 풀이
- i번 이동해서 갈 수 있는 블럭 dp[i]
- dp[i+1]은 dp[i]블럭 좌표 중 맵 안에 있고, 방문하지 않았으며, puddle이 아닌 경우 이동할 수 있음
- j번 째 블록에서 목적지에 최초 도달했다면, 그 때 목적지에 도달한 가짓수를 반환
- 그 이전까지는 중복을 고려하지 않아도 됨 -> set?
코드
function solution(m, n, puddles) { let dp = Array.from(Array(n + 1), () => new Array(m + 1).fill(0)); dp[1][1] = 1; const puddleSet = new Set(puddles.map(puddle => `[${puddle[0]},${puddle[1]}]`)); for(let i=1; i<=n; i++) { for(let j=1; j<=m; j++) { if(i === 1 && j === 1) continue; if(puddleSet.has(`[${j},${i}]`)) { dp[i][j] = 0; } else { dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007; } } } return dp[n][m]%1000000007; }
✏️ 후기
문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.
수영
- dp 문제 풀이 익숙해지면 푸는 방식은 비슷한 것 같기도 하다.
- x, y 좌표 반대여서 헷갈렸다
정은
- 처음에는 dp라고 해도 bfs 밖에 생각나지 않았다.. 당연 시간초과
- 이제 dp에 대해 살짝 감이 오는 것 같기도..?
종혁
- js로 풀기는 조금 어려워서 문제 풀이법만 잡고 넘어가도 괜찮을것 같다
재웅
- 될 것 같은 코드가 효율성에서 실패했을 때 방향을 틀어 생각하기가 쉽지 않은 것 같다..
- Set에는 배열의 중복처리가 이루어지지 않는다 !