파이썬 알고리즘 194번 | [백준 5014번] 스타트링크 - bfs

194. 스타트링크

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

• bfs

2) 코딩 설명

<내 풀이>

import sys
from collections import deque

F, S, G, U, D = map(int,sys.stdin.readline().rstrip().split())
#총 F층으로 이루어진 고층 건물에 사무실이 있고, 
#강호가 지금 있는 곳은 S층이고,
#이제 엘리베이터를 타고 G층으로 이동하려고 한다.
updown = [U, -D]
impossible = True

def bfs(q) :
    global mini
    global impossible

    while q :
        now = q.pop()
        
        if now[0]==G:
        
            impossible = False
            print(now[1])

        for j in range(2) :
            tmps = now[0]+updown[j]
            if 0<tmps and tmps<F+1 and visited[tmps]==0 : 
                
                visited[tmps]=1
                q.appendleft((tmps, now[1]+1))
       
q=deque()
q.append((S,0))
visited = [0 for _ in range(F+1)]
visited[S]=1
bfs(q)
if(impossible) : print("use the stairs")

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

아래 코드는 내자마자 틀렸다구 한다.

import sys
from collections import deque

F, S, G, U, D = map(int,sys.stdin.readline().rstrip().split())
#총 F층으로 이루어진 고층 건물에 사무실이 있고, 
#강호가 지금 있는 곳은 S층이고,
#이제 엘리베이터를 타고 G층으로 이동하려고 한다.
updown = [U, -D]
impossible = True

def bfs(q) :
    global mini
    global impossible

    while q :
        #print(q)
        now = q.pop()
        
        if now[0]==G:
            #print(now[1])
            impossible = False
            if now[1]<mini:
                mini=now[1]
                break
        for j in range(2) :
            tmps = now[0]+updown[j]
            if 0<tmps and tmps<F+1 and visited[tmps]==0 : 
                #print(j, tmps, visited, now[0], "-", now[1], q)
                visited[tmps]=1
                q.appendleft((tmps, now[1]+1))
                
                
mini=99999
q=deque()
q.append((S,0))
visited = [0 for _ in range(F+1)]
visited[S]=1
cnt=[0 for _ in range(F+1)]
bfs(q)
if(not impossible) : print(mini)
else : print("use the stairs")

2프로에서 틀리는 코드

import sys
from collections import deque

F, S, G, U, D = map(int,sys.stdin.readline().rstrip().split())
#총 F층으로 이루어진 고층 건물에 사무실이 있고, 
#강호가 지금 있는 곳은 S층이고,
#이제 엘리베이터를 타고 G층으로 이동하려고 한다.
updown = [U, -D]
impossible = True

def bfs(q) :
    global mini
    global impossible

    while q :
        #print(q)
        now = q.pop()
        
        if now[0]==G:
            #print(now[1])
            impossible = False
            if now[1]<mini:
                mini=now[1]
                break
        for j in range(2) :
            tmps = now[0]+updown[j]
            if 0<tmps and tmps<F+1 and visited[tmps]==0 : 
                #print(j, tmps, visited, now[0], "-", now[1], q)
                visited[tmps]=1
                q.appendleft((tmps, now[1]+1))
                
                
mini=99999
q=deque()
q.append((S,0))
visited = [0 for _ in range(F+1)]
visited[S]=1
cnt=[0 for _ in range(F+1)]
bfs(q)
if(not impossible) : print(mini)
else : print("use the stairs")

2프로 틀린 이유 : 가히 충격적

mini 99999 로 설정했던게 , now[1]이 99999보다 큰 경우가 존재,,,!!!

(1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000)
100000인 경우도 존재하므로,,, 흑흑

(+)

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

시간초과

import imp
import sys
from itertools import deque()
sys.setrecursionlimit(10**6)
F, S, G, U, D = map(int,sys.stdin.readline().rstrip().split())
#총 F층으로 이루어진 고층 건물에 사무실이 있고, 
#강호가 지금 있는 곳은 S층이고,
#이제 엘리베이터를 타고 G층으로 이동하려고 한다.
visited = [0 for _ in range(F+1)]
impossible = False

def bfs(s, cnt) :
    global mini
    global impossible
    if s==G:
        impossible = True
        if mini>cnt :mini=cnt; return

    elif s<1 : return
    elif s>F : return
    else : 
        #print(s,cnt)
        tmps1=s+U
        tmps2=s-D
        if tmps1 <=F and visited[tmps1] == 0 :
            visited[tmps1]=1
            bfs(tmps1, cnt+1)
            visited[tmps1]=0
        if tmps2>0 and visited[tmps2] == 0 :
            visited[tmps2]=1
            bfs(tmps2, cnt+1)
            visited[tmps2]=0
mini=99999
bfs(S, 0)
if(impossible) : print(mini)
else : print("use the stairs")

2프로에서 틀림

import sys
from collections import deque
sys.setrecursionlimit(10**6)
F, S, G, U, D = map(int,sys.stdin.readline().rstrip().split())
#총 F층으로 이루어진 고층 건물에 사무실이 있고, 
#강호가 지금 있는 곳은 S층이고,
#이제 엘리베이터를 타고 G층으로 이동하려고 한다.
visited = [0 for _ in range(F+1)]
impossible = True

def bfs(q, cnt) :
    global mini
    global impossible
    
    while q :

        now = q.pop()
        
        if now==G:
            impossible = False
            if cnt<mini:
                mini=cnt
                return
            
        elif now+U<F+1 and visited[now+U]==0: 
            visited[now+U]=1
            #print(q)
            q.append(now+U)
            #print(q, "q is here")
            bfs(q, cnt+1)
            

        elif now-D<F+1 and visited[now-D]==0: 
            visited[now-D]=1
            q.append(now-D)
            bfs(q, cnt+1)
            
        
mini=99999
q=deque()
q.append(S)
bfs(q, 0)
if(not impossible) : print(mini)
else : print("use the stairs")

<반성 점>

• 범위,,, 범위를 잘 보자

<배운 점>