05 Apr 2024

[Java] 코드트리: 메이즈 러너

M명의 참가자가 미로 탈출하기 게임에 참가하였습니다.

미로의 구성은 다음과 같습니다.

1. 미로는 N×N 크기의 격자입니다. 각 위치는 (r,c)의 형태로 표현되며, 아래로 갈수록 r이 증가, 오른쪽으로 갈수록 c가 증가합니다. 좌상단은 (1,1)입니다.
2. 미로의 각 칸은 다음 3가지 중 하나의 상태를 갖습니다.
   1. 빈 칸
      • 참가자가 이동 가능한 칸입니다.
   2. 벽
      • 참가자가 이동할 수 없는 칸입니다.
      • 1이상 9이하의 내구도를 갖고 있습니다.
      • 회전할 때, 내구도가 1씩 깎입니다.
      • 내구도가 0이 되면, 빈 칸으로 변경됩니다.
   3. 출구
      • 참가자가 해당 칸에 도달하면, 즉시 탈출합니다.

1초마다 모든 참가자는 한 칸씩 움직입니다. 움직이는 조건은 다음과 같습니다.

• 두 위치 (x1,y1), (x2,y2)의 최단거리는 ∣x1−x2∣+∣y1−y2∣로 정의됩니다.
• 모든 참가자는 동시에 움직입니다.
• 상하좌우로 움직일 수 있으며, 벽이 없는 곳으로 이동할 수 있습니다.
• 움직인 칸은 현재 머물러 있던 칸보다 출구까지의 최단 거리가 가까워야 합니다.
• 움직일 수 있는 칸이 2개 이상이라면, 상하로 움직이는 것을 우선시합니다.
• 참가가가 움직일 수 없는 상황이라면, 움직이지 않습니다.
• 한 칸에 2명 이상의 참가자가 있을 수 있습니다.

모든 참가자가 이동을 끝냈으면, 다음 조건에 의해 미로가 회전합니다.

• 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형을 잡습니다.
• 가장 작은 크기를 갖는 정사각형이 2개 이상이라면, 좌상단 r 좌표가 작은 것이 우선되고, 그래도 같으면 c 좌표가 작은 것이 우선됩니다.
• 선택된 정사각형은 시계방향으로 90도 회전하며, 회전된 벽은 내구도가 1씩 깎입니다.

K초 동안 위의 과정을 계속 반복됩니다. 만약 K초 전에 모든 참가자가 탈출에 성공한다면, 게임이 끝납니다. 게임이 끝났을 때, 모든 참가자들의 이동 거리 합과 출구 좌표를 출력하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에 N, M, K가 공백을 사이에 두고 주어집니다.

다음 N개의 줄에 걸쳐서 N×N 크기의 미로에 대한 정보가 주어집니다.

• 0이라면, 빈 칸을 의미합니다.
• 1이상 9이하의 값을 갖는다면, 벽을 의미하며, 해당 값은 내구도를 뜻합니다.

다음 M개의 줄에 걸쳐서 참가자의 좌표가 주어집니다. 모든 참가자는 초기에 빈 칸에만 존재합니다.

다음 줄에 출구의 좌표가 주어집니다. 출구는 빈 칸에만 주어집니다.

• N: 미로의 크기 (4≤N≤10)
• M: 참가자 수 (1≤M≤10)
• K: 게임 시간 (1≤K≤100)

출력 형식

게임 시작 후 K초가 지났거나, 모든 참가자가 미로를 탈출했을 때, 모든 참가자들의 이동 거리 합과 출구 좌표를 출력합니다.

풀이 방법

배열 돌리기 + 복잡한 구현 문제

생각해봐야 하는 점

참가자가 이동할 때

1. 참가자는 동시에 움직이며 최단 거리가 가까워야만 움직인다.
2. 같은 공간에 두 명 이상의 참가자가 있을 수 있다.

90도 회전할 때

1) 출구와 한 명 이상의 참가자가 포함된 최소 크기의 정사각형 공간을 구하고, 오른쪽으로 90도 회전한다. 이 때, 같은 사이즈의 공간을 여러 개 만들 수 있다면, 최대한 좌측 상단으로 잡는다.

(a) moveHumans 메소드

1. 참가자들의 정보를 담은 리스트를 마지막부터 순회하며 이동할 수 있으면 이동시켰다. 출구랑 만나게 되면 그 동안 이동했던 칸 수를 더해주고 리스트에서 삭제했다.

(b) checkSquareAndRotate 메소드

1. 출구랑 참가자(1명 이상)를 포함하는 최소 정사각형을 만들었다.
   • 참가자 리스트를 순회하면서 출구로부터 떨어진 행과 열을 구한다.
   • 행과 열 중 큰 걸 구한다.(어차피 정사각형을 만들어야 되니 멀리 떨어진 것을 선택해야 한다.)
   • 출구와 가까운 사람 리스트를 만들고 최신화한다.
2. 졍샤갹형 중 최소 R값, C값을 구해야 했기 때문에 (1, 1)부터 정사각형을 탐색하고, 찾으면 break로 빠져나온다.

(c) rotate90 메소드

1. 만들어진 정사각형 내부를 오른쪽 방향으로 90도 회전시킨다.
2. 돌려지는 정사각형 안에 출구 또는 참가자가 있다면 같이 회전시킨다.
   • 한 번 돌아간 참가자/출구가 또 다시 돌아가는 걸 막기 위해 boolean 변수를 만들었다.

게임시간 K가 지난 후에 리스트에 남아있는 참가자들을 결과값에 추가해주면 정답을 도출할 수 있다.

중간에 참가자가 모두 출구로 나갔다면 break문으로 탈출시켜주었다.

걸린 시간: 6시간

풀이 코드

comments powered by Disqus