23.04.10 파이썬 코딩 퀴즈#213 공 이동 시뮬레이션(프로그래머스 스쿨)

이번 문제는 공 이동 시뮬레이션 문제이다

처음 nxm 이차원 배열이 주어지며 전달받은 queries를 순서대로 시뮬레이션 했을 때, 목적지 (x,y)에 도달해야 한다.

이 때 (x,y)에 도착가능한 시작점의 개수를 구하는 문제이다.

먼가 설명히 막막해 보인다.

먼저 command 부터 살펴보자.

command 는 0, 1, 2, 3 총 4개이며 각 좌, 우 ,상, 하로 움직임을 명령한다.

dx 는 좌표이며, 이동하는 칸의 개수를 의미한다. 만약 범위를 벗어난 경우라면 이동 가능한 지점까지 이동 후 멈추게 된다.

 

먼저 입출력 예 1번은 보자

command 만 먼저 살펴보면, 2, 0, 1, 0, 2 이다. 상-> 좌 -> 우 -> 좌 -> 상 순서대로 명령을 전달 받는다.

각 명령별로 이동 거리는 다 1 이다.

이를 역순으로 살펴보면 하- > 우 -> 좌 -> 우 -> 하 이다. 즉 범위 제한이 없는 2차원 배열에서 해당 queries 에 의해 (0,0)에 도달하려면 (2,1)에서 시작해야 목표 지점으로 도달 가능하다. 

 

한 가지 더 살펴봐야 할 점은 이동 거리이다.

즉 격자의 크기를 넘어가는 명령에 대해서는 언제나 이동 가능한 마지막 위치값을 가진다.

즉 첫 queries 로 [[0,100],[1,1]] 을 전달 받은 경우 왼쪽으로 100칸 이동 후 오른쪽으로 1 칸을 이동하게 된다.

만약 한 행의 길이가 50 이라면, 모든 위치에서 실행한 결과값은 +1 이 된다. 즉 도달해야 할 위치가 (0,0) 이라고 가정하면 해당 queries로는 목표 좌표에 도달 할 수 없다는 결론이 나온다.

 

다시 입출력 예 1번을 살펴보자.

크기에 제한이 없는 상황이라면 총 6개의 좌표에서 해당 queries 를 활용하여 (0,0)에 도달 가능하다. 그리고 다시 범위가 제한된 2차원 배열에서는 총 4개의 좌표에서 목표지점까지 도달이 가능하다.

 

그리고 위 그림에서 알 수 있듯이 해당 문제는 범위의 설정하여 접근해야 하는 문제이다.

근데 이게 범위를 설정하는게 상당히 어려운 부분이 있다.

위에서 언급했듯이 만약 목표 좌표가 벽에 붙은게 아닌 경우이다.

따라서 전달받은 queries 를 역순으로 탐색하여, 해당 목표지점을 시작으로 탐색할 필요가 있다.

이제 코드를 살펴보자

새로운 변수 xx1,xx2,yy1,yy2는 사각형 범위를 의미하게 되며, 시작은 x,x,y,y 에서 시작한다.

이제 해당 범위를 기준으로 queries를 역순으로 탐색하게 되는데

만약 cmd 가 0 인 경우라면 왼쪽으로 이동 즉, 이전 좌표가 오른쪽에 위치하게 된다.

그리고 여기서 한가지 생각해야 할 부분의 배열의 범위 이다.

만약 yy2 가 열의 끝에까지 도달하게 된다면, yy2값은 열의 끝으로 고정시켜 준다.

그 다음 yy1 값을 살펴봐야 하는데, 한가지 예를 들어 살펴보자

목표 지점이 (1,1) 이고 cmd 로 (0,3)을 전달 받았으며, 배열의 크기는 3x3 이다.

yy2 값은 1에서 3증가한 4가 되어야 하지만, 이는 배열의 크기를 초과하기에  값은 2가 된다.

그리고 yy1 값은 벽에 붙은게 아니기 때문에 move 값만큼 오른쪽으로 이동해야 한다. 따라서 4가 된다.

밑에서 다시 설명하겠지만, 범위가 뒤집히는 경우라면 어떠한 경우에서도 해당 위치로 도달할 수 없기 때문에 0을 반환하게 된다.

 

다시 코드로 돌아와 이번엔 cmd 로 1이 주어질 경우를 보자.

오른쪽으로 이동, 즉 이전 좌표가 왼쪽에 존재한다.

 이 경우에는 yy1 값을 감소 시켜주어야 한다. 그 이유는 위 yy2 값의 증가와 같다.

말이 값의 감소이지, 실제로는 영역의 이동이다.

cmd가 1이고 move 가 2라면 목표 좌표에 도달하기 위해서는 yy1과 yy2 값을 왼쪽으로 두칸 이동시켜 줘야 한다.

이 경우에는 yy1 값이 벽에 고정되어도 상관은 없지만, yy2 값이 벽에 고정이 아니라면 move 값만큼 왼쪽 (음수)으로 이동시켜 줘야 한다. 

cmd가 2나 3이 들어온 경우도 동일한 방법으로 좌표를 이동시켜 주면 된다.

그리고 위에서 한번 언급했듯이 잘못된 좌표값 (각 범위가 뒤집힌 경우)라면 어떠한 경우에도 해당 위치로 도달이 불가능 하기에 현재 answer값 0을 반환하면 된다.

그리고 해당 queries를 다 실행한 이후 각 좌표값을 기준으로 넓이를 계산하여 answer에 넣어주면 된다.

해당 문제는 코딩 실력보다, 논리적 접근법이 중요한 문제이다.

공을 해당 위치를 기준으로 다시 역순으로 탐색할 때, 어떤 범위의 값들이 해당 위치에 도달할 지 판단해야 한다.