[Python] BOJ(백준) 1697번 - 숨바꼭질

링크

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

난이도(solved.ac 참고)

실버1

풀이

BFS 활용했고, 다음 큐가 비어있을 때까지 계속 진행하는데, 우선 popleft를 한 뒤에 그 값에 대해 1을 뺀 값, 1을 더한 값, 2를 곱한 값 중에 10만보다 작거나 같고, visited의 값이 0인 경우(그러니까, 방문하지 않은 경우) 그 값을 큐에 넣은 뒤 그 인덱스에 해당하는 visited의 값을 1 더해줬다. 여기서 visited는 방문 여부로도 판단할 수 있지만, 이동한 횟수로도 그 기능을 한다. 그 값이 0이라면 한번도 방문한 적이 없는 것이고, 0이 아니면 방문한 적이 있는 것이다.

 

시간 없어서 일단 여기까지 풀었는데, 이따 밤에 다시 풀어봐야겠다 ㅠㅠ

풀었는데, 통과하지 못했던 이유는.. 저 if문에서 next가 0보다 작을 수 있다는 점을 생각하지 않았기 때문이었다.

어쨌든 해결..

 

여기서, 17행을 보면 and조건으로 묶여있는데, 이 두개가 바뀌면 안된다. and 조건의 경우 앞 조건을 먼저 확인하고 그 다음 조건을 확인하는 것으로 보인다. 두개가 바뀔 경우, not visited[i]더라도, i가 10만을 넘을 수 있기 때문에 제출해보면 IndexError가 난다. 그렇기 때문에 먼저 i의 범위를 제한한 뒤 not visited[i] 여부를 확인해야 한다.