[2020 카카오 기출] 블록 이동하기

 

문제: https://programmers.co.kr/learn/courses/30/lessons/60063

---

시뮬레이션 문제입니다.

 

따져줄 게 참 많아보이는 문제입니다만 아래 두 가지에 대해서만 잘 정하고 풀면 됩니다.

 

1. 상태를 어떻게 저장할 지

2. 다음 좌표 탐색을 어떻게 할 지

 

우선 편의를 위해 블록의 2칸 중 한 칸을 HEAD, 다른 한 칸을 TAIL이라고 하겠습니다.

 

우리는 (HEAD_Y, HEAD_X, TAIl_Y, TAIL_X)로 4개의 정보가 필요하지만

이는 (HEAD_Y, HEAD_X, HEAD가 TAIL과 연결되어 있는 방향) 3개 정보로 똑같이 표현할 수 있습니다.

 

그래서 상태를 어떻게 저장하느냐에 대해서는 (HEAD_Y, HEAD_X, Direction)으로 표현하겠습니다.

(bool visited[Direction][HEAD_Y][HEAD_X]에 방문 표시 저장)

---

그 다음은 좌표 탐색을 어떻게 할 것이냐에 대한 것인데요.

 

일반적인 BFS가 Queue.front()에 대해 4방향 탐색을 한다고 하면, 

 

이 문제의 경우는 Queue.front()에 대해 12방향 탐색을 하면 됩니다.

 

첫 번째 4방향 탐색은 HEAD와 TAIL이 원래 연결 상태를 유지하면서 동서남북 4방향 탐색을 하는 경우 (+4)

두 번째 4방향 탐색은 HEAD 위치 기준으로 TAIL이 회전하는 경우 (+4)

세 번째 4방향 탐색은 TAIL 위치 기준으로 HEAD가 회전하는 경우 (+4)

이렇게 총 12개이구요. 당연히 가지치기가 필요합니다.

 

아래 그림은 회전하는 경우를 따질 때 어떻게 코드를 단순화할 것인지 그림으로 표현한 것입니다.

 

 

왼쪽 그림 (Tail 고정, Head가 회전하는 경우)을 기준으로 설명하겠습니다.

왼쪽 그림이 이해가 되신다면 그거 그대로 반대로 적용하면 오른쪽 그림이 됩니다.

 

현재 조사하려고 하는 건, Head가 회전이 가능한지 여부입니다. 

 

<탐색 순서>

1. Tail 기준으로 동서남북 4방향 탐색 => 노란색 좌표를 얻을 수 있습니다.

2. Tail 기준으로 대각선 4방향 탐색 => 초록색과 빨간색 좌표를 얻을 수 있습니다.

3. 여기서 노란색 1, 2번 좌표는 Head가 회전한 후의 좌표이므로 nextHead로 표기하겠습니다.

4. 현재 Head 좌표와 nextHead(노란색 1, 2번) 그리고 Tail 기준 대각선 4방향 탐색을 한 칸을 비교합니다.

5. 빨간 좌표와 초록좌표의 차이는 빨간 좌표는 Head와 nextHead와 모두 인접합니다.

6. 노란색 1, 2번과 인접한 빨간좌표가 벽인지 아닌지 따져줍니다. 

7. 6번의 결과에 따라 노란색 1,2번으로 Head가 이동가능한지 아닌지가 결정됩니다.

 

요약 하자면

1. Tail 기준 4방향 탐색 => 노란색 좌표를 구한다.

2. Tail 기준 대각선 4방향 탐색 => 빨간색 & 초록색 좌표를 구한다.

3. 빨간색 좌표가 벽 => continue;

4. 빨간색 좌표가 벽 X => 노란색 1,2번 좌표가 nextHead가 되면서 방향이 바뀐다. (nextDirection 생성)

5. visited[nextDirection][TAIL_Y][TAIL_X] 방문표시를 하고 (nextDirection, TAIL_Y, TAIL_X)을 큐에 넣는다.

 

이렇게 구현해놓으면, Head와 Tail이 어떤 상태로 들어오든지 간에 12방향 탐색으로 모든 경우를 따져줄 수 있습니다.

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG60063.java