17071 숨바꼭질 5

 

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

#bfs

17071번: 숨바꼭질 5

 

#17071 숨바꼭질 5 정리

'''
조건에 맞춰서 도는데 이제 조건이 뭐냐 하면
1. bfs 내에서 홀수와 짝수 로 구분을 하자면 이 전의 있던 홀수번째초의 것은 이후에 홀수번째초의 것에 다 포함된다. 고로 계속 홀수번쨰는 홀수 visited에 짝수번째는 짝수 visited에 탐색을 저장하다가
만약 지금 돌고 있는 curtime 이 이전에 탐색했었던 거라면 (홀 짝 맞춰서) 바로 현재 시간 출력 이걸 하기 위해서는 기존에 -1 +1 *2를 세부적으로 나누었던걸 안하고 전부 다 세어줘야함

홀 짝이 되는 이유는 -1 +1 하면 0이 되기 때문임. 고로 앞으로 가는 모든 경우의 수에서 이전것에 더해지는거다 . 예를들면

n-1 n+1 n*2 이니깐

3     2   4   6

4  1   3 4  5   7  8  12

5  0 2 3 4 5 6 7 8 9 10 11 13 14 16 24   

봐라 2 4 6 들어간다 5번째에 

고로 여기서 알 수 있는것 이전에 탐색했는지만 보면 이후에 정답인 시간에 k가 (홀,짝에 맞춰서) 탐색됐었는지만 보면 빠르게 답을 알 수있다는 것.

'''

def f(n,k):

    visited=[[False]*500001 for i in range(2)]
    #0은 짝수 1은 홀수

    flag=0
#홀,짝 깃발 설정

    visited[flag][n]=True
#0 짝이라 가정 탐색 완료

    todo=[n]
#큐에 n집어 넣고

    curtime=0
#현재 시간 0초

    while todo:
        nexttodo=[]
#다음 큐

        if k>500000:
#만약 K가 조건에 안 맞으면 -1 (문제 조건)

            return -1
        if visited[flag][k]==True:
            return curtime
#이전에 K가 탐색이 됐었으면 현재시간 리턴

        curtime+=1
#다음 탐색 시간

        k+=curtime
#시간은 1초씩 늚으로 함수 더 만들지 말고 그냥 시간을 더함 K에

        flag=flag^1
#XOR을 이용하면 그럴듯하게 0일때 1 1일때 0을 표현할수있다! 쓸데없긴해

        for n in todo:
            for i in (n+1,n-1,n*2):
                if 0>i or i>500000:
                    continue
#i역시 조건에 맞아야함

                if visited[flag][i]==False:
                    visited[flag][i]=True
#홀짝에 맞춰서 탐색 되지 않은걸 탐색한다는 것

                    nexttodo.append(i)
#다음 큐에 넣자

        todo=nexttodo
#큐 리셋

n,k=map(int,input().split())
time=f(n,k)
print(time)

#답

 

#쉽지 않았고 BFS를 구사하여 풀 수는 있었으나 이런 응용문제가 나오면 대처를 어떻게 해야되는지에 대한 생각은 안했었다. 그러다 이런 문제가 나오니 이게 참 틀에 박힌 생각을 반복해서 하게 됐던듯. 내가 볼땐 홀 짝 이 생각을 제일 먼저 하는 사람이 진짜 컴퓨터적 생각을 하는 사람이 아닌가 했다. 나는 그저 키보드 만질 줄 아는 찐따니 답지를 봐야겠다고 생각했고 실행에 옮겼다

 

#이전에 숨바꼭질 문제들을 풀면서 다듬었던 내 코드에 조금씩 커밋하고 커밋하면서 이번문제역시 홀짝이라는 그 개념을 코드에 삽입 출력 제출 성공 이 순서로 끝나게 되었다. 이런 유연한 생각을 반복하다 보면 하게 될거라고 생각하니 기분이 좋아진 하루였다. 내 다음 발판은 뭘까