백준 1194

1194번: 달이 차오른다, 가자.

 

 꽤 재밌었던 문제. 왔던 방향으로 다시 되돌아가야 되는 경우가 있어서 처음엔 어떻게 구현해야할지 몰라서 계속 헤맸다. 열쇠를 새로 얻으면 벽에 부딪히고 다시 되돌아갈 수 있게 해야 하나 등등의 오만 생각이 다 들었으나, 현재 내가 어떤 상태에 놓여있는지 정의하면 문제가 간단해지는 걸 깨달음. int 하나를 내가 획득한 열쇠로 정의하고 내가 지금 이러한 열쇠를 얻은 상태에서 내가 가려는 지점을 방문한 적이 있는지 체크하면 중복을 방지할 수 있고 또 내가 새로운 열쇠를 얻은 시점에 가던 길 그대로 가는 경우와 되돌아가는 경우 모두 손쉽게 처리가 가능하다는 걸 깨달음.

 

 주의점은 새로운 열쇠를 얻었을 때 bit 상태를 업데이트 하므로 상태가 달라짐. visited 배열을 업데이트 해야함.

 

 

 - Source code link

github.com/Bibidi/Algorithms/blob/master/boj/boj%201194.cpp