다음 미로 찾기 문제를 스택(stack)을 이용하여 해결하고자 한다. 출발점에서 시작하여 도착점까지 가기 위해 필요한 push 연산 횟수와 pop 연산 횟수는? (단, 출발점, 도착점 좌표에 대해서는 push 연산 횟수에서 제외한다)
○ 출발점은 (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
선지를 골라 바로 채점해 보세요.
정답 ③
출처: 인사혁신처 공개 기출(공공데이터포털, 이용허락 제한 없음)