🕊 Link

Lv3. 등굣길 Javascript
https://programmers.co.kr/learn/courses/30/lessons/42898

🧑🏻‍💻 Code(javascript)

function solution(m, n, pds) {
  const arr = Array.from(Array(n), () => Array(m).fill(1))
  pds.forEach(pd => {
    const [x, y] = pd
    arr[x - 1][y - 1] = 0
  })
  for (let i = 1; i < n; i++) {
    for (let j = 1; j < m; j++) {
      if (arr[i][j] !== 0) {
        arr[i][j] = arr[i - 1][j] + arr[i][j - 1]
      }
    }
  }
  return arr[n - 1][m - 1] % 1000000007
}

💡 Solution

최종 코드(결과 확인 불가)

// Test Code
const m = 4
const n = 3
const pds1 = [[2, 2]]
const pds2 = [[1, 3]]
console.log(solution(m, n, pds1)); // 결과값: 4 | 기대값 : 4 (O)
console.log(solution(m, n, pds2)); // 결과값: 7 | 기대값 : 7 (O)

function solution(m, n, pds) {
  // 1로 채워진 n x m 배열 생성
  const arr = Array.from(Array(n), () => Array(m).fill(1))

  // 웅덩이 배열을 돌며 arr에 웅덩이를 0으로 체크
  // 웅덩이는 1부터 시작하지만 우리의 arr는 0부터 시작하므로 -1 연산
  pds.forEach(pd => {
    const [x, y] = pd
    arr[x - 1][y - 1] = 0
  })

  // i=0, j=0 인 웅덩이가 있으면 웅덩이 다음으로는 모두 접근이 불가능한 길임.
  // 각각의 경우 돌면서 flag(1)로 채워주는데, 
  // 만약 중간에 웅덩이(0)을 발견하면 flag를 0으로 전환하여
  // 그 뒤의 경우는 모두 flag(0)으로 채움
  let flag = 1
  for (let j = 0; j < m; j++) {
    if (arr[0][j] == 0) flag = 0
    arr[0][j] = flag
  }
  flag = 1
  for (let i = 0; i < n; i++) {
    if (arr[i][0] == 0) flag = 0
    arr[i][0] = flag
  }
  
  // i=1~, j=1~ 의 경우 각 자리의 윗쪽칸, 왼쪽칸을 더한 값을 할당
  for (let i = 1; i < n; i++) {
    for (let j = 1; j < m; j++) {
      if (arr[i][j] !== 0) {
        arr[i][j] = arr[i - 1][j] + arr[i][j - 1]
      }
    }
  }
  
  // 마지막 칸을 확인
  return arr[n - 1][m - 1] % 1000000007
}

1차 코드(오류)

// Test Code
const m = 4
const n = 3
const pds1 = [[2, 2]]
const pds2 = [[1, 3]]
console.log(solution(m, n, pds1)); // 결과값: 4 | 기대값 : 4 (O)
console.log(solution(m, n, pds2)); // 결과값: 8 | 기대값 : 7 (X)


// solution
function solution(m, n, pds) {
  const arr = Array.from(Array(n), () => Array(m).fill(1))
  pds.forEach(pd => {
    const [x, y] = pd
    arr[x - 1][y - 1] = 0
  })
  
  // i=0, j=0 인 웅덩이가 있으면 웅덩이 다음으로는 모두 접근이 불가능한 길임  
  for (let i = 1; i < n; i++) {
    for (let j = 1; j < m; j++) {
      if (arr[i][j] !== 0) {
        arr[i][j] = arr[i - 1][j] + arr[i][j - 1]
      }
    }
  }
  return arr[n - 1][m - 1] % 1000000007
}

👨🏻‍💻💭 Self Feedback

• javascript로 채점이 불가능한 문제지만, 최단거리로 접근하여 풀이함.
• n과 m, i와 j 순서에 주의.

• 2021.08.13 - 최초 작성

댓글 환영 질문 환영
by.protect-me