[코테] 0-1 BFS (숨바꼭질 3, 알고스팟)

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

숨바꼭질 3

 

문제설명 : 현재 위치 n과 가야할 위치k가 주어집니다. 현재 위치에서 +1 또는 -1 을하는데 걸리는 시간은 1이고 현재위치 x에서 2x로는 이동시간이 걸리지 않습니다. k위치로 가는 가장빠른 시간을 구하시오.

 

문제 난이도: 골드5

 

첫번째 시도:

from collections import deque
n,k = map(int,input().split())

def bfs():
    q =deque([[n,0]])
    while q:
        cur,t = q.popleft()
        if cur<0 or cur>2*k:
            continue
        if cur==k:
            return t
        q.append([cur-1,t+1])
        q.append([cur+1,t+1])
        q.append([2*cur,t])

print(bfs())

첫번째 시도는 아무것도 넣지않은 순수 bfs로 논리자체는 언젠가 답에 다다르게 되지만 시간t가 막 섞이게 되어 제한이 없기 떄문에 그게 최소답인지 확언할 수 없으며 시간복잡도도 한번 q에 들어갈때마다 3제곱씩 증가하므로 기하급수적으로 늘어나게 됩니다. 결국 큐에 너무많은 데이터가 쌓여 시간초과에 가지도 못하고 메모리 초과가납니다.

 

두번쨰 시도:

from collections import deque
import heapq as hp
n,k = map(int,input().split())

def bfs():
    q =[[0,n]]
    while q:
        t,cur = hp.heappop(q)
        if cur<0 or cur>2*k:
            continue
        if cur==k:
            return t
        hp.heappush(q,[t+1,cur-1])
        hp.heappush(q,[t+1,cur+1])
        hp.heappush(q,[t,2*cur])

print(bfs())

이번엔 우선순위큐를 활용해 시간을 단축하고자 했습니다. 이렇게되면 t가 적은것을 우선으로 하기때문에 무조건 답에는 도착하지만 heappush,heappop의 시간복잡도는 O(log n)이되므로 역시 시간초과에 걸리게됩니다.

 

세번째 시도:

from collections import deque
n,k = map(int,input().split())
visited=[0]*(max(n,k)*2)
def bfs():
    q =deque([[0,n]])
    if n>=k:
        if n==k:
            return 0
        else:
            return n-k
    while q:
        t,cur = q.popleft()
        if cur<0 or cur>2*k or visited[cur]:
            continue
        if cur==k:
            return t
        visited[cur]=1
        q.append([t+1,cur-1])
        q.append([t+1,cur+1])
        q.appendleft([t,2*cur])

print(bfs())

지금까지의 알고리즘의 단점은 중복으로 인해 기하급수적으로 가짓수가 늘어난다는 점 입니다. 가령 1에서 시작했을때 1+1로 2로가나 1*2로 2로가나 2라는 숫자에 가게되는데, 이를 처리하지 않기 떄문에, 앞에서 방문한곳에는 방문하지 않게 visited를 만들어 놓고, 만약 여러개의 크기를 갖는 유동적인 값을 가지는 리스트에서 대소비교를 하려면 우선순위큐가 좋지만, 지금처럼0 - 1, 즉 크기의 변화가 일정할 경우 0은 리스트의 앞쪽에 appendleft로 1은 뒤쪽으로 append시킬경우, t가 한번커진이후에 그보다 작아질 순 없으므로 논리적으로 항상 t가 가장 작은 경우부터 시도할 수 있게되어 O(1)에 시간복잡도로 해결할 수 있게 됩니다.

 

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

문제설명 : m x n의 0과1을 가지는 2차원 배열에서 0은 길을 1은 벽을 의미합니다. (1,1)에서 시작하여 (n,m)으로 이동하기 위해 벽을 최소 몇개를 부수어야 하는지 출력하세요.

 

난이도 : 골드4 

 

첫번째 제출:

import sys
input = sys.stdin.readline
from collections import deque
m,n = map(int,input().split())
arr = [input().rstrip() for _ in range(n)]
visited = [[[0]*m for _ in range(n)] for _ in range(m+n-1)]
dy = [-1,0,1,0]
dx = [0,1,0,-1]

def go(lim):
    q= deque([[0,0,0]])
    while q:
        y,x,b = q.popleft()
        if (y,x)==(n-1,m-1):
            return b
        visited[lim][y][x]=1
        for i in range(4):
            ny=y+dy[i]
            nx=x+dx[i]
            if 0<=ny<n and 0<=nx<m :
                if visited[lim][ny][nx]:
                    continue
                elif arr[ny][nx]=='0':
                    q.append([ny,nx,b])
                elif lim>b:
                    #코인이 있음
                    q.append([ny,nx,b+1])
    return -1

for i in range(n+m-2):
    if go(i)!=-1:
        print(i)
        break

 

의도는 벽을 부술수 있는 기회를 0부터 올려서 0일때 가보고 없으면 하나씩 올려 처음부터 진행했습니다. 시간초과가 떳고 이유는 갔던곳을 계속 방문하고 있기 때문입니다. 가령 (5,5)까지 벽이없어 그냥 갈수있다면, 이를 기회가 올라갈때마다 처음가는길 처럼 다시 오릅니다. 이를 개선해야합니다.

 

두번째 제출:

import sys
input = sys.stdin.readline
from collections import deque
m,n = map(int,input().split())
arr = [input().rstrip() for _ in range(n)]
visited = [[0]*m for _ in range(n)]
dy = [-1,0,1,0]
dx = [0,1,0,-1]

def solution():
    q=deque([[0,0,0]])
    while q:
        y,x,k = q.popleft()
        if (y,x)==(n-1,m-1):
            return k
        visited[y][x] = 1
        for i in range(4):
            ny=y+dy[i]
            nx=x+dx[i]
            if 0<=ny<n and 0<=nx<m and visited[ny][nx]==0:
                if arr[ny][nx]=='1':
                    q.append([ny,nx,k+1])
                else:
                    q.appendleft([ny,nx,k])

print(solution())

똑같이 진행하되, 이번엔 0-1 bfs를 사용하여 벽을 부수지않고 갈수있는곳을 다 가보고, 그다음  벽을 하나 부숴보고 다시 찾아보고 하는 방식입니다. 역시 아까와 같이 정답이 되는 벽을 부수는 숫자가 1차이로 증가하고 있고 최소를 찾는것이기 때문에 이렇게 하게되면 순서대로 진행할 수 있으며, visited를통해 지금까지 왔던곳은 가지않을 수 있습니다.