[C++] 백준 1697번 숨바꼭질

그래프 탐색 문제인 줄 몰랐던 그래프 탐색 문제.

알고보니 모든 정점들이 서로 연결돼 있던 그래프였다는 것을 문제에서 설명해 주고 있었다.

이 사실을 질문 검색 게시판을 보다가 알게되었다.

 

처음 이문제를 보았을 때

수학 문제인 줄 알았다. 그래서 경우의 수를 나눠서 구현해야 하는 줄 알고 그렇게 시도했다.

결과는 틀렸습니다가 나왔다. 그래서 어떻게 풀어야 할까 고민하면서 질문 검색 게시판을 보았다.

 

두번째 시도

게시판에서 보니 사람들이 그래프 탐색으로 많이 풀었다는 사실을 알게되었다.

"이 문제를 어떻게 그래프 탐색으로 풀까..?" 고민하던 찰나에 머리에 다익스트라와 비슷한 알고리즘이 스쳐지나갔다.

게시판 검색 안했다면 아마 생각 못하지 않았을까 생각한다. 정말 많은 문제를 풀어봐야 겠다고 생각했다.

DFS, BFS는 자신있다고 생각했는데 실버1만 와도 정말 생각하기 어렵게 느껴진다.

롤에서는 실버1, 실버2 차이 없던데...

 

문제풀이

 

사용한 STL과 변수

BFS를 이용해서 풀긴 했는데, 그래프를 따로 구현할 필요가 없다.

어차피 그래프는 10만개의 각 정점이 모두 연결된 형태라고 문제에서 알려주는 셈이다.

그리고 10만개의 각 정점을 방문했는지 여부를 확인하는 visit 배열을 만들어주었다.

 

메인함수 - 1

n과 k를 입력받고 queue를 pair 자료형으로 만든다.

첫번째가 정점의 번호, 두번째가 현재 내가 몇초 왔는지를 저장해둔다.

 

메인함수 - 2

반복문에 진입하고 나서는 큐의 맨 앞 번호와 초를 불러오고 pop()한다.

만일 cur_num이 내가 찾고자 하는 k와 같다면 result를 업데이트 한다.

사실 다익스트라와 비슷한 개념인데, 어차피 cur_num이 k에 접근했다면 굳이 저렇게 삼중연산자를 할 필요없이 

바로 업데이트 해주면 된다. 왜냐면 첫 접근이 최소의 초를 사용한 접근이였을 것이다.

그리고 만일 아니라면 bfs처럼 구현해주면 된다.

1. cur_num - 1이 0보다 크거나 같고(0을 포함 안해서 한 번 틀렸다.) 방문하지 않았다면 큐에 넣어준다.
2. cur_num + 1이 100001보다 작고 방문하지 않았다면 큐에 넣어준다.
3. 2 * cur_num이 100001보다 작고 방문하지 않았다면 큐에 넣어준다.

그리고 결과값을 출력해주면 끝.

 

아래 두 개는 구현으로 시도하다 틀렸고

맞았습니다 바로 아래 틀렸습니다 는 0을 포함 안해서 틀렸다...

 

그래프 문제라고 생각도 못했는데 그래프 문제였다.

아직 갈 길이 멀다. 더 많은 문제를 풀어보고 익숙해져야 할 것 같다...

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.