[삼성SW역량][Python/BOJ] 백준 19238 스타트택시(BFS+구현)

 

 

 

 

 

 

드디어...! 

나 혼자 골드 3 문제를 풀었다!

 

 

 

문제 : 

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.

 

 

---

 

해설 : 

 

0. 승객만큼 반복한다.

     1-1. 택시의 위치에서 모든 위치까지의 거리를 구한다.(벽 제외)(BFS이용 == 최단거리)

     1-2. 거리가 짧고, x,y가 작은 순으로  정렬한다. 

     1-3. 최적의 승객을 찾은 후 승객까지의 거리를 energy에서 뺀다.

 

     2-1. 그 승객의 위치에서 목적지의 위치까지의 거리를 구한다.(벽 제외)(BFS이용 == 최단거리)

     2-2. 목적지까지의 최소거리를 찾은 후 거리를 energy에서 뺀다. 그리고 두배만큼 더한다. 

     2-3. 그 후 목적지를 지금의 위치로 지정한다. 

3. energy를 출력한다. 

 

 

 

중간중간에 승객에게로 가지 못하거나 에너지가 부족할 경우 -1을 출력한후 끝낸다.

 

 

---

 

 

코드 : 

from collections import deque
from itertools import combinations as c 


dx = [1,0,-1,0]
dy = [0,1,0,-1]
            
     
            
if __name__=="__main__" :
    n,m,energy = map(int,input().split())
    mp = [list(map(int,input().split())) for i in range(n)]
    # 운전을 시작하는 칸 
    x,y = map(int,input().split())
    x,y = x-1, y-1 
    guest = [list(map(int,input().split())) for i in range(m)]
    
    # 모든 승객을 완료할 때까지 
    for i in range(m) :
        
        vis = [[-1]*n for i in range(n)]
        d = deque([[x,y]])
        vis[x][y] = 0
        while d :
            x,y =d.popleft()
            for i in range(4) :
                nx,ny = x + dx[i], y + dy[i]
                # 벽이 아니고 방문한적이 없을 때 
                if 0<=nx<n and 0<=ny<n and mp[nx][ny]!= 1 and vis[nx][ny]==-1 :
                    d.append([nx,ny])
                    # 방문 표시 & 거리 표시 
                    vis[nx][ny]= vis[x][y] +1 
                    
        ans = int(1e9)
        dest = []
        for idx in range(len(guest)) :
            x,y,nx,ny = guest[idx]
            # 모든 손님을 이동시킬 수 X 
            if vis[x-1][y-1] == -1 :
                print(-1)
                exit(0)
            dest.append([idx, vis[x-1][y-1],x-1,y-1])
        
        # 거리 , 행 , 열이 작은 순으로 정렬 
        dest.sort(key = lambda x : (x[1],x[2],x[3]))
        destination = dest[0]
        pos = guest.pop(destination[0])
        
        
        # 거리만큼 에너지를 빼준다. 
        if energy >= destination[1] :
            energy -= destination[1]
        else :
            print(-1)
            exit(0)
        
        x,y,ndx,ndy = pos
        x,y,ndx,ndy = x-1,y-1,ndx-1,ndy-1 
        vis = [[-1]*n for i in range(n)]
        d = deque([[x,y]])
        vis[x][y] = 0
        while d :
            x,y =d.popleft()
            for i in range(4) :
                nx,ny = x + dx[i], y + dy[i]
                # 벽이 아니고 방문한적이 없을 때 
                if 0<=nx<n and 0<=ny<n and mp[nx][ny]!= 1 and vis[nx][ny]==-1 :
                    d.append([nx,ny])
                    # 방문 표시 & 거리 표시 
                    vis[nx][ny]= vis[x][y] +1 
                # 거리만큼 에너지를 빼준다. 
        if energy >= vis[ndx][ndy] :
            energy -= vis[ndx][ndy]
            energy += vis[ndx][ndy]*2 
        else :
            print(-1)
            exit(0)
        x,y = ndx,ndy
    print(energy)