[백준 13549] 숨바꼭질3

🍎 [백준 13549] 숨바꼭질3

문제링크

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

13549번: 숨바꼭질 3

 

⚾ 코드

from collections import deque

N, K = map(int, input().split())  # N: 언니, K:동생
INF = int(1e9)
second = [INF]*(max(N, K)*2)  # 언니와 동생중 큰 값의 두 배 길이의 second 리스트 생성


def check_range(n):  # 범위 확인
    if n >= 0 and n < (max(N, K)*2):
        return True
    return False

def solution(start, end):
    second[start] = 0
    q = deque()
    if start == end:
        return 0
    q.append(start)

    while q:  # q가 없을 때 까지
        index = q.popleft()

        move_list = [index*2, index-1, index+1]

        for j in range(3):
            next_node = move_list[j]
            if check_range(next_node):
                if j == 0:  # 만약 순간이동을 한다면 0초 소요
                    if second[next_node] > second[index]:
                        second[next_node] = second[index]
                        q.appendleft(next_node) # 
                        
                else:  # 만약 +1, -1 이동을 한다면 현재 인덱스의 시간 +1초 소요
                    if second[next_node] > second[index]+1:
                        second[next_node] = second[index]+1
                        q.append(next_node)

    return second[end]


print(solution(N, K))

 

🔔 해결 과정 & 깨달은 점

- 처음에 문제를 접했을 때 다이나믹 프로프래밍 방법으로 풀어야 하나? 라고 생각했다.

그래서 다이나믹 프로그래밍 방법으로 풀었더니, -1로 이동했을 때 그 노드가 갱신된 경우를 고려할 수 없었다. 그래서 -1로 이동했을 때 갱신되면, 다시 그 노드에서 update를 했다. (접은 글 참조)

N, K = map(int, input().split())
INF = int(1e9)
second = [INF]*(max(N, K)*2)


def check_range(n):
    if n >= 0 and n < (max(N, K)*2):
        return True
    return False


def update_list(index):
    move_list = [index*2, index-1, index+1]

    for j in range(3):
        next_node = move_list[j]
        if check_range(next_node):
            if j == 0:
                if second[next_node] > second[index]:
                    second[next_node] = second[index]
            elif j == 1:
                if second[next_node] > second[index]+1:
                    second[next_node] = second[index]+1
                    update_list(next_node)
            else:
                if second[next_node] > second[index]+1:
                    second[next_node] = second[index]+1


def solution(start, end):
    second[start] = 0

    if start == end:
        return 0

    if start < end:
        for i in range(start, end+1):
            update_list(i)

    else:
        for i in range(start, end-1, -1):
            update_list(i)

    return second[end]


print(solution(N, K))

- 풀이가 잘 진행되지 않아 질문 검색 탭에 올라와있는 글들을 읽어보니 0-1 BFS 알고리즘을 참고해보라는 글이 있었다.

    -> 0-1 BFS 알고리즘에 포스팅해두었다.

- deque를 사용하여 풀었더니 바로 통과되었다!