-
1697. [Python]숨바꼭질Python_알고리즘/Silver I 2023. 3. 9. 13:13
1. 문제
https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- BFS (Queue)
3. 파이썬 코드
from collections import deque N,K = map(int,input().split()) # popleft 를 사용하기 위해 deque 를 사용 => deque 의 경우 popleft 사용해도 시간 복잡도가 O(1)인 것으로 암 queue = deque([[N,0]]) # 방문했는지 체크를 10만개까지 생성함 visited = [False]*(2*10**5+1) visited[N] = True # 만약 위치가 같은 경우 시간이 0 초 걸렸으므로 0 출력 if N == K: print(0) # 시작 위치가 종료위치보다 큰 경우 => -1 해서 도착하는 방법밖에 없다. elif N > K: print(N-K) # 그 외의 경우 else: # queue를 무한 반복 while queue: # 제일 왼쪽 값 pop 하여 check = queue.popleft() # visited 에 True로 변경 visited[check[0]] = True # 2배, -1, +1 한 값들을 각각 변수에 저장 check_twice = check[0] * 2 check_minous = check[0] - 1 check_plus = check[0] + 1 # -1 했을때 값이 K*2를 넘지 않고 0 이상일때 실행 if check_minous <= K*2 and check_minous >= 0: # 목표 값인 경우 check 에 저장된 count 변수를 출력 => check == [숫자,시간] 으로 구성됨 if check_minous == K: print(check[1]+1) break # 방문하지 않은 경우 if not visited[check_minous]: # queue에 -1 한값과 이전 값의 시간을 더해서 저장 queue.append([check_minous,check[1]+1]) # visted 변수 true로 변경 visited[check_minous] = True # +1 했을때 값이 K*2를 넘지 않고 0 이상일때 실행 if check_plus <= K*2 and check_plus >= 0: # 목표 값인 경우 check 에 저장된 count 변수를 출력 => check == [숫자,시간] 으로 구성됨 if check_plus == K: print(check[1]+1) break if not visited[check_plus]: # queue에 +1 한값과 이전 값의 시간을 더해서 저장 queue.append([check_plus,check[1]+1]) visited[check_plus] = True # *2 했을때 값이 K*2를 넘지 않고 0 이상일때 실행 if check_twice <= K*2 and check_twice >= 0: # 목표 값인 경우 check 에 저장된 count 변수를 출력 => check == [숫자,시간] 으로 구성됨 if check_twice == K: print(check[1]+1) break if not visited[check_twice]: # queue에 *2 한값과 이전 값의 시간을 더해서 저장 queue.append([check_twice,check[1]+1]) visited[check_twice] = True
4. 문제를 풀고난 후 생각
- BFS 류의 문제이기 떄문에 선입선출(FIFO)을 생각을 하였고, 일반 List로 풀면 왼쪽부터 뽑아낼려면 O(N)의 시간복잡도가 걸리기 떄문에 `deque`를 사용하여 popleft 를 통해 O(1)의 시간복잡도 낮은 시간복잡도를 사용할려 했다.
- 문제를 구현하는 것 자체는 그렇게 어렵지 않았지만, 문제의 조건들을 생각해가며 푸는데 시간을 많이 소요하고 시간초과도 많이 났던 것 같다.
- 처음 생각은 그냥 구현하면 끝이 아닌가? 라는 생각을 했고 별다른 제한을 두지않고 한 값에 대해서 -1, +1, *2 한값들을 모두 리스트에 넣었다. 하지만 이렇게 진행할 경우 탐색하는 값들이 너무 많아서 좀 더 줄일 수 있는 방법에 대해서 생각해 보았다.
- 값들에 대해서 K*2(목표되는 값의 2배)가 넘는 값이 되면 필요가 없기 때문에 그 값보다는 작고 0 보다는 커야하는 조건을 걸어서 탐색하는 리스트의 범위를 많이 제한시켰다.
- 여기서 생기는 또 다른 문제점은 K(목표값)이 N(현재값) 보다 작은 경우가 있는데 이경우 N의 값을 -1씩 해서 K 에 도달하는 경우밖에 없기 때문에 입력값이 들어왔을 때 부터 검사를 진행해주고 난 후 제출했더니 해결됐다.
5. 문제를 푸는데 도움이 되는 지식
- 큐
- BFS
'Python_알고리즘 > Silver I' 카테고리의 다른 글
1926. [Python]그림 (0) 2023.12.09 1342. [Python]행운의 문자열 (1) 2023.12.08 1421. [Python]나무꾼 이다솜 (2) 2023.12.07 1527. [Python] 금민수의 개수 (0) 2023.08.30 2667. [Python]단지번호붙이기 (0) 2023.06.04