1일 1커밋 !

1일 1PS 80일차!

📚 문제

[Level 3] - 등굣길

💡 풀이 과정

  • 가장 기본적인 DP 문제이다.
    • 점화식을 찾아내기도 쉽고 조건을 처리하기도 쉽다.
    • 점화식은
      • dp[x][y] = dp[x-1][y] + dp[x][y-1] 이다.
      • 여기서 물웅덩이의 dp 값은 더해주지 않으면 되고 현재 위치가 물웅덩이라면 continue 하면 된다.
    • 여기서 가장 주의할 점은 dp 값이 할당되지 않은 곳과 물웅덩이를 구별지어야한다.
      • 만약 물웅덩이를 0 으로 둔다면 dp 를 더했을 때 0 이 더해져 따로 처리를 안해도 될 것 같지만
      • 실제로는 해당 물웅덩이를 할당되지 않은 일반 dp 값과 구분할 수 없어 물웅덩이에 값이 채워진다.
      • 따라서 여기에서는 물웅덩이를 -1 로 설정하였다.
      • dp 의 초기값을 -1 로 설정하고 물웅덩이를 0 으로 해도 된다.


  • 이제 순서대로 dp 를 처리하기만 하면 된다. dp 는 (1, 1) 에서 출발해 (4, 3) 까지 대각선으로 수행되어야한다.
  • bfs 를 실행할 때의 처리 과정과 동일하다 볼 수 있다.
  • 따라서 아래와 같이 bfs 를 진행해봤는데, 기존의 코드보다 훨씬 느리게 동작했다.

def bfs(N, M):
        dx = [1, 0]
        dy = [0, 1]

        queue = deque()
        queue.append((1,1))
        visited = [[False for _ in range(M + 1)] for _ in range(N + 1)]
        visited[1][1] = True

        while queue:
            x, y = queue.popleft()

            for i in range(2):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx > N or ny > M or visited[nx][ny] or dp[nx][ny] == -1:
                    continue

                sum = 0
                if dp[nx - 1][ny] != -1:
                    sum += dp[nx - 1][ny]
                if dp[nx][ny - 1] != -1:
                    sum += dp[nx][ny - 1]

                dp[nx][ny] = sum % 1000000007
                queue.append((nx, ny))
        return dp[N][M]

    
    return bfs(n, m)


  • 결국 그냥 for 문을 사용하게 되었는데,

””” (1,1) (2,1) (1,2) … (4,3) “””

  • 위와 같이 적용되어야한다.
    • 보면 총 합이 2 ~ (n + m) 인 것을 확인할 수 있다.
    • 또한 x <= n, y <= m 조건을 활용한다면 쉽게 해당 순서로 진행시킬 수 있다.


  • 이제 물웅덩이 조건을 추가해야한다.
  1. 물웅덩이가 온 곳 (dp = -1) 은 경로를 더하지 않는다.
  2. 물웅덩이인 곳은 계산을 하지 않는다.
  • 2번을 적용시키지 않으면 물웅덩이는 -1 에서 값이 업데이트되어 1번 상황이 일어나지 않는다.
  • 두 조건을 잘 적용시키면 dp[n][m] 이 정답이다.

📌포인트

  • dp
    • dp 에서는 점화식을 세워 값을 더해나간다.
    • dp 의 초기값을 모두 설정해주고 시작할 수도 있지만
    • 0 값인 행과 열을 추가해 첫번째 행과 열 초기값 처리 없이 바로 진행할 수 있다.
  • x, y
    • 2차원 배열에서는 문제에서 주어진 값의 x, y 를 잘 확인해서 입력하자.

💻 코드

# 문제 조건!
# 1000000007 로 나눈 나머지를 return

def solution(m, n, puddles):
    dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
    
    # 처음 시작 지점
    dp[1][1] = 1
    
    # puddles 는 -1 로 설정
    # 조건에서 x, y 위치 제대로 확인.
    for px, py in puddles:
        dp[py][px] = -1
    
    
    # 위에서부터 대각선으로 탐색해야한다.
    """
    (1,1)
    (2,1) (1,2)
    ...
    (4,3)
    
    for i in range(m + n):
        for j in range(1, i):
            여기서 좌표는 (j, i-j)
            이때 (1, 6), (2, 5) 등 i 는 n 보다 작아야하며, i - j 는 m 보다 작아야한다.
        
    (i, j) 를 sum(i,j) 순서대로 오름차순 정렬해도 될 것 같긴 하다.
    """
    
    # [1, 1] 은 이미 1로 지정해놓았으니 합이 3부터 해야한다. 
    for i in range(3, m + n + 1):
        for j in range(1, i):
        
            if j > n or i - j > m:
                continue

            if dp[j][i-j] == -1:
                continue
                
            # print(j, i-j)
            # 여기서 dp 처리 ..
            sum = 0
            if dp[j - 1][i - j] != -1:
                sum += dp[j - 1][i - j]
            if dp[j][i - j - 1] != -1:
                sum += dp[j][i - j - 1]
            
            dp[j][i-j] = sum % 1000000007
        
    return dp[n][m] % 1000000007

# 확인해야할 테스트케이스!

# dp 에서 외곽부분 처리..

업데이트:

댓글남기기

참고