[Text] 22311번 Maze 6

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

22311번: Maze 6

---

 

22/09/27

 

 

코드를 짜지 않고도 충분히 손으로도 풀 수 있는 문제로, 같은 시리즈의 Maze 9문제와 함께 풀면 더욱 좋은 문제이다.

 

나의 경우는 Maze 9문제를 예전에 풀었었기 때문에 이에 영감을 받아 쉽게 풀 수 있었다.

---

 

문제 접근 방식:

 

 

문제를 해석하자면 다음과 같다.

 

우리의 목적은 "미로의 시작점부터 가장 중심(그 위치까지 도달하는 데에 걸리는 최단 거리가 가장 긴 곳)까지의 거리가 54 이상이 되게끔 미로를 구성하는 것"이다.

 

예시를 들면 다음과 같다. (원래는 입구표시와 중심 표시, 가는 경로 같은 상황을 표시하지 않는다.)

#EX#######
#+#X#C+.##
#+++X#+X.#
#.#++++..#
#.XXXX##.#
##########

미로의 입구를 E, 미로의 중심을 C, 그 칸으로 가지 못하게 끔 벽을 세운 것을 #, 미로의 입구부터 미로의 중심까지의 이동 경로를 +로 표시를 했다.

 

만약 이렇게 미로를 구성했다면, 12가 미로의 입구부터 미로의 중심까지의 거리가 되는 것이다.

 

보면, 미로는 입구가 1개여야 좋다. 왜냐하면 입구가 2개면 그곳으로 가는 경로도 더 늘어나기 때문에, 더 짧은 경로가 생길 여지가 다분하다.

 

나는 어떤식으로 접근했냐면, 맨 처음에는 그냥 수평 혹은 수직 방향으로 구불구불, 마치 뱀처럼 구성을 했었다.

 

하지만, 당연히 이는 최적의 해가 아니다.

 

때문에 접근 방식을 수평 방향이 아닌 대각선 방향으로 구불구불 가는 것처럼 경로를 구성했고, 시행착오 끝에 딱 거리가 54가 되는 경로를 만들 수 있었다.

마치 이런 모양으로 구성했다.

 

텍스트 문제 특성상, 코드는 공개하지 않도록 하겠다.(그게 곧 답이므로)