프로그래머스 - 공원 산책

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

// 프로그래머스 - 공원 산책
// https://school.programmers.co.kr/learn/courses/30/lessons/172928

// 문제 설명
// 'O'(통로) / 'X'(장애물) / 'S'(시작)로 이루어진 직사각형 공원에서
// 로봇 강아지가 "op n"(방향 op로 n칸) 명령을 순서대로 수행한다.
// 단, 명령대로 갔을 때 (1) 공원을 벗어나거나 (2) 도중에 장애물을 지나면
// 그 명령은 무시하고 다음 명령으로 넘어간다.
// 모든 명령 수행 후 위치를 [세로(행), 가로(열)]로 반환한다.

// 접근
// - 좌상단 (0,0), N=행-1 / S=행+1 / W=열-1 / E=열+1
// - 명령마다 "한 칸씩" 전진하며 매 칸이 공원 안인지·장애물 아닌지 검사
// - 한 칸이라도 걸리면 그 명령 전체를 무시(중간 칸 통과 검사가 핵심)
// - 전 구간 통과한 명령만 실제 위치에 반영

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<string> park, vector<string> routes) {
    int n = park.size(), m = park[0].size();
    int r = 0, c = 0;

    // 시작 지점 'S' 찾기
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (park[i][j] == 'S') { r = i; c = j; }

    for (string& route : routes) {
        char op = route[0];
        int d = route[2] - '0';     // 이동할 칸 수
        int dr = 0, dc = 0;
        if (op == 'N') dr = -1;
        else if (op == 'S') dr = 1;
        else if (op == 'W') dc = -1;
        else dc = 1;                // 'E'

        // 한 칸씩 전진하며 공원 이탈/장애물을 검사 — 하나라도 걸리면 명령 전체 무시
        int nr = r, nc = c;
        bool ok = true;
        for (int k = 0; k < d; k++) {
            nr += dr; nc += dc;
            if (nr < 0 || nr >= n || nc < 0 || nc >= m || park[nr][nc] == 'X') {
                ok = false;
                break;
            }
        }
        if (ok) { r = nr; c = nc; }  // 전 구간 통과한 명령만 실제 이동
    }

    return {r, c};
}

정리

• 핵심은 “끝 칸만 검사하면 안 되고, 지나가는 중간 칸까지 모두 검사”해야 한다는 점이다. 예제 2처럼 목적지는 멀쩡해도 도중에 장애물을 지나면 명령 전체를 무시한다.
• 그래서 d칸을 한 번에 더하지 않고 한 칸씩 전진하며 매 칸마다 이탈·장애물을 검사한다. 하나라도 걸리면 ok=false로 끊는다.
• 임시 좌표 nr, nc로 시뮬레이션하고, 전 구간을 통과한 경우에만 실제 좌표 r, c에 반영한다. 검사 중에 본 좌표를 바로 갱신하면, 중간에 실패했을 때 위치가 오염된다.
• 방향은 dr, dc 증분으로 통일하면 4방향 분기가 깔끔해진다 — N/S는 행을 ±1, W/E는 열을 ±1.
• 반환은 [행, 열] 순서다. (가로/세로 순서를 뒤집기 쉬운 함정)