SLENDER ANKLES's 개발블로그

우선 문제에서 이상하게 헷갈렸던 점이 

1) 장애물을 만나거나 길을 벗어날 경우 90도의 방향을 전환 할 수 있다. 

=> 질답게시판을 이용해 물어봤더니 장애물을 만났을 때 항상 시계 방향을 회전해야 되는 것은 아니다. 

예를 들어 북쪽으로 진행하다가 벽을 만나면 서쪽으로, 또는 동쪽으로 방향을 바꿀 수 있다는 것이다. 

문제를 읽고 문제에서 하라고 하지도 않은 제약사항을 만들어 고민한 케이스 였다. 

2) 최장 경로가 그림의 것이라는 말은 없었는데, 마음대로 판단해버렸다. 

=> 문제에서는 "아래 그림은 샐리가 움직인 한 경로이다."

라고 나와있는데 잘 못 판단해버렸다. 

코딩 실력이 문제가 아니라 읽기 능력이 저조하여 문제를 이해하지 못한 것이다.

풀었다.

더블릿의 예제 테스트케이스가 나오지 않았다면 푸는 데 정말 많은 시간이 걸렸을 것이다.

내가 짠 소스코드는 불완전하여 예외를 처리하는데 많은 시간이 걸렸다. 

대략적인 핵심적인 내용을 정리해보기 전에 문제의 내용에 대해 간략히 정리해보자면

문제정리)

- 첫 출발은 1, 1에서 시작했다.

- 첫 출발점에서는 동쪽으로, 남쪽으로만 출발한다.

- 장애물 또는 벽을 만났을 때에는 진행중이던 방향의 90도로 양방향으로 꺾어서 진행해야 한다. 

- 방향에 따라 진행 중에 내가 지나왔던 꼬리(내가 현재 진행 경로 중 방문점)을 만나면 진행을 중지해야 한다. 

풀이정리)

- 입력은 숫자 형태로 주지 않는 불친절한 문제였지만 하나는 캐릭터로 받고 하나는 int로 받으면 입력을 받는데는 문제가 없다. 

- 처음 (1,1)지점에서 동쪽으로 한 번 dfs수행, 남쪽으로 한 번 dfs를 수행한다. 

- dfs를 수행하면서 현재까지의 length를 재주면서 전역변수로 선언된 최대값을 갱신해나갔다.

- 다음 진행방향이 벽이 아니고 계속 진행 할 수 있는 상태에서는 다음 x인자, y인자, 방향, 길이를 인자로 한 dfs 재귀 호출을 수행했다.

다음 진행 방향이 벽인 경우에는 현재의 진행방향에 맞추어서 4가지의 if문을 통해 나아갈 수 있는 방향과 x인자, y인자를 설정해놓고 재귀식을 호출했다. 

- 기본적으로 많이 사용하는 dfs에서는 함수의 최 상단에 visited를 통해 방문관리를 하게 되는데, 이 문제에서는 탐색을 할 때 visited도 필요했으며, 탐색을 마쳤을 때는 visited를 다시 거두어들이는 소스코드가 필요했다. 

그래서 탐색을 종료해야 할 때(꼬리를 만난 시점)와, 함수의 실행부분을 모두 마친 후에 방문 여부를 거두어 들였다(visited[x][y] = false로 거두어들였다.).

dfs를 수행하는 원리와 구조와 진행상황을 좀 정확히 파악 할 수 있어야지만 이 문제를 푸는 데 수월 할 수 있었다고 생각한다. 다시 한 번 문제를 풀어 볼 필요가 있을 것 같다. 

- 우선 2를 제외한 모든 짝수들은 소수가 아니다라는 점

- 만약 N이 합성수라면 N = a * b형태이므로(a > 1 && b > 1), a와 b 둘 중 하나는 sqrt(N)보다 작거나 같음을 알 수 있다.

그러므로 N을 2부터 sqrt(N)까지 나눠보아 나누어지지 않으면 N은 소수가 된다. 

다음은 2부터 N까지 소수를 구하여 prime이라는 배열에 반영하는 코드의 핵심 함수이다.

간단하게 풀 수 있다. 

어느 한 점(x, y)에서 가장 먼 거리는 이 미로의 가장 끝이고(target_x, target_y) 

그 가장 끝 점(target_x, target_y) 에서 가장 먼 거리는 이 미로에서 가장 긴 거리(max_length)가 된다. 

bfs 2번으로 바로 답을 구할 수 있는 문제

PREORDER로 주어진 트리 정보를 이용해

POSTORDER를 출력하는 문제였다. 

노드의 제한은 20개 였다. 

노드의 자식이 없는 경우에 -1을 제공하는 친절한 문제였다. 

처음에는 -1이라는 정보를 이용해 완전이진트리를 구조화하는 트리배열을 만들어도 될까 고민했다. 

(2*N + 1, 2*N + 2)

노드 최대 개수는 20개였으므로 최악의 테스트케이스에서 2의 21승의 노드 배열이 필요했다. 

비주얼스튜디오 환경에서 배열을 100만개 이상 전역으로 선언하는 것은 아무 문제가 없었고, 실제로 어느 테스트케이스에서도 100만개 이상의 순회를 할 필요는 절대 없다고 판단했다. 일렬로 쭉 늘어뜨린 트리의 형태여도 재귀적으로 42번정도만 수행하면 된다. 

그래서 입력 받은 PREORDER정보를 완전이진트리 배열로 만들어주었다. 

테스트케이스에서 

5 3 11 7 -1 -1 2 -1 -1 -1 8 13 -1 -1 4 -1 1 -1 -1

이면 

완전이진트리배열

node[32] = 

5, 3, 8, 11, -1, 13, 4, 7, 2, 0, 0, -1, -1, -1, 1, -1, -1, -1, -1, ......

이런식으로 만들어진다. 

그 다음에는 완전이진트리배열을 이용해 재귀적으로 postorder를 사용해주면 된다. 

dfs의 진입점이 몇 번 나오냐를 판별하는 문제이다. 루프를 돌면서 dfs를 수행하면서 방문 기록을 갱신해준다. 

그러면 2차원 배열을 순회하면서 뭉터기 뭉터기를 판별 할 수 있게 된다. 

안전영역과 비슷하다고 할 수 있겠다.

1번의 실패를 했는데 그 것은 테스트케이스가 배열의 시작을 0,0으로 나와있다. 

4방향 검사를 원할히 하기 위해서 1,1부터 입력을 받고 있으므로 

주어진 테스트케이스에 x+1, y+1을 해주면 된다.