[연습문제] 공원 산책

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

프로그래머스

---

문제 설명
지나다니는 길을 '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

---

입출력 예

park	routes	result
[     "SOO",     "OOO",     "OOO" ]	["E 2","S 2","W 1"]	[2,1]
[     "SOO",     "OXX",     "OOO" ]	["E 2","S 2","W 1"]	[0,1]
[     "OSO",     "OOO",     "OXO",     "OOO" ]	["E 2","S 3","W 1"]	[0,0]

---

입출력 예 설명
입출력 예 #1

• 입력된 명령대로 동쪽으로 2칸, 남쪽으로 2칸, 서쪽으로 1칸 이동하면 [0,0] -> [0,2] -> [2,2] -> [2,1]이 됩니다.

입출력 예 #2

• 입력된 명령대로라면 동쪽으로 2칸, 남쪽으로 2칸, 서쪽으로 1칸 이동해야하지만 남쪽으로 2칸 이동할 때 장애물이 있는 칸을 지나기 때문에 해당 명령을 제외한 명령들만 따릅니다.
• 결과적으로는 [0,0] -> [0,2] -> [0,1]이 됩니다.

입출력 예 #3

• 처음 입력된 명령은 공원을 나가게 되고 두 번째로 입력된 명령 또한 장애물을 지나가게 되므로 두 입력은 제외한 세 번째 명령만 따르므로 결과는 다음과 같습니다.
• [0,1] -> [0,0]

---

격자 모양의 공원에서 로봇 강아지를 산책시켰을 때, 제대로 된 명령들만 수행한다면 최종적으로 어디에 위치하는지 구하는 문제입니다.

 

정상적인 명령은 다음 두 조건을 지켜야만 합니다.

• 이동 후 공원 내에 위치해야 함
• 장애물을 지나지 않아야 함

이동하는 방법은 모두 정해져 있기 때문에, 규칙에 맞게 로봇 강아지의 현재 position을 반복문으로 확인하면서 진행하면 됩니다.

 

정답 코드를 작성해보겠습니다.

 

1. 자바

import java.util.HashMap;
import java.util.ArrayList;

class Solution {
    public int[] solution(String[] park, String[] routes) {
        // 공원의 가로, 세로를 설정합니다.
        int n = park.length, m = park[0].length();

        // 방향과 이동 거리를 해시맵으로 저장합니다.
        HashMap<String, int[]> directions = new HashMap<>();
        directions.put("N", new int[]{-1, 0}); // 북쪽
        directions.put("S", new int[]{1, 0}); // 남쪽
        directions.put("E", new int[]{0, 1}); // 동쪽
        directions.put("W", new int[]{0, -1}); // 서쪽

        // 시작점과 장애물 위치를 설정합니다.
        int nx = 0, ny = 0;
        ArrayList<int[]> obstacles = new ArrayList<>(); // 장애물 위치를 저장할 리스트

        for (int i = 0; i < n; i++) { // 공원의 모든 위치에 대해 탐색합니다.
            for (int j = 0; j < m; j++) {
                if (park[i].charAt(j) == 'S') { // 시작점일 경우
                    nx = i;
                    ny = j;
                }
                if (park[i].charAt(j) == 'X') { // 장애물일 경우
                    obstacles.add(new int[]{i, j}); // 장애물 위치를 추가
                }
            }
        }

        // 경로를 따라 이동합니다.
        for (String route : routes) {
            // 방향과 거리를 분리합니다.
            String[] parts = route.split(" ");
            String direction = parts[0];
            int steps = Integer.parseInt(parts[1]);

            // 방향 벡터를 가져옵니다.
            int[] move = directions.get(direction);

            // 이동 가능한지 확인하며 이동
            int tx = nx, ty = ny;
            boolean canMove = true;
            for (int i = 0; i < steps; i++) {
                tx += move[0];
                ty += move[1];

                // 공원 범위를 벗어나거나 장애물에 닿으면 이동 중단
                if (tx < 0 || tx >= n || ty < 0 || ty >= m) {
                    canMove = false;
                    break;
                }
                for (int[] obstacle : obstacles) {
                    if (obstacle[0] == tx && obstacle[1] == ty) {
                        canMove = false;
                        break;
                    }
                }
                if (!canMove)
                    break;
            }

            // 이동이 가능하면 현재 위치를 업데이트
            if (canMove) {
                nx = tx;
                ny = ty;
            }
        }

        return new int[]{nx, ny};
    }
}

 

2. 파이썬

def solution(park, routes):
    # 방향 및 이동 거리
    directions = {"N": (-1, 0), "S": (1, 0), "W": (0, -1), "E": (0, 1)}
    # 공원의 가로, 세로
    n, m = len(park), len(park[0])
    
    # 시작점 및 장애물 위치 설정
    obs = {(i, j) for i, row in enumerate(park) for j, col in enumerate(row) if col == "X"}
    nx, ny = next((i, row.index("S")) for i, row in enumerate(park) if "S" in row)
    
    # 경로를 진행합니다
    for route in routes:
        # 방향과 이동 거리를 분리합니다.
        d, step = route.split()
        dx, dy = directions[d]
        # 이동 거리는 정수로 변환합니다.
        step = int(step)
        
        # 다음 위치로의 이동이 가능한지 확인합니다.
        tx, ty, valid = nx, ny, True
        # 한 칸씩 이동하면서 검증합니다.
        for _ in range(step):
            # 각각의 위치를 탐색합니다.
            tx, ty = tx + dx, ty + dy
            # 조건을 벗어나는 경우가 있다면
            if not (0 <= tx < n and 0 <= ty < m) or (tx, ty) in obs:
                valid = False # 검증값을 False로 바꿉니다.
                break
        
        # 유효한 경로라면 이동합니다.
        if valid:
            nx, ny = tx, ty
    
    # 마지막 위치를 반환합니다.
    return [nx, ny]

 

정상적인 경로는 그 진행 과정에서 단 한 번도 공원 밖으로 나간다거나, 장애물을 만나서는 안 됩니다.

따라서 경로를 확인할 때는 끝지점만을 보는 게 아니라, 반복문을 통해서 이동 거리를 한 칸씩 확인하면서 가야하죠.

그리고 도중에 올바르지 않은 경로라면 다시 원래 위치로 돌아와야 합니다.

 

저는 시작점과 장애물을 우선적으로 기록한 뒤, 경로를 한 칸씩 진행하면서 이동이 가능한지 확인하였습니다

만약 이동이 가능하면 valid 값은 참으로 유지되며 현재 위치를 갱신하지만, 불가능하면 valid 값이 거짓으로 바뀌며 현재 위치를 갱신하지 않게 됩니다.

굳이 플래그 변수를 사용하는 이유는 이중 반복문 구조이기 때문입니다. 한 칸씩 확인해야 한다는 조건 때문에 플래그를 세워서 참/거짓의 경우를 나눠야 합니다.

 

이중 반복문을 통해 각각의 경로를 검증했다면, 현 위치가 마지막으로 이동한 위치이므로 해당 값을 반환하면 됩니다.