[백준_Python] 12851번 숨바꼭질 2 [골드 4]

황준성·2024년 12월 13일
DFS/BFS백준
0

BOJ_Python

목록 보기
38/70

문제

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

입력 예시 1

5 17

출력 예시 1

4
2

문제 이해 및 코드

틀린 코드

# 백준 12851번 숨바꼭질 2

# 읽는 속도 효율화
import sys
input = sys.stdin.readline

# 큐 모듈 import
from collections import deque

def BFS(x, times):
    global visited, min_time, count

    queue = deque()
    queue.append((x, times))
    visited[x] = 1 #방문처리

    while queue:
        x, times = queue.popleft()

       # 위치 값이 동생위치에 도달한다면
        if x == K:
            # 처음 도달했을때의 시간을 min_time에 기록
            if min_time == 0:
                min_time = times
                count += 1
            # 같은 시간에 도착하는 다른 경우도 카운트
            if times == min_time:
                count += 1

        # 더 이상 진행할 필요가 없으면 종료
        # 최단 시간보다 클때는 더 이상 탐색할 필요 없음
        if times > min_time and min_time > 0:
            return

        for nx in [x-1, x+1, x*2]:
            if 0 <= nx <= MAX and not visited[nx]:
                visited[nx] = 1 #방문처리
                queue.append((nx, times+1))

# 0. 입력 및 초기화
MAX = 100000

N, K = map(int, input().split()) # N수빈 K동생
visited = [0] * (MAX+1)

min_time = 0 # 최단 시간 저장
count = 0 # 최단 시간 경로 카운트

# 1. BFS호출
BFS(N, 0)

# 2. 출력
print(min_time)
print(count)

왜인지 모르겠지만 예제 입력을 하면 출력은 잘 나온다. 하지만 로직 자체가 틀렸다. 이게 최단거리를 하나만 구하는 문제면 visited를 지금처럼 사용하면 된다. 하지만 여러개의 최단거리를 구해야 하는 문제이기 때문에 visited를 이렇게 사용하면 정상적으로 구할 수가 없다. 일회성 visited 사용이기 때문에.

사실 이 부분을 어떻게 해결해야 할지 정말 감이 안왔다. 그래서 다른 사람들의 풀이를 검색했지만, 그 사람들도 자세한 설명보다는 그냥 코드만 붙여논 경우가 대부분이었고, 어떤 사람은 그 부분이 이해가 되지 않는다면 글을 써놓았다. 그래서 chatGPT를 이용해서 이해하려고 노력했다.

음,, 이번 문제에서는 visited를 조금 다른 방식으로 사용해야 한다. 먼저 visited의 초기값은 -1로 만든다. 이 문제 자체가 BFS문제이기 때문에 BFS를 사용한다. BFS는 거리가 가까운 순서부터 이동을 한다. 거리가 1, 2, 3.. 이런 순으로.

만약 N=2, K=4인 경우라면 시작점을 큐에 넣고에 넣고 visited값을 0으로 바꾼다.

현재 위치 x값이 2일때
이동 방식:
𝑥−1, 𝑥+1, 𝑥×2

갈 수 있는 위치 = 1, 3, 4 이다.
visited[1] = 1 (times+1)
visited[3] = 1 (times+1)
visited[4] = 1 (times+1)

그러면 4까지 도달하기 위해서는 최단시간이 1이여야 최단거리가 된다.

-> 최단 시간이 1 이상은 값은 애초에 4에 도달할 수가 없다.

visited[nx] = times + 1 때문에.

참고할만한 chatGPT설명

좋습니다! 이번에는 ( N = 5 ), ( K = 17 )의 경우를 다시 시뮬레이션하고 그림으로 보여드리겠습니다.

입력

  • 수빈 위치 ( N = 5 ), 동생 위치 ( K = 17 )
  • 이동 방식: ( x-1 ), ( x+1 ), ( x \times 2 )

탐색 진행 (BFS)

초기 상태

  • 시작 위치: ( 5 )
  • queue = [(5, 0)]
    → 현재 위치 5에서 걸린 시간 0
  • visited = [-1] * 100001
    → visited[5] = 0
    시작 지점은 visited의 값을 0으로 설정

1단계 탐색 (( N = 5 )):

  • 이동 가능한 위치: ( 4, 6, 10 )
  • queue = [(4, 1), (6, 1), (10, 1)]
  • visited[4] = 1, visited[6] = 1, visited[10] = 1

이게 제일 중요하고 어려운 부분!

5의 위치에서 갈 수 있는 경우가 3가지이고
visited[nx] == -1 (방문한 적이 없거나)
visited[nx] == visited[x] + 1 (이미 지나갔던 곳이면 먼저 도달한 최단거리(시간) 값이 visited[nx]에 저장되어 있으니까, 그 값이 현재 값보다 +1 크면 그건 최단 순서가 맞는 거임.

BFS니까 최단거리들이 먼저 그 배열을 지나갔을거다. 처음 최단거리가 지나갈 때는 -1이니까, 이 경우말고 안에 값이 있을때는 이미 지나간 최단거리가 남겨놓은 최단시간이자 거리란 의미다. 즉, 현재 값보다 작은 곳으로 가는 건 여기서 막힌다. 뱅뱅도는 경우는 여기서 다 걸러지는 거다.

2단계 탐색 (( 4, 6, 10 )):

  • 위치 ( 4 ): ( 3, 5, 8 ) (5는 이미 방문됨)
  • 위치 ( 6 ): ( 5, 7, 12 ) (5는 이미 방문됨)
  • 위치 ( 10 ): ( 9, 20, 5 ) (5는 이미 방문됨)
  • queue = [(3, 2), (8, 2), (7, 2), (12, 2), (9, 2), (20, 2)]
  • visited[3] = 2, visited[8] = 2, visited[7] = 2, visited[12] = 2, visited[9] = 2, visited[20] = 2

4, 6, 10 에서 각각의 3가지 경우를 또 처리함

3단계 탐색:

  • 위치 ( 3 ): ( 2, 4, 6 ) (이미 방문된 위치 제외)
  • 위치 ( 8 ): ( 7, 9, 16 ) (이미 방문된 위치 제외)
  • 위치 ( 7 ): ( 6, 8, 14 ) (이미 방문된 위치 제외)
  • 위치 ( 12 ): ( 11, 24, 10 ) (이미 방문된 위치 제외)
  • 위치 ( 9 ): ( 8, 10, 18 ) (이미 방문된 위치 제외)
  • 위치 ( 20 ): ( 19, 21, 40 )
  • 목표 ( K = 17 )에 도달.

  1. 시작점 (5):

    • ( N = 5 )에서 시작합니다.
    • ( visited[5] = 0 ), ( queue = [(5, 0)] ).

  2. 1단계 탐색 (5 → 4, 6, 10):

    • ( visited[4] = 1 ), ( visited[6] = 1 ), ( visited[10] = 1 ).
    • 큐 상태: queue = [(4, 1), (6, 1), (10, 1)].

  3. 2단계 탐색 (4, 6, 10):

    • 각각의 위치에서 이동 가능한 위치를 계산.
    • ( 4 → 3, 8 ), ( 6 → 7, 12 ), ( 10 → 9, 20 ).
    • ( visited ) 업데이트: ( 3, 8, 7, 12, 9, 20 ).

  4. 3단계 탐색:

    • 이 단계에서 ( 17 )에 처음 도달.
    • ( visited[17] = 3 ), 최단 시간 = 3초.

visited의 역할 요약:

  1. 방문한 위치는 다시 탐색하지 않아 중복 계산을 방지.
  2. 각 위치에 도달하는 데 걸린 "최소 시간"을 기록.

이제 ( N = 5, K = 17 )의 BFS 탐색 과정을 이해하는 데 도움이 되었길 바랍니다. 추가 설명이 필요하면 말씀해주세요! 😊

그러니까 BFS로 돌리니까 각 최단 시간을 저장을 하는 거고 혹시나 앞으로 갔다 뒤로 가는 경우 처럼 뱅뱅 돌아가는 경우는 조건문으로 알아서 걸러지는 방식이다.

1차 정답 코드

# 백준 12851번 숨바꼭질 2

# 읽는 속도 효율화
import sys
input = sys.stdin.readline

# 큐 모듈 import
from collections import deque

def BFS(x, times):
    global visited, min_time, count

    queue = deque()
    queue.append((x, times))
    visited[x] = 0 #방문처리

    while queue:
        x, times = queue.popleft()

       # 위치 값이 동생위치에 도달한다면
        if x == K:
            # 같은 시간에 도착하는 다른 경우도 카운트
            if times == min_time:
                count += 1
            # 처음 도달했을때의 시간을 min_time에 기록
            if min_time == 0:
                min_time = times
                count = 1
            

        for nx in [x-1, x+1, x*2]:
            if 0 <= nx <= MAX and (visited[nx] == -1 or visited[nx] == times + 1):
                visited[nx] = times +1 #방문처리: 최소거리(시간)을 기록
                queue.append((nx, times+1))

# 0. 입력 및 초기화
MAX = 100000

N, K = map(int, input().split()) # N수빈 K동생
visited = [-1] * (MAX+1)

min_time = 0 # 최단 시간 저장
count = 0 # 최단 시간 경로 카운트

# 1. BFS호출
BFS(N, 0)

# 2. 출력
print(min_time)
print(count)

1차 코드를 사용시 주의점

# 위치 값이 동생위치에 도달한다면
        if x == K:
            # 같은 시간에 도착하는 다른 경우도 카운트
            if times == min_time:
                count += 1
            # 처음 도달했을때의 시간을 min_time에 기록
            if min_time == 0:
                min_time = times
                count = 1

문제점

  1. if문 안의 두 조건문의 위치가 바뀌면 한번더 카운트가 되어서 틀리게 된다.
  2. if min_time == 0일때 count += 1을 해주면 문제가 틀린다.

1번 문제 이유

두 조건문의 위치가 바뀌면 처음에 min_time에 times 값이 들어가고 나서 times와 min_time이 같은지 비교하면 한번더 카운트가 되기 때문에 더블 카운트가 된다.

2번 문제 이유

만약 처음부터 수빈이와 동생의 위치와 같다면, times가 0인 상태로 x==K이기 때문에 count가 증가하고, 그 다음엔 min_time이 0이기 때문에 더블 카운트가 된다.

75%에서 틀렸다고 표시된다면, 그건 수빈이와 동생의 위치가 같을 때 값이 제대로 출력이 안되는 이유일 가능성이 높다.

2차 수정 코드

# 백준 12851번 숨바꼭질 2

# 읽는 속도 효율화
import sys
input = sys.stdin.readline

# 큐 모듈 import
from collections import deque

def BFS(x, times):
    global visited, min_time, count

    queue = deque()
    queue.append((x, times))
    visited[x] = 0 #방문처리

    while queue:
        x, times = queue.popleft()

       # 위치 값이 동생위치에 도달한다면
        if x == K:
            count += 1
            min_time = visited[x]
            
        for nx in [x-1, x+1, x*2]:
            if 0 <= nx <= MAX and (visited[nx] == -1 or visited[nx] == times + 1):
                visited[nx] = times +1 #방문처리: 최소거리(시간)을 기록
                queue.append((nx, times+1))

# 0. 입력 및 초기화
MAX = 100000

N, K = map(int, input().split()) # N수빈 K동생
visited = [-1] * (MAX+1)

min_time = 0 # 최단 시간 저장
count = 0 # 최단 시간 경로 카운트

# 1. BFS호출
BFS(N, 0)

# 2. 출력
print(min_time)
print(count)

애초에 빙빙돌아서 K에 도착할 수가 없음. visited[nx] == times + 1 조건문 때문에 최단 경로로만 K에 도달할 수 있다. 그래서 간단하게 2차 수정코드로 작성하면 문제를 해결할 수 있다.

이번 문제는 상당히 애를 먹었다. 위에서 말했듯이 visited를 일회성이 아닌 저런 방식으로 사용하는 걸 이해하는 게 너무 어려웠다. 그래도 포기하지 않고, 이해하려고 노력하니 안되지는 않았다. 다른 사람들이 블로그를 쓴 것을 보면 엄청 똑똑한 건지 그냥 이해하지 않고 대충 넘긴건지 모르겠지만, 내 방식을 고수해야겠다.

흔적

profile
황준성
Make progress
이전 포스트

[백준_Python]

다음 포스트

[백준_Python] 13913번 숨바꼭질 4 [골드 4]

0개의 댓글