다음 미로 찾기 문제를 스택(stack)을 이용하여 해결하고자 한다. … | [7급 국가직 자료구조론] 23년 1회차 기출문제 상세 페이지

다음 미로 찾기 문제를 스택(stack)을 이용하여 해결하고자 한다. 출발점에서 시작하여 도착점까지 가기 위해 필요한 push 연산 횟수와 pop 연산 횟수는? (단, 출발점, 도착점 좌표에 대해서는 push 연산 횟수에서 제외한다)
0
1
0
1
1
0
1
0
0
0
1
1
1
0
0
0
출발 → (0, 0) 칸, (3, 3) 칸 → 도착
방위: 위쪽 N, 아래쪽 S, 왼쪽 W, 오른쪽 E
○ 출발점은 (0, 0), 도착점은 (3, 3)이다.
○ 출발점에서 현재 좌표까지 이동 경로는 push 연산으로 현재 좌표를 스택에 저장하고, 직전 좌표로 돌아가는 경로는 pop 연산으로 현재 좌표를 스택에서 삭제하는 방법으로 만들어진다.
○ 미로의 크기는 4 × 4 2차원 배열로 구성되었고, 1은 장벽, 0은 통과할 수 있는 길이다. 4 × 4 2차원 배열 외부는 모두 장벽으로 간주하여 이 배열을 벗어날 수 없다고 가정한다.
○ 각 좌표에서 이전에 이동했던 좌표를 제외하고, N(북)에서 NE(북동), E(동), SE(남동), S(남), SW(남서), W(서), NW(북서) 순서로 검색하여 가장 먼저 찾은 이동 가능한 좌표로 이동한다. 주위 좌표가 모두 벽이거나 방문했던 곳일 경우 직전 좌표로 돌아간다.
push pop

3 0

4 0

5 2

6 2

규칙대로 탐색하면 push는 5회, pop은 2회 필요하다.
(0, 0)에서 SE (1, 1) push → NE (0, 2) push → SE (1, 3) push. (1, 3)은 주위가 모두 벽이거나 방문한 곳이라 pop하고, (0, 2)도 더 갈 곳이 없어 pop한다.
(1, 1)로 돌아와 남은 방향을 검색하면 S (2, 1) push → SE (3, 2) push → E (3, 3) 도착(도착점은 push 제외)이다.
push 3회·pop 0회: (1, 3)·(0, 2)의 막다른 길에서 되돌아오는 pop 2회가 반드시 생기므로 pop이 0일 수 없다.
push 4회·pop 0회: 마찬가지로 되돌아오는 과정이 빠져 있고, push도 실제 5회보다 적다.
push 6회·pop 2회: pop은 맞지만 push 대상이 아닌 도착점 (3, 3)까지 센 값이다.