SW Expert Academy 의 1226번 - 미로1 문제입니다. 16x16의 인풋으로 주어지는 미로 데이터에서 도착점까지 갈 수 있는지 여부를 판단해 출력합니다.
문제 조건
Input첫 줄에는 테스트 케이스 번호, 그 다음 줄에는 16x16 미로 데이터가 주어진다. Output2에서 3까지 갈 수 있는 경로가 존재하면 1, 없으면 0을 출력한다. 생각한 아이디어우선 16x16 데이터를 2차원 배열에 담은 뒤, 시작 위치를 행, 열 번호값으로 담아두었습니다. 그런 다음 왼쪽, 오른쪽, 위, 아래 중 갈 수 있는 방향(즉, 0이 있는 곳)으로 위치를 옮기되, 또한 길을 따라 가다가 벽에 막혀서 되돌아와야 할 경우를 대비하여, 이 때 좌표쌍은 C++의 STL에서 데이터 쌍을 표현할 때 사용하는 pair 클래스를 사용했습니다. stack은 가장 최근에 넣은 것이 제일 위에 있으므로, 꺼낼 때도 그 최신 데이터가 꺼내집니다. 그러므로 여기서는 stack이 더 어울린다고 판단했습니다. [1] 갈 수 있는 길을 찾았을 때는, 현재 위치를 스택에 저장한 뒤 다음으로 이동합니다. (항상 방문한 위치에는 8이라고 표기한다고 생각하면 됩니다.) [2] 벽에 막혔을 경우, 다시 되돌아가야 하므로 stack에 저장되어 있던 데이터들을 활용합니다. 스택의 top에 저장되어 있던 좌표로 되돌아가며, top에 있는 데이터는 pop합니다. [3] 지나온 경로를 돌아오는 와중에도 매번 상,하,좌,우를 보고 갈 수 있는 방향을 파악 중입니다. 갈 수 있는 방향을 찾았을 경우, 아까처럼 현재 위치를 stack에 push하고, 갈 수 있는 방향으로 갑니다. [-] 만약 갈 수 있는 모든 경로를 갔는데 3을 만나지 못하고 처음 위치로 되돌아왔다면 stack은 빈 상태였을 것입니다. 이 때 미로 탐색 실패를 반환하면 됩니다. 소스코드
c++의 STL에서 제공하는 stack, pair 자료구조를 이용하였습니다. ※ c++에서 cin으로 입력받기 전에, cin.tie(NULL); 을 선언하고 나서 입력받으면 실행시간이 줄어드는 효과를 얻을 수 있습니다. ※ 그러나 위와 같은 방법은 주의해서 사용하여야 한다고 합니다. 실무에서는 사용하지 말고, 싱글 쓰레드 환경에서만 사용하도록 합니다. 또한 scanf, printf와 함께 사용하면 안 됩니다. [출처 링크 : (클릭)] |