[프로그래머스][C++] 공원 산책

공원 산책

문제 링크

공원 산책

분석

“E 5”는 동쪽으로 5칸 이동한다는 의미입니다.

이동 할 때, 공원을 벗어나게 되거나 장애물과 부딪히는 명령은 수행하지 않습니다.

지나갈 수 있는 길은 ‘O’, 장애물이 있어 지나갈 수 없는 길은 ‘X’입니다.

이동할 칸의 수는 1의 자릿수로만 주어집니다.

2차원 배열 문제입니다.

풀이

#include <string>
#include <vector>

using namespace std;

// park의 시작 위치를 반환하는 함수
vector<int> startingPoint(const vector<string>& park)
{
    vector<int> startPoint;

    for (int i = 0; i < park.size(); ++i)
    {
        for (int j = 0; j < park[i].length(); ++j)
        {
            if (park[i][j] == 'S')
            {
                startPoint.push_back(i);
                startPoint.push_back(j);
                return startPoint;
            }
        }
    }
}

vector<int> solution(vector<string> park, vector<string> routes) {
    // 시작 위치로 설정
    vector<int> answer = startingPoint(park);
    
    // routes 순회
    for (int i = 0; i < routes.size(); ++i)
    {
        // 이동할 방향
        char Direction = routes[i][0];
        // 이동할 횟수
        int Count = routes[i][2] - '0';
        
        // 북쪽으로 이동하는 경우 공원을 벗어나는지 확인
        if (Direction == 'N' && answer[0] - Count >= 0)
        {
            // 이동 할 경로에 장애물이 있는지 확인하는 반복문
            for (int j = 1; j <= Count; ++j)
            {
                // 현재 위치를 기준으로 이동할 위치에 장애물이 있다면 이동 횟수를 0으로
                if (park[answer[0] - j][answer[1]] == 'X')
                {
                    Count = 0;
                    break;
                }
            }
            
            // Y축에 대한 값 변경
            answer[0] -= Count;
        }
        // 남쪽으로 이동하는 경우 공원을 벗어나는지 확인
        else if (Direction == 'S' && answer[0] + Count < park.size())
        {
            // 이동 할 경로에 장애물이 있는지 확인하는 반복문
            for (int j = 1; j <= Count; ++j)
            {
                // 현재 위치를 기준으로 이동할 위치에 장애물이 있다면 이동 횟수를 0으로
                if (park[answer[0] + j][answer[1]] == 'X')
                {
                    Count = 0;
                    break;
                }
            }
            
            // Y축에 대한 값 변경
            answer[0] += Count;
        }
        // 서쪽으로 이동하는 경우 공원을 벗어나는지 확인
        else if (Direction == 'W' && answer[1] - Count >= 0)
        {
            // 이동 할 경로에 장애물이 있는지 확인하는 반복문
            for (int j = 1; j <= Count; ++j)
            {
                // 현재 위치를 기준으로 이동할 위치에 장애물이 있다면 이동 횟수를 0으로
                if (park[answer[0]][answer[1] - j] == 'X')
                {
                    Count = 0;
                    break;
                }
            }
            // X축에 대한 값 변경
            answer[1] -= Count;
        }
        // 동쪽으로 이동하는 경우 공원을 벗어나는지 확인
        else if (Direction == 'E' && answer[1] + Count < park[0].length())
        {
            // 이동 할 경로에 장애물이 있는지 확인하는 반복문
            for (int j = 1; j <= Count; ++j)
            {
                // 현재 위치를 기준으로 이동할 위치에 장애물이 있다면 이동 횟수를 0으로
                if (park[answer[0]][answer[1] + j] == 'X')
                {
                    Count = 0;
                    break;
                }
            }
            // X축에 대한 값 변경
            answer[1] += Count;
        }
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(nm) + O(rc)$입니다.

• 2차원 배열인 park를 순회하는 반복문 $O(nm)$
• routes를 순회하는 반복문 $O(r)$
• 장애물을 확인하는 반복문 $O(c)$
• $O(nm) + O(r) \times (c)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 1 〉 통과 (0.01ms, 4.16MB)
테스트 2 〉 통과 (0.01ms, 4.21MB)
테스트 3 〉 통과 (0.01ms, 4.22MB)
테스트 4 〉 통과 (0.01ms, 3.66MB)
테스트 5 〉 통과 (0.02ms, 4.21MB)
테스트 6 〉 통과 (0.02ms, 4.17MB)
테스트 7 〉 통과 (0.01ms, 3.68MB)
테스트 8 〉 통과 (0.02ms, 3.68MB)
테스트 9 〉 통과 (0.03ms, 3.66MB)
테스트 10 〉 통과 (0.02ms, 4.01MB)
테스트 11 〉 통과 (0.02ms, 4.21MB)
테스트 12 〉 통과 (0.02ms, 3.69MB)
테스트 13 〉 통과 (0.02ms, 4.15MB)
테스트 14 〉 통과 (0.02ms, 4.15MB)
테스트 15 〉 통과 (0.02ms, 4.14MB)
테스트 16 〉 통과 (0.01ms, 4.21MB)
테스트 17 〉 통과 (0.02ms, 4.21MB)
테스트 18 〉 통과 (0.01ms, 4.2MB)
테스트 19 〉 통과 (0.02ms, 4.16MB)
테스트 20 〉 통과 (0.02ms, 4.14MB)