프로그래머스 공 이동 시뮬레이션 문제 풀이를 진행하였습니다.
문제 해석
문제를 읽으면 아래와 같은 해석이 가능합니다.
n x m크기의 격자가 주어짐
이 격자에 공을 하나 두고, 그 공에 다음과 같은 쿼리들을 날리고자 합니다.
열 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(0, dx))
열 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(1, dx))
행 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(2, dx))
행 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(3, dx))
공은 바깥으로 나갈 수 없으며, 목적지가 격자 바깥인 경우 공은 이동하다가 더 이상 이동할 수 없을 때 멈추게 됩니다.
각 격자들을 시작점으로 생각 후 공을 두고 순서대로 시뮬레이션했을 때 도착점에서 멈춘 공의 갯수를 return해야 합니다.
문제 풀이
처음 문제를 보고 이해하는데도 시간이 많이 걸렸습니다.
일단 최대 격자 수가 매우 크기 때문에 답을 구하기 위한 완전탐색을 사용할 수는 없기에 다른 방법을 찾아야 합니다.
이러한 문제들은 주어진 시뮬레이션만큼 돌아서 답을 구할 수 있는 경우가 많이 존재하기 때문에 시뮬레이션을 활용하여 답을 구할 수 있는지 생각해보았습니다.
순서대로 시뮬레이션 되는 것이기 때문에 도착점으로부터 공을 펼쳐나가 거꾸로 시뮬레이션을 진행시킨 후 끝났을 때의 공의 수를 구하는 방법도 가능성이 있을거라 생각하고 구해보았지만 출발점을 통해 공의 수를 구하는 방법을 찾지 못하였습니다.
답이 안나와 조금 찾아보니... 출발지를 범위로 만들어서 공의 수를 구하는 방법이 있었습니다.
도착지점에 출발지점에서 시작한 공들이 모여 있다고 생각해줍니다.
그리고 쿼리는 상하좌우, 4방향으로 움직이기 때문에 공의 범위는 직사각형으로 나올 것이기에 직사각형을 표현할 두 점의 좌표를 생성해줍니다.
이후 도착지점인 x, y를 두 점의 좌표에 넣어주며 (x, y)(x, y)로 시작해 거꾸로 시뮬레이션을 실행시킵니다.
감소하는 방향의 쿼리는 증가하는 방향으로 계산하고, 증가하는 방향의 쿼리는 감소하는 방향으로 계산하며 좌표를 하나씩 이동시켜줍니다.
여기서 주의할 점은 좌표의 값들 중 격자의 벽에 붙어있는 좌표는 계산이 조금 달라집니다.
예를 들어 n = 5, m = 5라는 격자가 주어지고, (2, 0)(4, 0)이라는 좌표가 있을 때 열이 감소하는 방향으로 2칸 이동하는 쿼리가 주어진다면
이런 모양이 아닌
이러한 모양이 나오게됩니다.
벽의 공이 부딪히게 되면 그 자리게 있다는 조건 때문에 아래의 시뮬레이션이 맞는 상황입니다.
이는 상하좌우 전체에 적용되며, 그림을 하나씩 그려보면서 이해할 수 있었습니다.
단, 벽에 붙어있지 않는 경우는 위와 같은 방식으로 두 좌표가 같이 움직여주어야 합니다.
전체 코드
예상 외로 이해하는데 많은 어려움을 느낀 문제였습니다.
#include <bits/stdc++.h>
#include <string>
#include <vector>
using namespace std;
long long solution(int n, int m, int x, int y, vector<vector<int>> queries) {
long long answer = 0;
//범위 지정
pair<long long, long long> start = make_pair(x, y);
pair<long long, long long> end = make_pair(x, y);
for(int i = queries.size()-1; i >= 0; i--)
{
long long dir = queries[i][0];
long long dist = queries[i][1];
switch(dir){
case 0: //열이 감소하는 방향 -> 오른쪽으로 범위 이동
if(start.second != 0) //0이 왼쪽에 붙어있음 -> 벽의 부딪힘 때문에 dist값만큼의 오른쪽 공의 수를 0으로 옮길 수 있음
start.second += dist;
end.second += dist; //범위 더해준 후 값 넘어가지 않도록 조정
if(end.second > m-1)
end.second = m-1;
break;
case 1: //열이 중가하는 방향 -> 왼쪽으로 범위 이동
start.second -= dist;
if(start.second < 0)
start.second = 0;
if(end.second != m-1) //0이 오른쪽에 붙어있음 -> 벽의 부딪힘 때문에 dist값만큼의 왼쪽 공의 수를 m-1으로 옮길 수 있음
end.second -= dist;
break;
case 2: //행이 감소하는 방향 -> 아래쪽으로 범위 이동
if(start.first != 0) //0이 위쪽에 붙어있음 -> 벽의 부딪힘 때문에 dist값만큼의 아래쪽 공의 수를 0으로 옮길 수 있음
start.first += dist;
end.first += dist;
if(end.first > n-1)
end.first = n-1;
break;
case 3: //행이 증가하는 방향 -> 위쪽으로 범위 이동
start.first -= dist;
if(start.first < 0)
start.first = 0;
if(end.first != n-1) //0이 아래쪽에 붙어있음 -> 벽의 부딪힘 때문에 dist값만큼의 위쪽 공의 수를 n-1으로 옮길 수 있음
end.first -= dist;
break;
}
//값이 지정된 격자를 넘어간다면 불가능한 조건
if(start.first < 0 || start.second > m-1 || end.first < 0 || end.second > m-1)
return answer;
}
//사각형의 범위 계산
answer = (abs(start.first - end.first)+1) * (abs(start.second - end.second)+1);
return answer;
}출저
https://school.programmers.co.kr/learn/courses/30/lessons/87391
