백준 17510 : Bigger Sokoban 40k

https://www.acmicpc.net/problem/17510

17510번: Bigger Sokoban 40k

현재 이 문제의 답은 인터넷 상에 나와있지 않다.

는 사실이 아니고, 한 달 전에 심심풀이 겸 찾아봤는데, 놀랍게도 있다..

하지만 여기서 그걸 찾는 방법은 서술하지 않을 것이고, 어떻게 풀어야 아래 사진와 같은걸 볼 수 있는지 설명할 것이다.

 

이 문제는 2019 NYPC 돌밀기가 생각되는 문제이다.

돌밀기를 해본 사람이라면 뒤로 갈수록 암걸리는 맵에 담이 걸려 포기한 적이 있을 것이다.

그런데 이번에는 우리가 그 맵을 만들어야 하는데, 어떻게 하면 최대한 암걸리게 맵을 만들 수 있을까?

 

아쉽게도 여기서 답을 공개할 수는 없으나, 떡밥은 주고 가겠다.

 

여러가지 방법이 있겠지만, 이 방법이 제일 먼저 생각나서 이 방법으로 했다.

올라가거나 내려가면서 계속 왼쪽 오른쪽 왔다리갔다리 하면서 이동횟수를 버는 방식이다.

또한 플레이어가 상자를 다음 절차로 옮길 때, 엄청 돌아가야지 움직일 수 있는 구조를 만들어야 한다.

그러기 위해서는, 다음 층으로 진입하는 통로를 최대한 좁게 만들고,

상자를 다음 층으로 완전히 옮기려면 상자를 기준으로 플레이어의 반대쪽에서 밀어야하는 구조를 만들어야 한다.

이런 식이다. 상자의 한쪽에만 있으면 상자를 목적지까지 옮길 수 없는 구조를 만들어서

플레이어가 무조건 상자의 반대쪽에 가게 만들어야 한다. 이 때, 반대쪽에 가는 길을 엄청 길게 만들어 이동 횟수를 번다.

 

 

 

그럼 이제 구체적인 계획을 세워보자.

위와 같이 두 층 사이에는 몇 칸이 있어야 적당할까?

 

2칸은 너무 꽉 껴서 상자를 위아래로 움직일 수가 없게 되고

4칸은 너무 넓어서 공간 활용을 위해서 더 적은 칸만 썼으면 좋겠으니

3칸이 적당하다고 생각했다.

 

그러면 왼쪽 벽부터 오른쪽 벽까지의 간격은 몇 칸이 적당할까?

그건 아래 그림을 보자.

위 사진은 제출 코드의 일부분이다.

위 맵에서 각 층에서 반대쪽으로 돌아가야만 하는 횟수는 총 3번이다.

이와 같은 형태를 위로 올라가며 계속 반복한다.

그러다가 위로 더 이상 못 올라가게 되면 오른쪽으로 간다음 다시 내려온다. 이걸 반복한다. 그럼 선이 된다.

그리고 이걸 오른쪽으로도 이제 더 이상 갈 수 없을 때까지 반복한다. 그리고 그 마지막 장소를 도착지로 둔다.

그 다음 마지막으로 도착지에서 출발지로 가는 길을 만든다.

완성하면 대략 이런 경로가 나온다.

계속 꼬불꼬불하게 가는 와중에 반대로 가느라고 맵을 완전히 한 번 돌아야 하게 만들었다.

 

 

설명히 상당히 추상적이였지만, 잘 생각해보면 어렵지 않게 맵을 완성할 수 있다.

참고로 이 문제를 머리로 맞추는 것보다 구글링을 열심히 해서 답을 알아내는 것이 더 어려우니 그건 지양하자.