[동적계획법] 프로그래머스 level 2 조이스틱 (Python 파이썬)

절대적 시간이 부족해서 점심시간에 PC방에서 코딩테스트 준비하기 시작..ㅎ__ㅎ 지나고 보면 다 추억이 되겠지 

 

💡문제 링크

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

프로그래머스

 

💡문제 분석 요약

경로의 개수를 구하는 문제(최단경로 아님 주의)

집(1, 1)에서 학교(m, n)까지 가는 길, 지도는 m x n 크기의 격자모양(m이 열 n이 행)이동의 조건은 단 두가지이다.1. 오른쪽과 아래쪽으로만 움직인다2. 물에 잠긴 곳은 이동 불가능

 

💡알고리즘 설계

1. 일단 m x n 격자모양을 보고 2차원 배열을 만들어야겠다고 생각했다.

# 지도 만들기
map = [[0] * m for _ in range(n)]

2. 물에 잠긴 위치를 map 위에 -1로 표시해야지

# 물에 잠긴 위치 표시
for p in puddles:
    map[p[1]-1][p[0]-1] = -1

인덱싱때문에 p[1] 대신 p[1]-1을 해줘야 한다.

그리고 처음에 행과 열의 위치를 반대로 써서 틀렸다. 보통 행렬 속 원소의 위치를 나타낼 때 (행, 열)로 나타내지만 이 문제에서는 (열, 행)이다!

3. 첫번째 행과 첫번째 열을 처리해준다.

전부 1로 채우는 게 디폴트이지만 물에 잠긴 위치가 등장한다면 그 이후로 전부 0으로 바꿨다. 물에 잠긴 위치도 -1에서 0으로 바꿔줬다.

0	0	-1	0
0	0	0	0
0	0	0	0

위와 같은 형태라면

1	1	0	0
1	0	0	0
1	0	0	0

이렇게 바꿔준다.

4. DP 탐색을 진행한다. 좌표 하나하나(map[i][j]) 탐색하며 값을 갱신해준다.

만약 좌표가 물에 잠긴 곳이라면? 값을 -1에서 0으로 바꿔주고 다음으로 넘어가기

만약 좌표가 물에 잠기지 않이라면? 왼쪽 좌표의 값과 위쪽 좌표의 값을 더하기

-> 이 때 물에 잠긴 곳을 0으로 바꿔준 이유가 나타난다. 이전에는 물에 잠긴 곳을 -1로 표시했는데, 이러니 물에 잠긴 곳의 상대적 위치에 따라 점화식이 달라져 코드가 엄청 길어졌다..

5. 마지막에 맨 오른쪽 아래에 있는 값을 1000000007로 나눈 나머지를 반환하기

 

💡코드

def solution(m, n, puddles):
    # 1. 지도 만들기
    map = [[0] * m for _ in range(n)]    
    # 2. 물에 잠긴 위치 표시
    for p in puddles:
        map[p[1]-1][p[0]-1] = -1
    # 3. 첫번째 행 처리
    p = 1
    for i in range(m):
        if map[0][i] == -1:
            p = 0
        map[0][i] = p
    # 3. 첫번째 열 처리
    p = 1
    for i in range(n):
        if map[i][0] == -1:
            p = 0
        map[i][0] = p
    print(map)
    # 4. DP 탐색
    for i in range(1, n):
        for j in range(1, m):
            # 물 있으면 0으로 만들기
            if map[i][j] == -1:
                map[i][j] = 0
                continue
            map[i][j] = map[i][j-1] + map[i-1][j]
    
    return map[-1][-1] % 1000000007

 

💡 오답 풀이

global asw
asw = 0
def move(x, y):
    global asw
    r = (map[x][y+1] == 0)
    d = (map[x+1][y] == 0)
    if r and d:
        move(x, y+1)
        move(x+1, y)
    elif r and not d:
        move(x, y+1)
    elif d and not r:
        move(x+1, y)
    else:
        asw += 1

처음에는 물에 잠긴 곳을 -1로 두고 조건별로 다른 점화식을 두었다.

그러나 물에 잠긴 곳을 0으로 바꾸니 하나의 점화식으로 가능해졌다.

 

처음에는 첫번째 행, 첫번째 열에 물에 잠긴 위치가 존재하는 경우를 고려하지 못하고 일단 다 1로 채워버렸다.

특수한 상황을 고려하자!

# 첫번째 행 처리
for i in range(m):
    if map[0][i] == -1:
        map[0][i] = 0
        break
    map[0][i] = 1
# 첫번째 열 처리
for i in range(n):
    if map[i][0] == -1:
        map[i][0] = 0
        break
    map[i][0] = 1

첫번째 행이 [0, 0, -1, 0, 0, -1, 0]일 수도 있다. -1이 나온다고 해서 바로 break문을 걸어버리면 안된다.

 

💡 느낀점 or 기억할정보

동적계획법은 너무 어렵지만

작은 문제로 큰 문제를 해결한다는 개념, 그리고 dp테이블을 만들어서 결과를 저장한다는 개념 - 이 두 가지를 머릿속에 잘 간직해두면 시작할 수 있다.

하지만 특수한 상황, 조건들을 빼먹지 말아야겠다..!