문제
[ 입력 조건 ]
미로의 세로길이(행), 가로길이(열) 을 각각 정수로 입력받고
입력받은 미로의 크기만큼(행 * 열) '0'과 '1'로 이루어진 문자값들을 입력 받는다5 10 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0[ 출력 조건 ]
'0'은 지나갈 수 있는 길, '1'은 지나갈 수 없는 벽이라고 가정.
시작 위치는 좌측 상단의 '0', 출구 위치는 우측 하단의 '0' 이라고 가정.
이동은 상, 하, 좌, 우 4방향에 대각선까지 총 8방향으로 이동할 수 있다고 가정.
이때, 시작 위치부터 출구 위치까지의 경로를 출력(0, 0) -> (1, 1) -> (0, 2) -> (0, 3) -> (1, 4) -> (0, 5) -> (1, 6) -> (1, 7) -> (0, 8) -> (0, 9) -> (1, 8) -> (2, 7) -> (3, 8) -> (4, 9)
💡어디서 부터 시작해야할까?
입력을 받고 무사히 2차원 배열의 미로를 저장했으면 그 다음에 뭘 하면 될까? 생각을 한번 해보자🙉
우선, "위치"를 2차원 배열의 각 인덱스값으로 표현할 수 있을것이다. 적당한 이름으로 정수형 변수 2개 선언해 주자
그럼 "위치의 변화"는 어떻게 정해줄 수 있을까? 문제에선 현재 위치에서 8방향으로 이동 가능하다고 서술하고 있다. 현재 인덱스에 주변 8위치의 상태가 0이라면 그쪽으로 위치가 변화 가능하다는 뜻인 것이다. 2차원 배열 상에서 8방향이라면 인덱스 값이 어떻게 변해야 하는지 생각해보자.
그리고 이 "위치의 변화"를 배열이나 큐 혹은 스택에 담아 저장해 나간다면 그것이 바로 "이동경로"가 될 것이다. 이동경로를 저장하기 위한 적당한 자료구조를 결정하려면 어떤 알고리즘으로 문제를 해결할 것인지가 결정되어야한다. 어떻게 하면 현재 위치로부터 출구의 위치까지 위치를 변화시킬 수 있을까!
💡탐색하고 이동하고 탐색하고 이동하고 실패하면 되돌아오고..
경로 저장 -> 정답검사 -> 주변탐색 -> 경로 저장 -> 정답검사 -> 주변탐색...
이런식으로 생각해 볼 수 있다.
그런데 이런식으로 쭉 가다가 만약 더이상 주변에 새롭게 갈수 있는 길이 없다면 어떻게할까?
길이 막혀있는 지금의 위치를 선택한 이전의 위치로 다시 되돌아 올 수 있어야 할 것이다. 그렇게 뒤로 한칸 다시 돌아간뒤, 가보지 않았던 새로운 위치로 가봐야 할것이다.
그렇게 하기 위해선 가본 길과 가보지 않은 길을 구분하기 위해 지나간 길들을 '0'이 아닌 다른 값으로 바꿔줘야 할 필요가 생긴다. (대충 '0'에서 '*'로 바꾼다고 치자)
그럼 다시 처음부터 생각해보자
시작 위치 (0,0)을 경로에 넣고 미로의 (0,0)인덱스의 값을 '*'로 바꾸고 (0,0) 주변에 내가 갈 수 있는 위치를 탐색한다.
그중 찾아낸 위치(값이 '0'인 인덱스)를 경로에 넣고 그 위치를 '*'로 바꾸고 그 위치 주변을 탐색하길 반복할 것이다.
그러다가 더이상 주변에 갈수있는 길이 없으면 경로에 넣었던 위치중 가장 최근의 위치를 삭제하여 바로 전 상황으로 되돌아간 뒤 주변을 탐색할 것이다.
경로를 저장할때 스택을 사용하는 이유가 바로 여기서 나온다.
가장 최근에 들어간 경로가 pop되어 나올 수 있기 때문
만약 아예 답이 없는 미로일 경우를 생각해보면 갈 수 있는 곳 다 가본뒤 뒤로 뒤로 뒤로 이동하다 결국은 경로에 저장된 위치가 더이상 존재하지 않는 상태가 될 것이다.
답이 있는 미로라면 정답 검사에서 걸려서 경로를 출력해주는 메소드로 가게 될 것이다.
따라서 이 문제에서 이전 경로로 되돌아가는 과정을 쉽게 만들어주는게 바로 stack이 하는 역할 이라고 할 수 있고, 한번 정한 위치에서 실패해서 되돌아 올때까지 쭉 진행한다는 점에서 DFS알고리즘 이라고 할 수 있다.
반대로 말해서, 실패해서 되돌아 올때까지 쭉 진행하는 DFS알고리즘 방식으로 문제를 풀이할 것으로 아이디어가 떠올랐다면, 경로 저장의 자료구조를 Stack으로 결정해야한다는 뜻이 될것이고, 이것이 오늘의 알고리즘 문제풀이 생각방식의 시사점이라고 정리 할 수 있을 것같다.
그럼 이만!
🐒 학교 자료구조 수업 내용을 복습하며 나름 스스로 정리해본 내용입니다!
이상한 부분이나 오류가 있을시 알려주시면 감사하겠습니다! 🐒