백준 18232 텔레포트정거장 파이썬

링크 : https://www.acmicpc.net/problem/18232

문제

그냥 BFS만 돌리면 되지않을까?

딱히 가중치가 있지도않고, 그냥 노드로 이동하는 문제인것같다.

텔레포트가 혹시 단방향인가? 에 대한 생각을 해봣는데, 점 x의 텔레포트와 점 y의 텔레포트가 연결되어있다는 뜻 에서 양방향이라고 생각했다

테스트케이스

# N, M = 10 ,3
# S, E = 2, 5
# graph = [[], [6, 3], [8], [1], [], [], [1], [], [2], [], []]

메모리 초과되는 소스코드

import sys 
input = sys.stdin.readline 
N, M = map(int, input().split())
S, E = map(int ,input().split())
graph = [ [] for _ in range(N+1)]
for _ in range(M) :
    x, y = map(int ,input().split())
    graph[x].append(y)
    graph[y].append(x)

from collections import deque 
Q = deque()
Q.append((S,0))

while Q : 
    location, cost = Q.popleft()

    if location == E : 
        print(cost)
        break

    for i in [location+1, location-1] :
        if 1<i<N : 
            Q.append((i,cost+1))

    if graph[location] :
        for i in graph[location] : 
            Q.append((i, cost+1))

왜 메모리 초과가 날까?
이 소스코드의 문제점은 ‘노드의 방문여부와 상관없이 큐에서 보내면 다시 방문해야한다는 ‘것 때문이다

가령 시작지점이 2이고, 1→ 3으로 가는 텔레포트가 있다면
2 → (-1) → 1 → (텔레포트) → 3 → (-1) → 2 이런식으로 무한루프를 돌게되서
결국 방문처리가 의미가없게되더라

그래서 해결방법으로는
이번엔 어떤 부분을 추가해줬냐면 dp[]배열을 선언해서
이미 방문한 노드면 새로운 큐를 돌게 만들었다

이번엔 시간초과 나는 소스코드

import sys 
input = sys.stdin.readline 
N, M = map(int, input().split())
S, E = map(int ,input().split())
graph = [ [] for _ in range(N+1)]
for _ in range(M) :
    x, y = map(int ,input().split())
    graph[x].append(y)
    graph[y].append(x)

from collections import deque 
Q = deque()
Q.append((S,0))

dp = [int(1e7) for _ in range(N+1)] #무지하게 큰 값으로 초기화 
dp[S] = 0 

while Q : 
    location, cost = Q.popleft()

    #종료조건
    if location == E : 
        print(cost)
        break

    if cost > dp[location] : 
        continue 
    else : 
        dp[location] = cost 

    for i in [location+1, location-1] :
        if 1<i<N : 
            Q.append((i,cost+1))

    if graph[location] :
        for i in graph[location] : 
            Q.append((i, cost+1))

근데 시간초과가 나더라
왜 시간초과가 날까를 생각해봤는데 if cost > dp[location] 의 위치가 문제였던것같다

이런식으로 dp테이블을 활용해서 하는 BFS는 Queue에 값을 넣어줄때 append() 메소드를 쓰는데
이게 O(N)인가? 그렇다.
앞에서부터 쭉쭉쭉 연결되어있는 리스트에서 맨 뒤로 가야하기때문에 O(N)이 든다

근데 O(N) 들여서 꾸역꾸역 리스트 뒤에 붙혀놨더니, 이미 방문한 노드라고 continue를 돌린다?
이만한 낭비가 없다. 그래서 애초에 무지성으로 추가하지말고, 넣을지말지를 확인하고 넣으면 좋을것같다

문제없는 코드

# N, M = 10 ,3
# S, E = 2, 5
# graph = [[], [6, 3], [8], [1], [], [], [1], [], [2], [], []]

import sys 
input = sys.stdin.readline 
N, M = map(int, input().split())
S, E = map(int ,input().split())
graph = [ [] for _ in range(N+1)]
for _ in range(M) :
    x, y = map(int ,input().split())
    graph[x].append(y)
    graph[y].append(x)

from collections import deque 
Q = deque()
Q.append(S)

dp = [int(1e7) for _ in range(N+1)] #무지하게 큰 값으로 초기화 
dp[S] = 0 

while Q : 
    location = Q.popleft()

    #종료조건
    if location == E : 
        print(dp[location])
        break

    for i in [location+1, location-1] :
        if (1<=i<=N) and (dp[i] > dp[location]+1): 
            Q.append(i)
            dp[i] = dp[location]+1 

    if graph[location] :
        for i in graph[location] :
            if (dp[i] > dp[location]+1) :  
                Q.append(i)
                dp[i] = dp[location]+1
    # print(dp)

자잘하게 틀렸던 iteration범위를 재설정 해줬다

그리고 dp[i] > dp[location]+1 로 ‘이 노드를 가도 되는지' 확인 후에 BFS()에 넣었다