파이썬 알고리즘 198번 | [백준 12851번] 숨바꼭질2 -bfs ****

198. 숨바꼭질2

1) 어떤 전략(알고리즘)으로 해결?

• bfs

주의할 점 :

도착점이 아닌 점에서 최단 시간으로 같은 점을 여러 번 방문하였을 때 방법을 세는 부분 필요 (백준 질문)

• 기존에 나는 한번 visited 되면 다시는 안 찾아가게 했음
• 그렇게 되면 입력값이 (1, 3 ) 인 경우에

2) 코딩 설명

<내 풀이>

• 도저히 알 수 없어서 https://2hs-rti.tistory.com/7 분의 풀이를 보고 참고 및 이해한 후 코드를 작성하여 통과하였다.
  

from collections import deque
import sys
n,k= map(int, sys.stdin.readline().rstrip().split())

q=deque()
q.append((n, 0)) #시작 위치, 횟수 (초기값은 0으로 conut)
cnt=0 
visited=[-1 for _ in range(100001)] # 방문 여부 및 방문 최소 횟수를 기록 
visited[n]=0 #-1이 아닌 방문 여부 및 
case=[-1,1]

while q :
    now = q.pop()
    loc=now[0] ; time=now[1]

    if loc==k: #k 만나면 cnt 갱신 
        cnt+=1

    for i in range(3) :
            if i==2: #순간이동 경우 
                tmploc=loc*2
            else : # -1 , 1 더하는 경우 
                tmploc=loc+case[i]
            
            if 0<=tmploc<100001 and (visited[tmploc]==-1 \
                or visited[tmploc]==time+1):
                # 주의! 단순히 한번 방문했다고 무시하면 안됨
                # 이미 방문됐더라도 -
                # 방문된 아이의 최소 시간과 지금 내 시간이 같으면
                # 나도 q에 들어가기 가능 
                visited[tmploc]=time+1 # visited[tmploc]==-1 경우를 고려한 코드 
                q.appendleft((tmploc, time+1))

print(visited[k]) 
#visited에는 최소 횟수들이 기록돼있으니 k의 최소횟수 데려오면 됨 
print(cnt)

<내 틀렸던 풀이, 문제점>

7 프로에서 틀림

from collections import deque
import sys
n,k= map(int, sys.stdin.readline().rstrip().split())

q=deque()
q.append((n,0))
mini=1000001
cnt=0
visited=[0 for _ in range(100001)]
visited[n]=1

while q :

    now = q.pop()
    #print("now",now) ;print(q)
    loc=now[0] ; time=now[1]
    
    if loc==k:
        if mini>time:mini=time ; cnt=1; 
        elif time==mini: cnt+=1
        if mini<1000001:
            visited[mini]=0

    if 0<=loc-1<100001 and visited[loc-1]==0:
            visited[loc-1]=1
            if loc-1==k:
                if mini>time+1:mini=time+1; cnt=1; 
                elif time+1==mini: cnt+=1
                visited[mini]=0
            q.appendleft((loc-1, time+1))

    if 0<=loc+1<100001 and visited[loc+1]==0:
            visited[loc+1]=1
            if loc+1==k:
                if mini>time+1:mini=time+1; cnt=1; 
                elif time+1==mini: cnt+=1
                visited[mini]=0
            q.appendleft((loc+1, time+1))
            
    if 0<=loc*2<100001 and visited[loc*2]==0:
            visited[loc*2]=1
            if loc*2==k:
                if mini>time+1:mini=time+1; cnt=1; 
                elif time+1==mini: cnt+=1
                visited[mini]=0
            q.appendleft((loc*2, time+1))
            
print(mini)
print(cnt)

50%에서 틀리는 코드

from collections import deque
import sys
n,k= map(int, sys.stdin.readline().rstrip().split())

q=deque()
q.append((n,0))
mini=1000001
cnt=0
visited=[0 for _ in range(100001)]
visited[n]=1

while q :

    now = q.pop()
    #print("now",now) ;print(q)
    loc=now[0] ; time=now[1]

    if 0<=loc-1<100001 and visited[loc-1]==0:
            visited[loc-1]=1
            if loc-1==k:
                if mini>time+1:mini=time+1; cnt=1; 
                elif time+1==mini: cnt+=1
                visited[mini]=0
            q.appendleft((loc-1, time+1))

    if 0<=loc+1<100001 and visited[loc+1]==0:
            visited[loc+1]=1
            if loc+1==k:
                if mini>time+1:mini=time+1; cnt=1; 
                elif time+1==mini: cnt+=1
                visited[mini]=0
            q.appendleft((loc+1, time+1))
            
    if 0<=loc*2<100001 and visited[loc*2]==0:
            visited[loc*2]=1
            if loc*2==k:
                if mini>time+1:mini=time+1; cnt=1; 
                elif time+1==mini: cnt+=1
                visited[mini]=0
            q.appendleft((loc*2, time+1))
            
print(mini)
print(cnt)

흠..

from collections import deque
import sys
n,k= map(int, sys.stdin.readline().rstrip().split())

q=deque()
q.append((n,0))
mini=1000001
cnt=0
visited=[0 for _ in range(100001)]
visited[n]=1

while q :
    now = q.pop()
    
    loc=now[0] ; time=now[1]
    

    if 0<=loc-1<100001 and visited[loc-1]==0:
            visited[loc-1]=1
            if loc-1==k:
                if mini>time+1:mini=time+1; cnt=1; visited[mini]=0
                elif time+1==mini: cnt+=1;visited[mini]=0
            q.appendleft((loc-1, time+1))

    if 0<=loc+1<100001 and visited[loc+1]==0:
            visited[loc+1]=1
            if loc+1==k:
                if mini>time+1:mini=time+1; cnt=1;visited[mini]=0 
                elif time+1==mini: cnt+=1;visited[mini]=0
            q.appendleft((loc+1, time+1))
            
    if 0<=loc*2<100001 and visited[loc*2]==0:
            visited[loc*2]=1
            if loc*2==k:
                if mini>time+1:mini=time+1; cnt=1;visited[mini]=0
                elif time+1==mini: cnt+=1;visited[mini]=0
            q.appendleft((loc*2, time+1))
            
print(mini)
print(cnt)

OING ~~ 39프로에서 시간초과

from collections import deque
import sys
n,k= map(int, sys.stdin.readline().rstrip().split())

q=deque()
q.append((n, 0))
mini=1000001
cnt=0
visited=[0 for _ in range(100001)]
visited[n]=1
case=[-1,1]

while q :
    now = q.pop()
    loc=now[0] ; time=now[1]
    
    for i in range(3) :
            if i==2:
                tmploc=loc*2
            else :
                tmploc=loc+case[i]
            #print(tmploc, q)

            if 0<=tmploc<100001 and visited[tmploc]==0:
                visited[tmploc]=1

                if tmploc==k:
                        if mini>time+1:mini=time+1; cnt=1; visited[tmploc]=0
                        elif time+1==mini: cnt+=1;visited[tmploc]=0
                        
                if tmploc==2*loc: visited[tmploc]=0
                q.appendleft((tmploc, time+1))

print(mini)
print(cnt)

<반성 점>

<배운 점>

• visited에 센 값을 넣어주는 것도 가능하다. !!!!
• 단순히 방문만 했다고 끝이 아니었던 문제,
• visited 에 최소시간을 기록해놓고 진행하는 문제 , 방문됐더라도 지금 아이의 방문 자리의 최소시간이 지금 아이의 시간이랑 같으면 q에 넣어주기 가능