1697. [Python]숨바꼭질

1. 문제

 

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

1697번: 숨바꼭질

 

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