Programmers] 공원 산책

📌 파이썬 으로 풀이

 

📌 문제 링크 :

프로그래머스

 

📌 문제 설명 :

지나다니는 길을 'O', 장애물을 'X'로 나타낸 직사각형 격자 모양의 공원에서 로봇 강아지가 산책을 하려합니다. 산책은 로봇 강아지에 미리 입력된 명령에 따라 진행하며, 명령은 다음과 같은 형식으로 주어집니다.

• ["방향 거리", "방향 거리" … ]

예를 들어 "E 5"는 로봇 강아지가 현재 위치에서 동쪽으로 5칸 이동했다는 의미입니다. 로봇 강아지는 명령을 수행하기 전에 다음 두 가지를 먼저 확인합니다.

• 주어진 방향으로 이동할 때 공원을 벗어나는지 확인합니다.
• 주어진 방향으로 이동 중 장애물을 만나는지 확인합니다.

위 두 가지중 어느 하나라도 해당된다면, 로봇 강아지는 해당 명령을 무시하고 다음 명령을 수행합니다.
공원의 가로 길이가 W, 세로 길이가 H라고 할 때, 공원의 좌측 상단의 좌표는 (0, 0), 우측 하단의 좌표는 (H - 1, W - 1) 입니다.

공원을 나타내는 문자열 배열 park, 로봇 강아지가 수행할 명령이 담긴 문자열 배열 routes가 매개변수로 주어질 때, 로봇 강아지가 모든 명령을 수행 후 놓인 위치를 [세로 방향 좌표, 가로 방향 좌표] 순으로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

📌 제한 사항

• 3 ≤ park의 길이 ≤ 50
  • 3 ≤ park[i]의 길이 ≤ 50
    • park[i]는 다음 문자들로 이루어져 있으며 시작지점은 하나만 주어집니다.
      • S : 시작 지점
      • O : 이동 가능한 통로
      • X : 장애물
  • park는 직사각형 모양입니다.
• 1 ≤ routes의 길이 ≤ 50
  • routes의 각 원소는 로봇 강아지가 수행할 명령어를 나타냅니다.
  • 로봇 강아지는 routes의 첫 번째 원소부터 순서대로 명령을 수행합니다.
  • routes의 원소는 "op n"과 같은 구조로 이루어져 있으며, op는 이동할 방향, n은 이동할 칸의 수를 의미합니다.
    • op는 다음 네 가지중 하나로 이루어져 있습니다.
      • N : 북쪽으로 주어진 칸만큼 이동합니다.
      • S : 남쪽으로 주어진 칸만큼 이동합니다.
      • W : 서쪽으로 주어진 칸만큼 이동합니다.
      • E : 동쪽으로 주어진 칸만큼 이동합니다.
    • 1 ≤ n ≤ 9

 

📌 입출력 예

---

추측) 

일단 현재 위치에 대한 배열을 저장 [열, 행] 기본 [0,0]

그리고 park 배열에서 S의 위치를 찾아 현재 위치를 갱신해 준다. 

그리고 routes를 for문으로 돌려 하나씩 빼와서 현재위치를 이동을 시키는 데

먼저 판별부터 한다.

1. E나 W면 현재 위치의 열에서 n만큼 E면 +, W면 -  시키고 해당 값(x1)이 park 인덱스 하나의 길이보다 길어지면 해당 routes는 cotinue로 바로 넘어감

2. N나 S면 현재 위치의 행에서 n만큼 S면 +, N이면 -  시키고 해당 값(y1)이 park 전체 길이보다 길어지면 해당 routes는 cotinue로 바로 넘어감

 

위의 2가지 판별이 모두 통과하면

이제 중간 장애물 판정을 해야함

위에서 길이 판별할때 저장해 놓은 값을 가지고 

1. E나 W면 park 해당 x번째 인덱스 값에서 현재 위치의 x값과 이동후 값인 x1값 문자열 순서 사이에 X가 포함되어 있으면 routes는 cotinue로 바로 넘어감

2. N나 S면 현재 위치의 y값과 이동후 값인 y1값 사이에 인덱스 값의 x번째 문자열에 X가 포함되어 있으면 routes는 cotinue로 바로 넘어감

 

이마저도 다 통과하면

현재 위치를 x1과 y1으로 변경하고 다음 routes로 넘어간다. 

 

소스코드) 

* 1차)  실패: 정확도 80점 

def solution(park, routes):
    now = [0,0]
    
    # 시작점 
    for i in range(0,len(park)):
        if 'S' in park[i]:
            now[0] = i                      # 행
            now[1] = park[i].index('S')     # 열
            
            
    x1 = y1 = 0
    # Route 판별
    for route in routes :
        
        # 공원 밖인지 판별
        if route[0] == 'E' :
            x1 = now[1] + int(route[2])
            if x1 > len(park[0])-1 :
                continue
        elif route[0] == 'W' :
            x1 = now[1] - int(route[2])
            if x1 < 0 :
                continue
        elif route[0] == 'S' :
            y1 = now[0] + int(route[2])
            if y1 > len(park)-1 :
                continue
        elif route[0] == 'N' :
            y1 = now[0] - int(route[2])
            if y1 < 0 :
                continue
                

        b_x = b_y = a_x = a_y = 0    
        # 장애물 판별
        if route[0] == 'E' or route[0] == 'W' :
            if now[1] > x1 :
                b_x = x1
                a_x = now[1]
            else :
                b_x = now[1]
                a_x = x1
                
            if 'X' in park[now[0]][b_x:a_x]:
                continue
            else :
                now[1] = x1
        else :  
            
            if now[0] > y1 :
                b_y = y1
                a_y = now[0]
            else :
                b_y = now[0]
                a_y = y1
            
            if 'X' in [ park[j][now[1]] for j in range(b_y,a_y) ]:
                continue
            else :
                now[0] = y1
                
    
    return now

* 2차) 성공

def solution(park, routes):
    now = [0,0]
    
    # 시작점 
    for i in range(0,len(park)):
        if 'S' in park[i]:
            now[0] = i                      # 행
            now[1] = park[i].index('S')     # 열
            
    x1 = y1 = 0
    # Route 판별
    for route in routes :
        
        # 공원 밖인지 판별
        if route[0] == 'E' :
            x1 = now[1] + int(route[2])
            if x1 > len(park[0])-1 :
                continue
        elif route[0] == 'W' :
            x1 = now[1] - int(route[2])
            if x1 < 0 :
                continue
        elif route[0] == 'S' :
            y1 = now[0] + int(route[2])
            if y1 > len(park)-1 :
                continue
        elif route[0] == 'N' :
            y1 = now[0] - int(route[2])
            if y1 < 0 :
                continue

        b_x = b_y = a_x = a_y = 0    
        # 장애물 판별
        if route[0] == 'E' or route[0] == 'W' : 
            if now[1] > x1 :
                b_x = x1
                a_x = now[1]
            else :
                b_x = now[1]+1
                a_x = x1+1
                
            if 'X' in park[now[0]][b_x:a_x]:
                continue
            else :
                now[1] = x1
        else :  
            if now[0] > y1 :
                b_y = y1
                a_y = now[0]
            else :
                b_y = now[0]+1
                a_y = y1+1

            if 'X' in [ park[j][now[1]] for j in range(b_y,a_y) ]:
                continue
            else :
                now[0] = y1
                
    return now

 

 

리뷰) 

1차에서 실패했던 관건은 X 가 어디에 있는지 판별하는 구역을 잘 파악했어야 했다는 점이었다.

현재 위치는 판별에서 제외했어야 했는데 ㅠ

특히 사방팔방 다 장애물이라 움직이지 못할 때 이 문제가 발생했다.

 

현재 위치를 포함 시켜 버리면서 S는 X가 아니다 보니 X판별할 때 OK X없음 해버리고 움직여버리는 사태가!

그래서 X판별할때 현재 위치를 제외하니 모두 통과했다

 

그리고 분명 더 좋은 방법이 있을거 같아 찾아보니 BFS로 푸는 방법이 있다고 한다. BFS를 공부해서 다시 풀어보는 걸로