[백준/파이썬] 18235: 지금 만나러 갑니다

문제 풀러 가기!!

오 ㅎㅎ 재밌는 BFS 문제였다.
처음에는 어떻게 풀지 고민되어서 문제 분류를 봤다. BFS 라고 하니 감이 와서 풀 수 있었다!
보통 너비 우선 탐색을 하면 2차원 테이블 안에서 가장 빨리 도착하는 식으로 풀었는데, 직선 상에서 오리, 육리가 만나는 걸 찾아서 특이했다.
또 보통은 하나에서 출발해서 고정된 도착점을 찾는 식이었는데, 이번에는 오리, 육리가 둘 다 움직여서 독특했다.

오리, 육리가 만날 수 있는 최소 일수를 구해야 하므로 BFS를 사용했다. 

1. 오리, 육리의 (점프 횟수, 위치, 이름)을 q에 넣었다.

2. q가 있는 동안 while문을 돌렸다.

2-1. q에 있는 원소를 popleft로 꺼냈다. (먼저 들어온 걸 먼저 꺼냄) 점프 횟수, 위치, 오리인지 육리인지가 나온다.

2-2. 오리라면:  n번 점프해서 오리가 갈 수 있는 지점들을 모두 now_5_ri라는 set에 저장해두었다. 이때 범위 체크도 고려해야 한다! (0보다 크고, N+1 보다 작아야 한다!!)

2-3. 육리라면: 육리가 n번 점프해서 있을 수 있는 위치가 now_5_ri(오리가 갈 수 있는 지점들) 중에 있으면, 둘이 만날 수 있다고 봤다. 그래서 flag를 True로 바꾸고, while문을 break 해서 나왔다. ans에 점프 횟수를 저장했다.

3. 마지막에는 flag 에 따라서 정답을 출력하면 된다. flag가 false면 둘이 못 만나니까 -1을, flag가 true이면 둘이 만나는 거니까 ans+1을 출력한다.(ans에 점프 횟수를 저장했는데, 그 후에 한번 더 점프한 위치니까.. ans+1을 해야 한다.)

 

코드 👩‍💻

'''
18235: 지금 만나러 갑니다
https://www.acmicpc.net/problem/18235
'''

import sys, collections

input = sys.stdin.readline().rstrip

N, A, B = map(int, input().split())

q = collections.deque()
now_5_ri = set()

q.append((0, A, '5'))  # 몇번 점프, 오리 위치, 이름
q.append((0, B, '6'))  # 몇번 점프, 육리 위치, 이름

now_cnt = 0
flag = False
ans = 0
while q:
    jump_cnt, idx, name = q.popleft()


    if name == '6':  # 육리는 오리를 찾기
        # 점프 횟수가 바뀌면
        if now_cnt != jump_cnt:
            tmp1 = idx + 2 ** jump_cnt
            tmp2 = idx - 2 ** jump_cnt
            if 0 < tmp1 <= N:
                q.append((jump_cnt + 1, tmp1, '6'))
            if 0 < tmp2 <= N:
                q.append((jump_cnt + 1, tmp2, '6'))

        else: # 점프 횟수 같을 때

            tmp1 = idx + 2 ** jump_cnt
            tmp2 = idx - 2 ** jump_cnt

            if tmp1 in now_5_ri or tmp2 in now_5_ri:  # 만났으면
                flag = True
                ans = jump_cnt
                break
            else:  # 못 만났으면
                if 0 < tmp1 <= N:
                    q.append((jump_cnt + 1, tmp1, '6'))
                if 0 < tmp2 <= N:
                    q.append((jump_cnt + 1, tmp2, '6'))

    else:  # 오리면 자기 자리 표시하도록
        # 점프 횟수가 바뀌면
        if now_cnt != jump_cnt:
            now_5_ri = set()  # 오리 위치 초기화
            now_cnt = jump_cnt

        tmp1 = idx + 2 ** jump_cnt
        tmp2 = idx - 2 ** jump_cnt

        if 0 < tmp1 <= N:
            now_5_ri.add(tmp1)
            q.append((jump_cnt + 1, tmp1, '5'))

        if 0 < tmp2 <= N:
            now_5_ri.add(tmp2)
            q.append((jump_cnt + 1, tmp2, '5'))

if flag:
    print(ans+1)
else:
    print(-1)