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

 

 

 

 

 

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

프로그래머스

 

이번 문제는 BFS와 유사한 문제였습니다.

2가지 방법으로 구현했습니다.

 

 

 

 

 

1. BFS와 유사하게 풀이

📝 문제 풀이

1. map 컨테이너를 이용하여 방향을 나타내는 문자('N' 또는 'S' 또는 'W' 또는 'E')와 해당 좌표를 인덱스로 매핑

2. 시작점을 loc 변수에 저장

3. routes(로봇 강아지가 수행할 명령이 담긴 문자열 배열)를 순회하면서 각 명령마다 거리(n)만큼 while문 수행

• 산책하려는 좌표(nx, ny)가 park 배열의 범위 내에 있고 장애물이 없다면 계속 진행 (n--)
• 산책하려는 좌표(nx, ny)가 park 배열의 범위 밖에 있거나 장애물이 있다면 while문 종료

4. 거리(n)만큼 산책을 완료했다면 loc 변수에 (nx, ny) 좌표 저장

 

 

 

 

👩🏻‍💻 C++ 코드

#include <string>
#include <vector>
#include <map>

using namespace std;

typedef struct {
int x, y;
}box;

// 상 하 좌 우
box moveD[4] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
map<char, int> mapping = { { 'N', 0 }, { 'S', 1 }, { 'W', 2 }, { 'E', 3 } }; // 1

vector<int> solution(vector<string> park, vector<string> routes) {
	pair<int, int> loc;
	
	int H = park.size();
	int W = park[0].size();
	
	for (int i = 0; i < H; i++) {
	    for (int j = 0; j < W; j++) {
	        if (park[i][j] == 'S') {
	            loc = { i, j }; // 2
	            break;
	        }
	    }
	}
	
    	// 3
	for (const auto &route: routes) {
	    char op = mapping[route[0]];
	    int n = route[2] - 48;
	
	    int nx = loc.first;
	    int ny = loc.second;
	
	    while (n--) {
	        nx += moveD[op].x;
	        ny += moveD[op].y;
	
	        if ((nx < 0 || H <= nx || ny < 0 || W <= ny) || park[nx][ny] == 'X') 
						break;
	    }
		
	    if (n < 0) loc = { nx, ny }; // 4
	}

	return { loc.first, loc.second };
}

 

프로그래머스 - 결과 화면

 

 

 

 

 

 

2. 분기문으로 풀이

📝 문제 풀이

1. 시작점을 loc 변수에 저장

2. routes(로봇 강아지가 수행할 명령이 담긴 문자열 배열)를 순회하면서 각 명령마다 walk 함수 실행

     - 각 명령의 방향(op)에 따라 loc 변수의 범위 및 장애물 여부 확인

     - if 문에 걸리지 않고 for문이 종료되면 각 명령의 방향(op)에 따라 loc 변수 업데이트

 

 

 

 

👩🏻‍💻 C++ 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

pair<int, int> loc;

void walk(const vector<string>& park, char op, int n) {
    int H = park.size();
    int W = park[0].size();

    if (op == 'N') {
        for (int i = 1; i <= n; i++) {
            if (loc.first - i < 0 || park[loc.first - i][loc.second] == 'X') return;
        }

        loc.first -= n;
    } else if (op == 'E') {
         for (int i = 1; i <= n; i++) {
            if (loc.second + i >= W || park[loc.first][loc.second + i] == 'X') return;
        }

        loc.second += n;
    } else if (op == 'S') {
         for (int i = 1; i <= n; i++) {
            if (loc.first + i >= H || park[loc.first + i][loc.second] == 'X') return;
        }

        loc.first += n;
    } else if (op == 'W') {
        for (int i = 1; i <= n; i++) {
            if (loc.second - i < 0 || park[loc.first][loc.second - i] == 'X') return;
        }

        loc.second -= n;
    }
}

vector<int> solution(vector<string> park, vector<string> routes) {
    vector<int> answer;
    int H = park.size();
    int W = park[0].size();

    for (int i=0; i<H; i++) {
        for (int j=0; j<W; j++) {
            if (park[i][j] == 'S') {
                loc = { i, j };
                break;
            }
        }
    }

    for (const auto &route: routes) {
        char op = route[0];
        int n = route[2] - 48;

        walk(park, op, n);
    }

    answer.push_back(loc.first);
    answer.push_back(loc.second);

    return answer;
}

 

프로그래머스 - 결과 화면