문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/87391?language=java
오랜만에 풀어본 프로그래머스 Level 3 문제.
1시간 제한시간을 두고 풀었는데, 로직만 생각하다가 결국에 실패했다.
끝나고도 천천히 고민해 봤지만 마땅히 답이 떠오르지 않아, 여러 정보를 참고해 봤다.
개인적으로 이 문제는 수학적인 센스를 요구하는 문제인 것 같다.
어떻게 이런 생각을 하지..
문제 핵심 및 풀이
문제 제한 사항 잘 파악하기
문제만 읽어보면 단순한 BFS 혹은 완전 탐색 시뮬레이션이라고 생각하기 쉽다.
하지만 제한사항을 보면 절대 그렇지 않은 것을 확인할 수 있다.
n과 m의 범위, 그러니까 행과 열의 개수가 모두 10^9까지 가능하다.
이 말은 격자가 총 10^9 * 10^9 = 10^18까지 나올 수 있다는 소리이다.
모든 격자를 일일이 탐색한다는 것은 불가능하다.
쿼리의 최대 개수는 200,000개(2*10^5)다.
이 쿼리를 거의 한번 순회하는 것으로 이 문제를 해결하는 방법이 필요하다.
주어진 정보 파악하기
이 문제를 풀기 위해선, 주어진 정보의 특성을 파악하는 것이 중요하다.
하나씩 살펴보자.
일단 최종적으로 구해야 하는 것은 특정 행과 열(x, y)에 도착하는 시작점의 개수이다.
그래서 특정 행과 열(x, y)를 제외한 나머지 위치는 알 필요가 없다.
즉, 나머지 위치에 도착하는 시작점은 계산할 필요가 없다.
그럼 여기서 한 가지 의문이 생긴다.
원하는 위치에 도착하는 시작점인지 아닌지를 어떻게 판별할까?
가장 명료한 방법은 도착지점부터 역으로 계산하면 된다.
처음에는 역으로 계산하기엔 경우의 수가 너무 많지 않나?라는 생각을 했는데,
이 문제에서는 움직여야 하는 방향과 횟수가 정해진다.
즉, 우리는 이를 도착지점부터 시작하여 역으로 계산하기 때문에,
주어진 방향의 반대 방향으로 횟수만큼 움직이면 된다.
움직임에 대한 경우의 수를 어떻게 구해야 할까?
이 문제에 대한 핵심이다.
난 이 부분을 전혀 떠올리지 못해서 인터넷을 참고했다.
핵심은 가능한 시작점을 하나의 점이 아닌, 범위로 생각하는 것이다.
무슨 소리인지는 그림을 통해 설명하겠다.
위와 같이 1행 1열에 도착하는 시작점을 알아보고자 한다.
여기서 몇 가지 가정을 하는데, 가로 이동과 세로 이동을 구분해서 볼 것이다.
세로 이동으로 "↑↑"가 있다고 생각해 보자.
위로 2칸을 이동했을 때, 도착점에 갈 수 있는 격자는 어디일까?
위로 2칸을 가기 전에 공이 초록색 범위에 있다면, 별에 갈 수 있는 가능성이 생긴다.
다음으로는 가로 이동이 순서대로 "←", "→", "←←"이 주어진다고 가정한다.
세로 이동을 전혀 고려하지 말고 가로 이동만을 고려했을 때,
도착점까지 갈 수 있는 격자는 어디일까?
뒤에서부터 역추적해보면 위 그림과 같다.
도착 지점부터 역추적하는 것이기 때문에
실질적인 진행순서는 "←←", "→", "←""←←", "→", "←"이다.
2번 과정에서 갑자기 노란색의 범위가 커졌다가,
3번 과정에서 하나로 줄어드는 것에 주목해야 한다.
이 의미는 오른쪽으로 한번 움직여 1번의 노란색 범위를 만들려고 할 때,
가능한 경우가 2가지라는 소리이다.
그리고 3번은 왼쪽으로 한번 움직여서는 가장 오른쪽의 세로 기둥은 만들 수 없다.
그래서 그 가능성은 사라지고 하나의 노란색 영역만이 남은 것이다.
이제 가로 이동과 세로 이동을 합쳐보면 아래와 같은 그림이 된다.
이렇게 가로 이동과 세로 이동이 겹치는 범위(빨간색)가 최종적으로 가능한 범위가 된다.
빨간색 격자에서 위의 움직임을 그대로 적용해 보면, 도착점에 도착하는 것을 확인할 수 있다.
이렇게 이 문제는 주어진 움직임 정보를 가로와 세로로 나누어서,
역순으로 추적하는 것이 핵심인 문제이다.
가능한 범위를 구하는 과정
이론적인 과정은 위와 같은데.. 이걸 알고리즘으로 옮기는 걸 어떻게 해야 할지가 참 골치 아팠다.
그래서 인터넷의 도움을 받아서 깔끔하게 정리해 주신 분에 블로그를 많이 참고했다.
https://stritegdc.tistory.com/311
[pro] 프로그래머스 level3 87391 공 이동 시뮬레이션 (Java) - 시뮬레이션
[문제] https://school.programmers.co.kr/learn/courses/30/lessons/87391 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이
stritegdc.tistory.com
이분이 설명도 깔끔하게 해 주시고, 코드도 깔끔해서 많은 도움이 됐다.
이는 텍스트로 나타내기에는 굉장히 애매한 것 같아서, 그림을 첨부하여 설명하겠다.
주어진 방향과 도착점은 위웨서 가정했던 것과 동일하게 진행하겠다.
("←←", "→", "←", "↑↑")
우선 2차원 좌표 p1(x1, y1), p2(x2, y2)를 도착 좌표로 초기화한다.
이 두 좌표는 도착점까지 도달 가능한 출발지점의 범위를 지정하기 위한 것이다.
p1에서 x1은 위쪽 벽의 충돌을, y1은 왼쪽 벽과의 충돌을 검사할 것이고,
p2에서 x2는 아래쪽 벽과 충돌을, y2는 오른쪽 벽과의 충돌을 검사한다.
여기서 벽과의 충돌을 검사하는 것이 굉장히 중요하다.
왜냐하면 벽과 충돌하는 상태라면 그 방향으로 더 이상 나아갈 수 없기 때문이다.
이에 관해서는 시뮬레이션을 더 돌려보면서 이야기하겠다.
일단 p1와 p2를 검사했을 때, 모두 벽에 붙어있는 것이 없다면 두 점 다 시키는 대로 이동시켜 준다.
물론 역순으로 이동시키는 것이기 때문에, 입력했던 방향 반대로 이동해야 한다.
그럼 위 그림같이 나오게 된다.
핵심이 부분이다.
오른쪽 방향 입력이 들어왔기 때문에 왼쪽으로 한번 움직여야 한다.
그런데 현재 오른쪽 벽과의 충돌을 검사하는 p2의 y2가 오른쪽 벽에 붙어있다.
이럴 때는 p2, 정확히는 y2를 움직이지 않고, p1만 움직인다.
따라서 위와 같은 그림이 나오게 된다.
이 상태에서 계속해보자.
p2는 오른쪽으로 가야 하지만, 더 이상 오른쪽으로 갈 수 없기 때문에 제자리이다.
그래서 p1만 이동해서 위와 같은 그림이 나오게 된다.
모든 이동을 완료했는데,
p1과 p2사이의 거리를 구하면 딱 저 부분만 가능하므로 1이 답이 된다.
이것만으론 긴가민가하기 때문에 입출력 예 2를 가지고 다시 한번 해보자.
이번엔 빠르게 과정과 결과만 보여주겠다.
최종적으로 p1(0,1), p2(1,1)이기 때문에 넓이(범위)를 구해보면,
(1-0+1)*(1-1+1) = 2가 나오게 된다.
예시와 비교해 봤을 때 정확히 일치하는 것을 확인할 수 있다.
실수하기 쉬운 부분
테스트케이스 33, 34
역추적하는 과정에서 배열 밖으로 나가는 것을 처리해주지 않을 경우,
테스트케이스 33,34번이 틀릴 것이다.
이 이유는 말 그대로 역추적하는 과정에서 배열 밖으로 나갈 수도 있기 때문이다.
이 점이 실수하기 쉽기 때문에 나중에 코드에서 주석으로 알려주겠지만,
반복문 내에서도 매번 체크를 해줘야 한다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
long long solution(int n, int m, int x, int y, vector<vector<int>> queries) {
long long x1 = x, y1 = y;
long long x2 = x, y2 = y;
for(int i = queries.size()-1; i >= 0; i--){
int dir = queries[i][0];
int size = queries[i][1];
/*
* 역추적하기 위해서 밑에 주석을 역추적하는 방향으로 적었음
* 예를 들어 0번은 원래 왼쪽으로 움직이는 건데, 오른쪽이라고 적었음
*/
switch(dir){
// 오른쪽
case 0:
if(y1 != 0) y1 += size;
y2 = min(y2+size,(long long)m-1);
if(y1 > m-1) return 0; // 범위 밖으로 나가는지 체크
break;
// 왼쪽
case 1:
if(y2 != m-1) y2 -= size;
y1 = max(y1-size,0ll);
if(y2 < 0) return 0;
break;
// 아래
case 2:
if(x1 != 0) x1 += size;
x2 = min(x2+size,(long long)n-1);
if(x1 > n-1) return 0;
break;
// 위
case 3:
if(x2 != n-1) x2 -= size;
x1 = max(x1-size,0ll);
if(x2 < 0) return 0;
break;
}
}
return (x2-x1+1)*(y2-y1+1); // 최종 계산
}
Java 구현 코드
↓
class Solution {
public long solution(int n, int m, int x, int y, int[][] queries) {
long x1 = x, y1 = y;
long x2 = x, y2 = y;
for(int i = queries.length-1; i >= 0; i--){
int dir = queries[i][0];
int size = queries[i][1];
/*
* 역추적하기 위해서 밑에 주석을 역추적하는 방향으로 적었음
* 예를 들어 0번은 원래 왼쪽으로 움직이는 건데, 오른쪽이라고 적었음
*/
switch(dir){
// 오른쪽
case 0:
if(y1 != 0) y1 += size;
y2 = Math.min(y2+size,m-1);
if(y1 > m-1) return 0; // 범위 밖으로 나가는지 체크
break;
// 왼쪽
case 1:
if(y2 != m-1) y2 -= size;
y1 = Math.max(y1-size,0);
if(y2 < 0) return 0;
break;
// 아래
case 2:
if(x1 != 0) x1 += size;
x2 = Math.min(x2+size,n-1);
if(x1 > n-1) return 0;
break;
// 위
case 3:
if(x2 != n-1) x2 -= size;
x1 = Math.max(x1-size,0);
if(x2 < 0) return 0;
break;
}
}
return (x2-x1+1)*(y2-y1+1); // 최종 계산
}
}
시행착오
센스가 필요했던 문제 같다.. 혼자서는 해결 못했을 문제였을 것이다..
포스팅을 하면서도 어떻게 하면 쉽게 설명할 수 있을지 고민을 많이 했다..
논리적인 사고와 센스가 필요했던 문제인 거 같은데.. 이런 문제가 나오면 풀기 어려울 것 같다.
센스를 기를 수 있는 방법은 없을까?
그냥 열심히 풀자.
센스 없이도 맞출 수 있는 문제를 그냥 다 맞히자는 생각으로 살자.
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me