[백준 16933] 벽 부수고 이동하기 3 - 불꽃카리스마진호우!^^

뚝~딱~뚝~딱

16933번: 벽 부수고 이동하기 3 (acmicpc.net)

16933번: 벽 부수고 이동하기 3

[백준 16933] 벽 부수고 이동하기 3 (gold 1)

위 문제는 벽 부수고 이동하기 1, 2를 푼 이후에 풀어보는 것을 추천합니다.
벽뿌이 1, 2에서 새로운 요소가 추가된 문제들이기 때문입니다.

벽뿌이 3은 벽뿌이 1, 2에서 '가만히 있을 수 있는' 기능과, 낮과 밤의 개념이 추가되었습니다.
위 두가지 기능을 어떻게 구현하였는지를 중점으로 설명하겠습니다.

일단, '가만히 있을 수 있는' 기능의 구현은 <코드 1>과 같이 해주었다.

 평소 위, 아래, 오른쪽, 왼쪽을 탐색하는 그래프 문제에서, <코드 2>와 같이 배열을 만들어준 다음, for문을 이용해 4방향을 모두 접근해주었습니다. 

 이에 착안하여 만든 것이 <코드 1>과 같은 배열입니다. 이런 식으로 구현해주면 5번째 원소들을 통해 쉽게 가만히 있는 경우를 표현할 수 있습니다. 또한, 가만히 있는 경우를 가장 뒤에 배치해준 데에도 이유가 있습니다. 배열을 몇 번째 원소까지 탐색할지 정해주는것 만으로 가만히 있는 기능을 손쉽게 넣었다 뺐다 할 수 있게 해주었다. 배열의 4번째 원소까지 탐색하게 하면 가만히 있는 기능이 없는 것이고, 5번째 원소까지 탐색하게 하면 가만히 있는 기능이 추가되는 것이죠.

 단, 그래프 탐색 과정에서 자기 위치를 한번 더 탐색하는 일은 매우 위험할 수 있는 일이니 조심해야합니다. 왜냐하면  가만히 있는다는 것은 사실 한번 탐색한 곳을 또 탐색하도록 허락해주는 것이기 때문입니다. 원래 기존의 그래프 탐색에서는 한번 방문한 노드는 다시 방문하지 않는 것이 보통입니다. 왜냐하면 한번 방문했던 곳을 또 방문해주도록 허락해주면, 그래프를 무한하게 탐색하거나, 전혀 영양가없는 탐색을 계속 반복할 수도 있습니다. 이는 엄청난 메모리, 시간 낭비를 일으킬 수 있습니다. 이 문제에 대한 해결은 후술하겠습니다.

 

 다음으로, 낮과 밤의 기능을 구현하겠습니다. 이 문제는 낮이냐 밤이냐에 따라서 탐색 자체가 달라집니다. 벽뿌이 3의 세상에서는 낮과 밤이 존재합니다. 낮에 탐색을 마치면 밤이 되고, 밤에 탐색하면 낮이됩니다. 낮에는 최대 K개까지 벽을 부술 수 있고, 밤에는 벽을 부술 수 없습니다. 낮과 밤에 따라 다른 그래프 탐색을 구현해주기 위해 저는 bfs 함수와 그에 필요한 queue를 2개씩 만들어주었습니다. bfs함수를 하나만 만들고 불리안을 이용하거나 여러 방법을 통해 낮인지 밤인지 확인하는 방법도 있겠지만, 그 구현이 매우 번거로울 것 같았고, 메모리나 시간제한에 문제가 없을 것으로 여겨져 2개씩 만들어주었습니다. 그 구현은 아래와 같습니다.

bfs함수를 구현하는 과정에서 가만히 있는 기능의 무한 순환을 막기위해, 해당 기능의 본질에 대해서 생각해 보았습니다. 가만히 있는 기능이 왜 필요한건가, 사실 딱히 필요없는 기능일 수도 있는게 아닌가? 천천히 생각하며 문제를 다시 읽어보니, 이는 밤을 위해 존재하는 기능이라는걸 깨달았습니다. 그래프를 탐색하다가 밤에 벽을 만나버린 사람은 어떻게 해야할까요? 벽을 부수지 못하므로, 강제로 제자리에 있게 되는 것입니다. 보통의 그래프 탐색처럼 코드를 짜주면, 이때 탐색 자체를 멈춰버리게 될 것입니다.. 그래서 밤에는 가만히 있는 기능을 추가해주었습니다. 또한, 낮과 밤의 bfs탐색을 나눠두고, 밤에만 가만히 있을 수 있게 해줌으로서 자연스럽게 무한 순환을 예방했습니다. 밤에 가만히 있던 탐색은 낮에 탐색을 이어 진행하다가 진행 사항이 없을 경우 소멸되기 때문에, 무한히 순환할 일은 없게 됩니다.

<코드 3>의 '탐색 - 낮'은 k개의 벽을 부술 수 있는 그래프 탐색입니다. 탐색 과정에서 도착지점을 만나게 되면, 이동 거리를 기록하고 탐색을 종료합니다. 방문 여부를 확인하는 check배열은 현재까지 벽을 부순 횟수에 따라 방문을 체크하도록 만들었습니다. (bool check[y좌표][x좌표][벽 부순 횟수]로, 벽을 하나 부술 때마다 벽 부순 횟수++). 다음 탐색 위치가 벽이 아닐때는 평범하게 진행하고, 벽일 때는 벽을 부순 횟수를 하나 추가해준 뒤, 해당 위치를 지나가게 해주었습니다. 보통의 bfs함수라면 현재 탐색에 이용중인 queue인 'day'에 다음 탐색할 노드들를 push해주겠지만, 밤과 낮의 다른 진행을 위해 'night'라 이름 붙인 queue에 push해주었습니다. (밤에는 반대로 'day'라 이름 붙여준 queue에 push해줍니다.)

 

이렇게 탐색도 여러개, queue나 stack도 여러개 만들어 주면 성질이 다른 여러개의 탐색을 여기저기 오가며 진행할 수 있도록 구현해줄 수 있습니다. 이와 같은 탐색으로 풀 수 있는 문제는 많습니다. 탐색자가 2명 이상인 상황에서, 진행 조건도 각자 상황이나, 진행 상황에 따라 다음 노드로의 진행 가능 여부가 달라지는 상황에서 편리합니다. (ex. 물이 얼음을 한칸씩 녹이며 진행하고 얼음이 녹아 만들어진 물이 다음 얼음을 녹이는 등의 문제) 

 

'탐색 - 밤'에서는 벽을 부수는 기능을 빼고, 가만히 있을 수 있게 해주었습니다. 위에서 언급한대로 dy, dx배열의 5번째 원소까지 탐색하도록 해주었습니다. 탐색 조건은 다음 위치가 0이고, 방문한 적이 없는 경우와 다음위치가 현재 위치와 같은 경우에 push하도록 했습니다. 사실 코드를 짜면서 생각해보니 굳이 마지막 배열을 dy[4] = 0, dx[4] = 0 과 같이 해줄 필요 없이 주석 처리 해준 것처럼 예외처리를 해주는 것이 더 편할것 같다는 생각을 하게 되었습니다..

아니면, for문의 밖에 따로 제자리에 무조건 푸쉬하는 코드를 짜 주었어도 좋았을 것 같습니다. 왜냐하면 제자리를 다시 방문할 때에는 다음 진행 위치가 지도를 벗어나는지 체크 할 필요가 없고, 해당 위치가 벽인지, 방문한적이 있는지 따로 체크할 필요가 없기 떄문입니다. 아무런 따질 것이 없이 그저 제자리에 push하기만 하면 그만인 것이지요.

이를 반영한 코드는 아래와 같습니다.

훨신 깔끔하네요 호호호~ 시간 차이는 없는거나 마찬가지지만, 조건문이 좀 더 보기좋게 되었습니다. 정말 만족스럽네요! 이로써, 문제 해결을 위한 핵심 코드들을 모두 설명해주었습니다. 나머지 구현은 따로 첨부하겠습니다.

부족한 글 읽어주셔서 감사합니다. 불꽃카리스마진호우!^^

 

 

전체코드: http://colorscripter.com/s/tERn91m