[프로그래머스] Lv1 - 공원 산책

문제

프로그래머스 연습문제

• Lv 1. 공원 산책 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/172928

코드 구현

def solution(park, routes):

    # Todo
    ## park 배열 -> S 위치 알아내기 (시작점)
    ## routes 문자열 쪼개기 -> 방향 배열 설정 -> N S W E 일 때 각각 row, column 이동 거리 설정
    ## 시작점에서 이동했을 때 -> park 배열 위치를 벗어난다면 -> 해당 route 사용 X (continue로 건너뛰기)
    ##                     park 배열 위치를 벗어나지 않는다면 -> 장애물을 만나는지 확인하기
    ## 이동 거리까지 한칸씩 이동했을 때 -> 장애물이 있다면 -> 해당 route 사용 X
    ## 장애물을 만나지 않는다면 -> 최종 이동해야하는 row, column 거리만큼 이동하기!

    current_location = []       # 현재 위치를 계속 갱신하며 담을 배열
    two_dim_park = []           # park 배열의 2차원 버젼을 담을 배열

    # park 배열에서 S 위치 알아내기 + 2차원 배열로 만들기
    for sub_park in park:
        sub_array = []
        for i in range(len(sub_park)):
            sub_array.append(sub_park[i])

            if(sub_park[i] == "S"):
                current_location.append(park.index(sub_park))
                current_location.append(i)

        two_dim_park.append(sub_array)

    r, c = 0, 0     # 각 route 별 이동해야 할 row, column 거리를 담을 변수

    # routes 배열을 쪼개서 -> 각 route를 파악 -> 이동해야 할 row, column 거리 담기 -> park 밖으로 나가는지 and 장애물을 만나는지 검사 -> 모두 통과한다면 이동
    for i in range(len(routes)):

        op = routes[i].split(' ')[0]        # 방향
        n = int(routes[i].split(' ')[1])    # 거리

        cannot_go = False       # 장애물을 만나는지 따질 때 사용

        r_location = current_location[0]
        c_location = current_location[1]

        if (op == 'N'):
            r = -n
            c = 0

            # park 바깥까지 나간다면 -> continue로 건너뛰어서 이 route 사용하지 않기
            if (r_location + r >= len(two_dim_park) or c_location + c >= len(two_dim_park[0]) or
                    r_location + r < 0 or c_location + c < 0):
                continue

            # park 바깥에 나가지 않는다면 -> 장애물을 만나는지 확인
            for move in range(1, n+1):
                r_location = r_location - 1         # N은 북쪽으로 올라가는 방향이니까 -> row 위치가 n만큼 -1씩 변하게 됨
                if(two_dim_park[r_location][c_location] == 'X'):    # 장애물을 만난다면
                    cannot_go = True        # 지나갈 수 없음
                    break

            # 장애물도 만나지 않는다면 -> 이동하기
            if (cannot_go == False):
                current_location[0] = current_location[0] + r
                current_location[1] = current_location[1] + c


        if (op == 'S'):
            r = n
            c = 0

            if (r_location + r >= len(two_dim_park) or c_location + c >= len(two_dim_park[0]) or
                    r_location + r < 0 or c_location + c < 0):
                continue

            for move in range(1, n+1):
                r_location = r_location + 1         # S은 남쪽으로 내려가는 방향이니까 -> row 위치가 n만큼 +1씩 변하게 됨
                if(two_dim_park[r_location][c_location] == 'X'):
                    cannot_go = True
                    break

            if (cannot_go == False):
                current_location[0] = current_location[0] + r
                current_location[1] = current_location[1] + c


        if (op == 'W'):
            r = 0
            c = -n

            if (r_location + r >= len(two_dim_park) or c_location + c >= len(two_dim_park[0]) or
                    r_location + r < 0 or c_location + c < 0):
                continue

            for move in range(1, n+1):
                c_location = c_location - 1         # W은 왼쪽으로 이동하는 방향이니까 -> column 위치가 n만큼 -1씩 변하게 됨
                if (two_dim_park[r_location][c_location] == 'X'):
                    cannot_go = True
                    break

            if (cannot_go == False):
                current_location[0] = current_location[0] + r
                current_location[1] = current_location[1] + c


        if (op == 'E'):
            r = 0
            c = n

            if (r_location + r >= len(two_dim_park) or c_location + c >= len(two_dim_park[0]) or
                    r_location + r < 0 or c_location + c < 0):
                continue

            for move in range(1, n+1):
                c_location = c_location + 1         # E은 오른쪽으로 이동하는 방향이니까 -> column 위치가 n만큼 +1씩 변하게 됨
                if (two_dim_park[r_location][c_location] == 'X'):
                    cannot_go = True
                    break

            if (cannot_go == False):
                current_location[0] = current_location[0] + r
                current_location[1] = current_location[1] + c


    return current_location

풀이

• 처음 막힌 부분 : 이동하려는 곳에 장애물이 있다면 이동할 수 없는데 이에 대한 조건부를 세우는 것에서 예외 발견
• 기존 코드 알고리즘 : 우선 이동 → 도착한 곳이 범위 밖인지 파악 → 도착한 곳이 장애물이 있는 X인지 판단 → 아니라면 이동
• 잘못된 점 : 이동한 곳이 장애물인 부분 뿐만 아니라 이동 중 장애물이 있다면 해당 위치로 갈 수 없음 !
  • 여기서 처음 생각한 방법 : X의 인덱스를 다 파악해놔서 해당 인덱스가 범위에 포함된다면 이동하지 못하게 하기
  • 이 방법에서도 실패한 점 : 이 방법의 조건문을 설정하는 것이 너무 까다롭고 만약 S인 시작점의 위치가 X 인덱스보다 앞에 있지 않고 뒤에 있다면 범위에 대한 조건문을 세워서 장애물을 피하는건 거의 불가능
    
• 그 다음으로 생각한 방법 : 처음부터 알고리즘 수정하기
  • 우선 이동하지 말고 이동해도 되는지 한칸한칸 따져가며 파악하고 → 이동해도 된다면 최종 이동
  • 수정한 알고리즘 : 이동하려는 범위만큼 for문 range 설정 → 한칸씩 검사 →
    1) park 범위를 벗어나는지 파악 → 2) 한칸씩 이동할 때 장애물이 있는지 파악
    → 둘 다 아니라면 최종 이동
• 각 방향 (N W S E) 에 따라 row, col 에 더해야하는 값이 달라짐 → 각 조건문에 대한 이동 위치가 다름

    # N은 북쪽으로 올라가는 방향이니까 -> row 위치가 n만큼 -1씩 변하게 됨
    # S은 남쪽으로 내려가는 방향이니까 -> row 위치가 n만큼 +1씩 변하게 됨
    # W은 왼쪽으로 이동하는 방향이니까 -> column 위치가 n만큼 -1씩 변하게 됨
    # E은 오른쪽으로 이동하는 방향이니까 -> column 위치가 n만큼 +1씩 변하게 됨

• 동작 과정
  • park 배열 → S 위치 알아내기 (시작점)
  • routes 문자열 쪼개기 → 방향 배열 설정 → N S W E 일 때 각각 row, column 이동 거리 설정
  • 시작점에서 이동했을 때
    → park 배열 위치를 벗어난다면 → 해당 route 사용 X (continue로 건너뛰기)
    → park 배열 위치를 벗어나지 않는다면 → 장애물을 만나는지 확인하기
  • 이동 거리까지 한칸씩 이동했을 때 → 장애물 X가 있다면 → 해당 route 사용 X
  • 장애물을 만나지 않는다면 → 최종 이동해야하는 row, column 거리만큼 이동하기!