🏫

등굣길

레벨

LV.3

날짜

Oct 12, 2023

링크

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

🔎 문제

school.programmers.co.kr

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

🧩 구현과정 및 코드

개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.

사용할 데이터 구조와 풀이 방향성

적용할 알고리즘 혹은 메서드

수영

구현

[1, 1]에서 아래, 오른쪽으로 가는 길은 모두 1, 중간이 문제!

[x, y] 기준에서 x-1 + y-1 = [x, y]

코드

정은

구현

JS로는 안 풀린다길래, 파이썬으로 풀었습니다.

dp[i][j] = (i,j)로 갈 수 있는 경로의 수

2차원 배열을 0으로 초기화 한 후, 첫 위치를 1로 지정하고 dp를 진행합니다.

현재 위치로 올 수 있는 경우는 왼쪽과 위쪽에서 온 경우 밖에 없으므로, 두 경로의 수를 더해주면 됩니다.

처음 이동은 둘 중 한 경우만 존재하므로, 하나만 더해줍니다.

m,n까지 진행합니다.

코드

종혁

구현

1,000,000,007로 나눈 값을 리턴하라고 했기 때문에 수가 엄청 커질거라고 예상했고, 상하좌우가 아닌 우하 만 가능했기 때문에 bfs 방식보다는 다른 방식으로 풀어야겠다고 생각함

dp[i][j] - dp[i-1][j] + dp[i][j-1] / 웅덩이가 있을 경우 0

코드

재웅

구현

DP를 이용한 최단경로 풀이

i번 이동해서 갈 수 있는 블럭 dp[i]

dp[i+1]은 dp[i]블럭 좌표 중 맵 안에 있고, 방문하지 않았으며, puddle이 아닌 경우 이동할 수 있음

j번 째 블록에서 목적지에 최초 도달했다면, 그 때 목적지에 도달한 가짓수를 반환

그 이전까지는 중복을 고려하지 않아도 됨 -> set?

코드

✏️ 후기

문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.

👧🏻

수영

dp 문제 풀이 익숙해지면 푸는 방식은 비슷한 것 같기도 하다.

x, y 좌표 반대여서 헷갈렸다

👧🏻

정은

처음에는 dp라고 해도 bfs 밖에 생각나지 않았다.. 당연 시간초과

이제 dp에 대해 살짝 감이 오는 것 같기도..?

👦🏻

종혁

js로 풀기는 조금 어려워서 문제 풀이법만 잡고 넘어가도 괜찮을것 같다

👦🏻

재웅

될 것 같은 코드가 효율성에서 실패했을 때 방향을 틀어 생각하기가 쉽지 않은 것 같다..

Set에는 배열의 중복처리가 이루어지지 않는다 !


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;
}


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


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];
}


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;
}