[BOJ] 1697 숨바꼭질

문제 예시이다.

 

 

문제는 수빈이가 동생을 +1, -1, *2 세 가지의 움직임을 통해 가장 빠르게 찾을 수 있는 횟수를 구하는 것이다.

처음에는 이것이 bfs랑 무슨 연관인거지? 생각하고 IF문을 마구잡이로 쓸 생각 밖에 나지 않았다.

 

문제 풀이를 보고나서, 풀이의 핵심은 visited배열을 MAX(100001)만큼 만든 것을 통해 해결하려고 한 것이다.

수빈이가 움직일 수 있는 범위를 최대 MAX로 둔 것에 착안하여 움직인 위치에 방문 횟수를 기록하는 방식이다.

현재 수빈이의 위치를 Queue에서 pop한 후, 세 가지 동작에 대하여 아직 방문하지 않았고, 범위를 초과하지 않았다면 이동한 visited배열에 이동하기 전 visited배열의 값 +1 을 넣는다.

 

아직도 헷갈리는 것은 visited가 왜 0이면 안되는걸까?

이미 한번 방문했기 때문에 거쳐서 들어온 값은 최소가 아니기 떄문에 의미가 없는 값이기 떄문이다.

 

 

 

내 생각:  처음 이 문제를 접했을 때, 문제를 풀 수 있는 어떠한 규칙이 있는 줄 알았다. *2 값이 오차가 2이상이면,,,어쩌구,,, 하면서 정리되지 않은 나만의 규칙들이 이것저것 생각이 났지만,, 더 먼 산으로 가는 방향이였다.

 

"이런 생각을 어떻게 하지"라는 생각밖에 들지 않는다... 알고리즘 계속 하다보면 실력이 느는거겠지,,,?

아직 알고리즘에 대한 문제 방식에 대해 익힐 필요가 있다. 아직은 초반이라 꾸준히 문제량을 늘리는데에 집중해보자.