프로그래머스. 블록 이동하기

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

코딩테스트 연습 - 블록 이동하기

 

처음에 dfs로 접근했는데 시간초과가 나서 bfs로 다시 풀었다.

dfs로 풀어도 시간초과는 안날거라고 예상했는데.. 어쨌든 bfs로 푸는게 나아보여서 bfs로 다시 풀었다.

 

이문제는 골치 아픈게 드론의 좌표가 하나가 아닌 두칸을 차지한다는점과 회전을 한다는점이다.

먼저 두칸을 차지하는 문제는 좌표를 하나를 기준으로 삼고, 그 좌표 기준의 방향을 기억해서 해결했다. 

예를들어 (0,0)의 동쪽이면 (0,0)과 (0,1)이 드론의 위치다.

 

회전을 할때는 그냥 모든 경우의 수를 하드코딩으로 해결했다.

드론이 좌우로 있을때,

왼쪽부분이 오른쪽 위로 이동할때, 오른쪽 부분이 왼쪽위로 이동할때, 

왼쪽부분이 오른쪽 아래로 이동할때, 오른쪽 부분이 왼쪽 아래로 이동할때 

 

드론이 상하로 있을때,

위쪽부분이 오른쪽 아래로 이동할때, 아래쪽 부분이 위쪽 오른쪽으로 이동할때 

위쪽부분이 왼쪽 아래로 이동할때, 아래쪽 부분이 왼쪽 위로 이동할때 

 

총 8가지 경우가 있다.

 

또한 이런 dfs나 bfs문제는 좌표를 이동하면서 이미 방문한 곳은 더이상 방문하지 않도록 하는 것이 중요한데,

이 문제에서는 그냥 방문 여부를 표시하고 방문 했다고해서 방문하지 않으면 안된다.

드론이 두칸을 차지하고 방향이 있기 때문에 특정 좌표에 이미 방문했어도 다른 방향으로는 방문하지 않았을 가능성이 있기 때문이다.

따라서 이문제는 다음과 같이 방문여부를 3차원 배열로 확인해줘야 한다.

bool mark[110][110][4];

 

mark[0][0][1] = true 라면 (0,0)에 드론이 오른쪽 방향을 향했을때 방문했다는 뜻이다.

(0:위, 1:오른쪽, 2:아래, 3:왼쪽) 

 

 

제출했는데 64점이 나왔다.

(64/100) 

 

64점이 나온 코드 

 

계속 수정해도 안되서 아예 처음부터 다시 풀어봤다.

방법은 동일하게 풀었는데 node 구조체에 드론이 차지하는 두칸의 좌표 모두 저장하는것이 아닌 

하나의 좌표와 방향을 저장하고, 그 좌표와 방향을 갖고 붙어있는 칸을 계산하도록 했다.

논리는 위의 64점 코드와 똑같은데 이건 통과됐다.

아마 첫 코드는 회전하는 과정의 하드코딩에서 어딘가가 문제가 있는것 같다.