[프로그래머스] 등굣길 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

해당 문제는 물에 잠긴 부분을 알려주는 행렬의 x좌표와 y좌표가 바뀌어 주어진다는 것을 알아야 한다.

나와있는 예제가 [[2, 2]]로 나와있어 파악하기 힘들었다.

하여 지도를 만들고 물에 잠긴 위치인치 판단할 때는 x좌표와 y좌표를 바꾸어 생각해줘야 한다.

그리고 지도의 인덱스 값을 그대로 좌표의 값으로 계산하기 위해 0행과 0열을 0으로 초기화하여 추가해 주는데, 이것은 다음 위치의 경우의 수를 계산할 때 따로 고려해주지 않아도 된다는 편리함이 있다.

 

1. 지도를 나타내줄 리스트를 생성하고 map = []
2. 좌표를 인덱스로 그대로 사용하기 위해 행을 인덱스가 n번까지 있도록 반복하고 for _ in range(n + 1)
3. 마찬가지로 열도 m번까지 있도록 반복하여 0으로 초기화한다. map.append([0 for _ in range(m + 1)])
4. 집의 좌표인 1, 1부터 시작하여 학교에 도착할 때까지 반복한다. for i in range(1, n + 1): for j in range(1, m + 1)
5. 만약 해당 위치의 좌표가 물에 잠긴 부분이라면 지나갈 수 없으므로 넘어간다. if ([j, i] in puddles): continue
6. 만약 해당 위치의 좌표가 1, 1로 집의 위치라면 if (i == 1) and (j == 1)
7. 무조건 시작되는 위치이므로 지도에서 해당 위치의 값을 1로 바꿔준다. map[i][j] = 1
8. 반면에 해당 위치의 좌표가 집의 위치가 아니라면 else
9. 해당 위치로 올 수 있는 이전의 두 위치가 모두 물에 잠긴 부분이 아닐 경우 if ([j, i - 1] not in puddles) and ([j - 1, i] not in puddles)
10. 해당 위치에 최단 경로로 올 수 있는 경우는 각 올 수 있는 두 위치의 경우의 수를 더해준 값이다. map[i][j] = map[i - 1][j] + map[i][j - 1]
11. 만약 해당 위치로 올 수 있는 이전의 두 위치 중 오른쪽에서 오는 위치가 물에 잠긴 부분이 아니라면 elif ([j, i - 1] not in puddles)
12. 해당 위치에 최단 경로로 올 수 있는 경우는 오른쪽에서 오는 위치의 값과 동일하다. map[i][j] = map[i - 1][j]
13. 반면에 해당 위치로 올 수 있는 이전의 두 위치 중 위쪽에서 오는 위치가 물에 잠긴 부분이 아니라면 else
14. 해당 위치에 최단 경로로 올 수 있는 경우는 위쪽에서 오는 위치의 값과 동일하다. map[i][j] = map[i][j - 1]
15. 학교까지 갈 수 있는 최단 경로의 경우의 수를 모두 구했으면 학교 위치의 좌표 값을 1,000,000,007로 나눈 값을 구해준다. answer = map[n][m] % 1000000007

반응형

3. 소스코드

def solution(m, n, puddles):
    answer = 0
    
    map = []
    for _ in range(n + 1):
        map.append([0 for _ in range(m + 1)])

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if ([j, i] in puddles):
                continue
            
            if (i == 1) and (j == 1):
                map[i][j] = 1
            else:
                if ([j, i - 1] not in puddles) and ([j - 1, i] not in puddles):
                    map[i][j] = map[i - 1][j] + map[i][j - 1]
                elif ([j, i - 1] not in puddles):
                    map[i][j] = map[i - 1][j]
                else:
                    map[i][j] = map[i][j - 1]

    answer = map[n][m] % 1000000007

    return answer