쑥로그

[자바] 백준 1697번 완전탐색 BFS - 숨바꼭질 본문

개인 프로젝트/72일 알고리즘 다지기 프로젝트

[자바] 백준 1697번 완전탐색 BFS - 숨바꼭질

SOOOOOK 2019. 9. 30. 16:16

https://www.acmicpc.net/problem/1697

 

1697번: 숨바꼭질

문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지

www.acmicpc.net

 

BFS로 쉽게 풀 수 있는 문제였다. 다만 조금 애먹었던 점이 메모리 초과 부분이었다.

익히 알고있는데로 BFS로 풀면 메모리 초과 문제가 발생한다. (+나는 런타임에러도 같이 났다.)

 

1. 메모리 초과

 

이 부분은 과거에 했던 값을 계속 처리하기 위해 큐에 값을 넣는 것 때문에 발생한다. 무슨 일이냐면, 위치 10에서 11, 9, 20으로 갈 수 있을 것이다. 근데 10까지 갈 수 있는 방법은 또 많다. 9->10, 11->10, 5->10. 

10으로 일단 도착하면 위의 3가지 길은 한번만 계산하면 되므로 

방문여부를 확인하는 배열을 하나 추가해서 방문할때마다 true로 설정해두고 체크하면서 이 문제를 해결할 수 있다.

 

 

2. 런타임 에러

 

이건 배열의 잘못된 인덱스로 접근하려고 해서 발생했다.

방문 여부를 체크하는 배열은 이 문제에서 최대로 받을 수 있는 값 100,000을 가지는데 +1, -1, *2 연산을 처리하다보면 0보다 내려가거나 100,000을 넘어갈 수 있다. 이걸 체크해주면 해결할 수 있다.

 

 

https://github.com/mychum1/shelf/blob/master/com.ksko.algorithm/src.main.java/baekjoon/P_1697.java

'개인 프로젝트 > 72일 알고리즘 다지기 프로젝트' 카테고리의 다른 글

[자바] 백준 14501 문제 풀이 - 퇴사  (0) 2019.09.17
[자바] 백준 11053 가장 긴 증가하는 수열  (0) 2019.09.14
[자바] 백준 1912 - 연속합 풀이  (0) 2019.09.10
알고리즘 스터디 2주차 준비 - 동적계획법 #1  (0) 2019.08.31
72일 알고리즘 스터디 커리큘럼  (0) 2019.08.25
'개인 프로젝트/72일 알고리즘 다지기 프로젝트' Related Articles more