SLENDER ANKLES's 개발블로그

트리 문제를 만났을 때, 배열을 통해서 구현 할 것인지 아니면 구조체를 통해서 구현해야 하는지에 대해서

항상 고민하게 된다. 

보통 배열을 쓰는 것이 더 직관적이고 습관화가 잘 되어있어서 편하지만 배열을 사용 할 수 없는 경우에는 이러한 습관이 또 독이 되는 것 같다. 

이번 문제는 배열을 써도 문제 없었다. 

노드의 개수는 26개까지 제한이 있었는데, 배열을 완전이진트리 형태로 만들어놓아도 큰 문제는 없었다. 

트리를 입력 받는 부분에서 지금까지와 다른 입력 형식이어서 살짝 고민했지만

인덱스를 관리해주는 배열을 따로 만들어서 풀어나갔다. 이런 부분은 그냥 경험으로 체득하는 것 같다. 

완전 이진트리를 만들어놓고 전위, 중위, 후위 순회하는 것은 별로 어렵지는 않았다.  

구조체를 사용해서 푸는 방법과 배열을 부모를 저장하는 형식으로 만들어내는 방법으로도 한 번 풀어볼 필요가 있을 것 같다. 

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

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

간단하게 풀 수 있다. 

어느 한 점(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을 해주면 된다. 

중요한 부분은

- 치즈로 둘러 싸여 있는 내부의 0인 부분은 바깥 공기가 아니라는 점이다.

- 치즈의 한 면이라도 공기와 접촉되면 한 시간 후에 없어진다.

1) 0,0에서 시작해서 공기에 해당하는 부분을 3(공기영역을 3으로 표기하게끔 해주었음)으로 갱신해주는 dfs를 수행한다.

2) 그리고 공기와 접촉되는 부분의 치즈를 0으로 바꾸어준다. 치즈의 개수를 세어준다.

루프를 수행하는 횟수를 시간과 연결시켜 답을 구한다.

공기와 맞닥뜨린 치즈의 개수를 세면서 전체 치즈의 개수를 세어 갱신하며 마지막 한 시간 전의 남아있는 치즈 개수를 구할 수 있게 유도

* 보물섬 안에서 가장 길이가 긴 육지의 두 공간에 보물이 묻혀있다.

* 보물섬 안에서 반복문을 순회하며 'L', 즉 육지인 곳이 나타나면 거기서부터 bfs를 수행해 가장 거리가 긴 것을 찾았다. 

* 가장 거리가 긴 육지사이의 거리가 결국 보물이 숨겨져 있는 두 육지안의 지점까지의 거리를 의미하니까.

* 4방향 검사가 아니라 대각선까지 고려하는 8방향검사를 수행한다.

* 루프를 돌면서 dfs를 진입하는 개수가 결국 섬의 개수다.

* 각 테스트 케이스마다 섬의 개수를 출력한다.

* 기존의 처음 테스트케이스의 개수가 주어지는 형태가 아니라 입력값이 0, 0이면 끝나게 끔 

하는 부분에서 한 번 틀렸지만 이런문제도 있다 정도로 생각하였음

도저히 제출이 성공하지 않는다.??

- 하루에 한 개씩 밖에 익지않는다는 점을 주의하라. 라는 도움말을 보았다. 

다음에 이 것을 고려해서 다시 한 번 작성해보아야 겠다.

dfs를 돌릴 때 특정 사각형 밖의 영역을 구하는 문제 였다. 

- 문제점은 dfs의 4방향 처리 때 끝에서 바깥부분을 검사할 때 발생했다.

- 예외처리를 거의 날로 한 거 같다.

- 풀기는 풀었지만 제 정신이 아니었다. 

- 바깥 부분을 -1로 다 만들어 놓았다면 이렇게 코드가 난잡해지지 않을 것 같다. 

- 다시 풀어봐야 한다.

- 소트는 버블 소트를 사용한다. 

- stl에서 제공해주는 소트를 사용하여서도 구현해보아야겠다.