백준 1697 - 파이썬

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

1697번: 숨바꼭질

문제 풀이

처음에는 그리디 문제인줄 알고 그리디 방식으로 풀려고 하였다. 떠오른 풀이 방법은 Top down 방식으로 예제 입력값이 5와 17일 때 17부터 숫자를 줄여나가며 정답을 찾는 방식이다. 알고리즘 작동 방식은 다음과 같다.

 

1. -1 or +1 해보고 n과 일치하는지 확인.

2. n과 일치하지 않는다면 짝수인지 홀수인지 확인 (짝수라면 2로 나누고, 홀수면 -1 해주기)

3. 2번 과정을 반복

 

import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())

def solution(n):
  cnt = 0
  q = deque()
  q.append((k, cnt))
  
  while q:
    res, cnt = q.popleft()
    
    if (res + 1) == n or (res - 1) == n:
      return cnt + 1
      
    elif res == n:
      return cnt

    if res % 2 == 0:
      res //= 2
      q.append((res, cnt + 1))

    elif res % 2 == 1:
      res -= 1
      q.append((res, cnt + 1))


print(solution(n))

해당 코드는 입력예제는 전부 맞았지만 시간 초과가 났다. 왜 시간 초과가 났는지 생각해보다가 해당 문제의 질문게시판에 들어가봤고, 나와 비슷한 방식으로 풀어서 시간 초과가 발생하여 질문을 남겨놓은 글을 발견했다. 질문의 답변에는 방문처리를 하지 않아 이미 계산한 것도 중복으로 계산되고 있다고 하였다. 그래서 BFS를 풀때의 전형적인 방법인 방문 처리를 통해 반복되는 계산의 수를 줄여보고자 하였다.

 

방문 처리는 초기값을 0으로 해두고, 방문시 해당 카운트 수가 현재 방문 리스트의 값보다 작으면 입력되도록 하였다.

 

import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())

cnt = 0
q = deque()
q.append((k, cnt))

def solution(n):
  visited = [0] * 100001
  while q:
    res, cnt = q.popleft()
      
    if res == n:
      return cnt

    # elif (res + 1) == n or (res - 1) == n:
    #   return cnt + 1
    if (res + 1) == n:
      return cnt + 1
        
    elif (res - 1) == n:
      return cnt + 1
      
    elif res % 2 == 0:
      res //= 2
      cnt += 1
      if visited[res] == 0 or visited[res] > cnt:
        visited[res] = cnt
        q.append((res, cnt))

    elif res % 2 == 1:
      res -= 1
      cnt += 1
      
      if visited[res] == 0 or visited[res] > cnt:
        q.append((res, cnt))
        visited[res] = cnt


print(solution(n))

결과적으로는 틀렸다는 답을 받았다. 예제 입력뿐만 아니라 질문 게시판에 있는 반례도 다 맞았기에 도무지 왜 틀렸는지 이유를 몰라 멘탈이 나가기 직전이었지만 인내심을 갖고 계속 고민해봤다. 그래서 떠오른 생각은 방문 리스트 안에 카운트 수를 넣지 말고 단순히 True, False로만 구분하는것이 더 나을거 같다는 생각이 들었고, -1과 +1하는 조건문이 두번이나 진행되는데 이것도 합쳐보기로 했다.

 

import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())

cnt = 0
q = deque()
q.append((k, cnt))

MAX = 100000

def solution(n):
  visited = [False] * (MAX + 1)
  while q:
    res, cnt = q.popleft()
      
    if res == n:
      return cnt

    if res % 2== 0:
      if visited[res//2] == False:
        q.append((res//2, cnt+1))
        visited[res//2] = True
    if 0 <= res + 1 <= MAX and visited[res+1] == False:
      q.append((res+1, cnt + 1))
      visited[res + 1] = True
    if 0 <= res - 1 <= MAX and visited[res-1] == False:
      q.append((res-1, cnt + 1))
      visited[res - 1] = True

print(solution(n))

결국, 정답을 받아냈다. 입력된 처음 값이 짝수라면 바로 2로 나눠주고 그렇지 않다면 +1과 -1을 하여 방문이 되어있지 않다면 방문처리 후 큐에 추가해주는 형태이고, 큐에 들어오는 모든 값을 출력해보면 아래와 같다.

 

5 17
deque([(17, 0)])
deque([(18, 1), (16, 1)])
deque([(16, 1), (9, 2), (19, 2), (17, 2)])
deque([(9, 2), (19, 2), (17, 2), (8, 2), (15, 2)])
deque([(19, 2), (17, 2), (8, 2), (15, 2), (10, 3)])
deque([(17, 2), (8, 2), (15, 2), (10, 3), (20, 3)])
deque([(8, 2), (15, 2), (10, 3), (20, 3)])
deque([(15, 2), (10, 3), (20, 3), (4, 3), (7, 3)])
deque([(10, 3), (20, 3), (4, 3), (7, 3), (14, 3)])
deque([(20, 3), (4, 3), (7, 3), (14, 3), (5, 4), (11, 4)])
deque([(4, 3), (7, 3), (14, 3), (5, 4), (11, 4), (21, 4)])
deque([(7, 3), (14, 3), (5, 4), (11, 4), (21, 4), (2, 4), (3, 4)])
deque([(14, 3), (5, 4), (11, 4), (21, 4), (2, 4), (3, 4), (6, 4)])
deque([(5, 4), (11, 4), (21, 4), (2, 4), (3, 4), (6, 4), (13, 4)])

 

위 출력값을 보면 이미 계산이 진행된 값은 중복 계산되지 않고 있다. 떠올린 알고리즘의 근본적인 형태는 같지만 방문처리와 중복된 조건문을 없애면서 코드를 좀더 깔끔하고 효율적이게 만든것이 다른점인거 같다. 추가적으로 res의 계산값이 0보다 크거나 같고 MAX 보다는 작거나 같다는 조건을 넣어줘야 런타임에러가 안 난다.

 

또 다른 풀이

내가 푼 방식 외에 다른 방식이 있나 싶어 구글링을 해 봤다. 대부분의 사람들은 Bottom Up 방식으로 풀었다.

from collections import deque

MAX = 10 ** 5
dist = [0] * (MAX + 1)
n, k = map(int, input().split())

def bfs():
  q = deque()
  q.append(n)

  while q:
    x = q.popleft()
    if x == k:
      print(dist[x])
      break
    for nx in (x-1, x + 1, x * 2):
      if 0 <= nx <= MAX and not dist[nx]:
        dist[nx] = dist[x] + 1
        q.append(nx)

bfs()

x-1, x+1, x*2를 반복문을 통해 계산을 하고, 계산한 값을 큐에 넣은 후 방문처리와 함께 카운트를 증가시켰다. 더 자세한 설명은 해당 글을 참고하면 좋을거 같다.

 

이번 문제를 푸는데 3일이 걸렸는데, 중간에 그냥 포기하고 답을 찾아볼까 하는 생각도 들긴 했지만 포기하지 않고 결국 스스로 답을 찾아내어 너무 기뻤다. 이번 문제를 풀면서 느낀 점은 똑같은 답을 찾아내더라도 어떻게 코딩하느냐에 따라 효율적인 측면에서 매우 달라진다는 것을 알았다. 또한 BFS에서 핵심은 방문처리를 통해 중복계산을 피하는 것인거 같다. 아직 부족한 점이 많지만 꾸준히 풀며 노력해야 되겠다.