프로그래머스 | 레벨1 | 공원 산책 | C++

프로그래머스 공원 산책

 

프로그래머스 | 레벨1 | 공원 산책 | C++

프로그래머스

 

1. 문제 접근

■ 1.1 시뮬레이션

로봇 강아지가 명령을 수행하기 전에 다음 두 가지 조건을 만족해야 한다. 첫 번째는 주어진 방향으로 이동할 때 공원을 벗어나면 안 되고, 두 번째는 주어진 방향으로 이동할 때 장애물을 만나면 안 된다. 인접 행렬로 표현한 그래프에서 두 가지 조건을 만족하는 경우에만 로봇 강아지를 실제로 이동시킨다.

 

2. 문제 풀이

■ 2.1 첫 번째 풀이 가이드

1. 공원을 인접 행렬로 표현하는 adj 배열을 선언하고 주어진 park 배열로 초기화한다. 공원의 세로 길이는 N, 가로 길이는 M으로 초기화한다.
2. routes 배열에서 로봇 강아지가 이동할 방향과 이동할 거리를 불러온다. isObstacle()을 통해서 두 가지 조건을 만족하는지 확인한다.
   • 로봇 강아지가 이동한 곳이 공원의 가로 길이와 세로 길이를 벗어나는지 확인한다.
   • 로봇 강아지가 이동하는 중에 adj 배열에서 'X'을 만나는지 확인한다.

 

■ 2.2 두 번째 풀이 가이드

1. 사방위로 이동할 방향과 이동할 거리를 나타내는 dx, dy 배열과 이동할 방향을 키, 0부터 3까지 인덱스를 값으로 하는 direction 비정렬 연관 컨테이너를 선언한다.
   • 남쪽 'S'는 인덱스 0과 연결한다. (dx[0], dy[0])는 (1, 0)이므로 강아지가 아래로 한 칸 이동한다.
   • 북쪽 'N'는 인덱스 1과 연결한다. (dx[1], dy[1])은 (-1, 0)이므로 강아지가 위로 한 칸 이동한다.
   • 동쪽 'E'는 인덱스 2과 연결한다. (dx[2], dy[2])는 (0, 1)이므로 강아지가 오른쪽으로 한 칸 이동한다.
   • 서쪽 'W'는 인덱스 3과 연결한다. (dx[3], dy[3])은 (0, -1)이므로 강아지가 왼쪽으로 한 칸 이동한다.
2. routes 배열에서 로봇 강아지가 이동할 방향과 이동할 거리를 불러온다. 로봇 강아지를 방향에 맞게 한 칸씩 이동하면서 두 가지 조건을 만족하는지 확인한다.
   • 로봇 강아지가 이동한 칸이 공원의 가로 길이와 세로 길이는 벗어나는지 확인한다.
   • 로봇 강아지가 이동한 칸이 park 배열의 'X'인지 확인한다.

IMPORTANT 사방위 방향을 나타내는 dx, dy 배열의 인덱스와 비정렬 연관 컨테이너의 값을 맞춰 놓음으로써 switch 문을 사용하지 않아도 된다.

 

3. 문제 해결

■ 3.1 첫 번째 풀이

#include <string>
#include <vector>
#include <iostream>
#define X first
#define Y second
using namespace std;

vector<vector<char>> adj;
pair<int, int> S, R;
int N, M;

void MakeGraph(vector<string>& park) {
    N = park.size();
    M = park[0].size();
    S = { 0, 0 }, R = { 0, 0 };
    
    adj = vector<vector<char>>(N, vector<char>(M, 'O'));
    for (unsigned int i = 0; i < park.size(); ++i) {
        for (unsigned int j = 0; j < park[i].size(); ++j) {
            adj[i][j] = park[i][j];
            if (adj[i][j] == 'S') { R = S = { i, j }; }
        }
    }
}

bool isObstacle(char op, int n) {
    bool isObstacle = false;
    
    switch(op) {
        case 'E':
            if (R.Y + n >= M) { isObstacle = true; break; }
            for (int i = R.Y + 1; i <= R.Y + n; ++i) {
                if (adj[R.X][i] == 'X') {
                    isObstacle = true;
                    break;
                }
            }
            break;
                    
        case 'W':
            if (R.Y - n < 0) { isObstacle = true; break; }
            for (int i = R.Y - 1; i >= R.Y - n; --i) {
                if (adj[R.X][i] == 'X') {
                    isObstacle = true;
                    break;
                }
            }
            break;
                    
        case 'S':
            if (R.X + n >= N) { isObstacle = true; break; }
            for (int i = R.X + 1; i <= R.X + n; ++i) {
                if (adj[i][R.Y] == 'X') {
                    isObstacle = true;
                    break;
                }
            }
            break;
                    
        case 'N':
            if (R.X - n < 0) { isObstacle = true; break; }
            for (int i = R.X - 1; i >= R.X - n; --i) {
                if (adj[i][R.Y] == 'X') {
                    isObstacle = true;
                    break;
                }
            }
            break;
    }
    return isObstacle;
}

vector<int> solution(vector<string> park, vector<string> routes) {
    MakeGraph(park);
    
    for (unsigned int i = 0; i < routes.size(); ++i) {
        char op = routes[i][0];
        int n = routes[i][2] - '0';
        
        if (isObstacle(op, n)) {
            continue;
        }
        
        switch (op) {
            case 'E':
                R = { R.X, R.Y + n };
                break;
            case 'W':
                R = { R.X, R.Y - n };
                break;
            case 'S':
                R = { R.X + n, R.Y };
                break;
            case 'N':
                R = { R.X - n, R.Y };
                break;
        }
    }
    
    vector<int> answer{ R.X, R.Y };
    return answer;
}

 

■ 3.2 두 번째 풀이

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> dx = { 1, -1, 0, 0 };
vector<int> dy = { 0, 0, 1, -1 };
unordered_map<char, int> direction = { { 'S', 0 }, { 'N', 1 }, { 'E', 2 }, { 'W', 3 } };

vector<int> solution(vector<string> park, vector<string> routes) {
    int H = park.size();
    int W = park[0].size();
    int cx, cy;
    
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (park[i][j] == 'S') {
                cx = i, cy = j;
            }
        }
    }
    
    int nx, ny;
    for (unsigned int i = 0; i < routes.size(); ++i) {
        int op = direction[routes[i][0]];
        int n = routes[i][2] - '0';
        bool isValid = true;
        
        nx = cx; ny = cy;
        for (int j = 0; j < n; ++j) {
            nx += dx[op];
            ny += dy[op];
            
            // 공원을 벗어나는 경우
            if (nx < 0 || ny < 0 || nx >= H || ny >= W) {
                isValid = false;
                break;
            }
            // 장애물을 만나는 경우
            if (park[nx][ny] == 'X') {
                isValid = false;
                break;
            }
        }
        
        if (isValid) {
            cx = nx; cy = ny;
        }
    }
    
    return { cx, cy };
}

 

4. 문제 고찰

첫 번째 풀이는 사방위 방향에 따라서 로봇 강아지의 도착 지점이 공원을 벗어나는지, 도착 지점으로 가는 동안 X를 만나는지 확인하고 위의 조건을 만족한다면 다시 방향에 따라서 로봇 강아지를 이동시켜야 했기 때문에 switch 문을 두 번 사용하게 되었다. 정답은 맞혔으나 코드 양이 100줄을 넘어 상당히 보기 불편하였다. 두 번째 풀이는 로봇 강아지가 이동할 방향을 나타내는 dx, dy 배열을 선언하고 비정렬 연관 컨테이너로 인덱스를 맞춰 놓았고 이에 따라 switch 문을 사용하지 않아도 되어 코드 양이 절반으로 줄어들었다.