[Python] 백준 1697번 - 숨바꼭질

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

1697번: 숨바꼭질

bfs......... 나 bfs 진짜 싫어.......

과제할 때 결국 못 풀고 그냥 제출한 경험이 있음.... 번아웃까지 야기했던 그 문제.... bfs.......

 

사실 이 문제 접근하면서 bfs를 코드로 짜는 방법을 드디어 이해한 것 같다.

큐에 넣고 빼고 하면서 이걸 어떻게 한다는 건지 학기 중에는 이해하지 못했다.

 

그래서 실버1이어도 긴장하면서 풀었는데.. 헛되지 않았다.. 좀 더 긴장했어도 됐을 듯..

자꾸 인덱스 에러가 나서 구글링도 하면서 다른 사람들 코드랑 비교도 해봤는데 계속 인덱스 에러가 난다....

나 이미 8번이나 제출했는데 8번 내내 인덱스에러다! 역대급이야.

 

원래 문제 못 풀면 글 안 쓰는데 지금 너무 짜증나서 일단 올려놓고 나중에 수정해야겠어.

하루에 한 문제라도 풀으려고 오후 느지막이 책상 앞에 앉았다가 괜히 열만 받았다.

bfs 진짜... 싫어... 열심히 해야지...

 

 

#인덱스에러........

import sys
from collections import deque

def bfs(v):
    q = deque([v]) #큐 구현을 위해 deque 사용
    while q:
        v = q.popleft()
        if v == k:
            return visited[v]
        for i in (v-1, v+1, 2*v):
            if not visited[i] and 0 <= i <= 100000:
                visited[i] = visited[v] + 1
                q.append(i)

n, k = map(int, sys.stdin.readline().split())
visited = [0 for i in range(100001)]
print(bfs(n))

 

 

---

 

 

와하하 대박 동아리 회원 한 분이 풀어주셨다......................................

bfs 함수 안에 if문에서 and로 복수 조건 줄 때 조건을 순차적으로 확인하는구나.. 동시에 확인이 아니라...

그래서 일단 not visited[i] 인 걸 확인하고 넘어갔는데 0<=i<=100000이 아니라서 인덱스가 없는 거였구나................... 맞나.. 쨌든 이런 것 같아.....

 

간만에 제대로 열 받았었는데 다행이다 감사합니다.....

꼭 기억하자 and로 조건 주면 순차적으로 확인.

 

 

#success

import sys
from collections import deque

def bfs(v):
    q = deque([v]) #큐 구현을 위해 deque 사용
    while q:
        v = q.popleft()
        if v == k:
            return visited[v]
        for i in (v-1, v+1, 2*v):
            if 0 <= i <= 100000 and not visited[i]:
                visited[i] = visited[v] + 1
                q.append(i)

n, k = map(int, sys.stdin.readline().split())
visited = [0 for i in range(100001)]
print(bfs(n))

 

ㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎ

 

 

---

 

 

#220128

처음에 이상한 방법으로 풀다가 이렇게 하면 초(sec)를 찾을 때 너무 복잡해진다는 사실을 깨닫고 처음부터 다시 풀었다.

지난 번에 푼 코드랑 거의 똑같다. 신기하군(?)

 

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

def hideseek(start):
    q = deque()
    q.append(start)
    visited[start] = 1
    while q:
        c = q.popleft() #current
        if c == k:
            return visited[c] - 1
        for i in (c-1, c+1, 2*c):
            if 0 <= i <= 100000 and not visited[i]:
                visited[i] = visited[c] + 1
                q.append(i)

n, k = map(int, input().split())
visited = [0 for _ in range(100001)]
print(hideseek(n))

 

한 번에 성공 ~