알고리즘 풀이 백준(BOI) 19238) 스타트 택시 (Python)

백준(BOI) 19238 - 스타트 택시

---

 

 

19238번: 스타트 택시

 

[문제풀이]

 

 

 택시가 승객들을 태우고 승객들의 목적지로 이동하는 문제이다. 승객들은 각각 고유한 자리에 존재하며 목적지 또한 고유하다.

 

택시는 이동 중 기름을 소모하며 기름이 다 떨어지면 운행을 종료한다. 택시가 승객을 성공적으로 목적지에 데려다주면 소모한 기름의

 

2배를 충전한다. 택시가 승객을 태우러 갈 수 없는 경우도 존재한다. 택시는 현재 택시의 위치에서 가장 가까운 승객을 다음 승객으로

 

선정한다. 이후 승객을 모두 태워서 목적지에 데려다주는 데 성공했으면 현재 남은 택시의 기름의 양을 출력하고 그렇지 않으면 -1을 

 

출력한다.

 

 

최단거리를 이용하는 문제이므로 승객을 선정할 때 BFS로 풀었다. 이 외에는 별 다른 특이한 점은 없었고 문제에서 주어지는 로직대로

 

시뮬레이션했다. 단, 주의할 점은 문제를 읽다 보면 승객을 태우러 갈 때 소비한 연료량과 태운 승객을 데리고 목적지로 갈 때 소비한 

 

연료량 두 가지 경우가 있는데, 이때 기름을 두 배로 충전해 주는 기름의 양은 후자에만 적용된다는 것이다.

 

또한 기름의 양이 초깃값은 최대 500,000 이고 이 후로 충전될 수 있는 양이 무한하므로 기름의 양으로 어떤 승객에게 도달할 수 있는

 

지 없는지를 판별하게 되면 시간초과가 날 수 있으므로 주의해야 한다.

 

 

필자는 문제에서 주어진 로직을 다음과 같이 구현해서 풀었다.

#1. 손님이 존재하는지 확인한다. 
 - isDone() 메소드 안에 구현하였다. 종료 조건이므로 While문 안에서 가장 먼저(혹은 마지막에) 체크해줘야 한다.
 필자는 택시가 성공적으로 고객을 목적지까지 데려다 주면 해당 고객의 원래 위치를 그리드상에서 -1로 표시해줌으로써 구현하였다. -1의 개수가 M(손님의 수)와 맞다면 True를 리턴한다. isDone이 True를 리턴하면 프로세스는 종료된다.

제출하고 나니 막상 메소드를 따로 만들 필요도 없이 변수 하나를 만들어 count만 up 시켜줘도 되는 거였다...



#2. 존재하는 손님 중 가장 가까운 손님의 위치를 파악한다. 최단거리의 손님이 두 명 이상일 경우에는 행과 열의 값이 낮은 손님을 우선으로 한다.
 - findNext(row, col) 메소드에 구현하였다.
 먼저 현재 택시의 좌표를 큐에 넣어주고 택시의 좌표로부터 다른 모든 칸에 대한 거리 값을 계산한다(BFS).
그리고 메소드의 아랫부분에서 최단거리인 손님과 손님들의 우선순위를 파악하고 해당 손님의 현재 좌표와 목적지의 좌표, 그리고 소모된 연료량을 리턴한다. 



#3. 선정된 손님에게 이동하고 목적지로 이동한다.
- move(now_row, now_col, destination_row, destination_col, fuel) 메소드에 구현하였다.
 마찬가지로 최단거리로 이동하므로 BFS로 구현하였다. 목적지까지의 최단 거리를 리턴한다. 중간에 기름이 떨어졌으면 -1을 리턴한다.



#4. 위 (#3)에서 소비된 연료량의 두배를 충전한다.
- 2에서 소비된 연료량은 충전 대상이 아니니 주의하자.


#1~#4를 반복.
루프 문 안에서 기름이 떨어지거나 손님이나 목적지에 도달할 수 없을 경우 -1을 리턴하는 종료 조건을 주었다.

다행히 시간 초과에 걸리지 않고 한 번의 시도만에 통과되었다.

 

 

---

 

 

[전체 소스코드]

 

def isDone():
    global n, m, grid
    count = 0
    for i in range(n):
        for j in range(n):
            if grid[i][j] == -1: count += 1
    if count == m: return True
    else: return False
    
def move(x,y,destx,desty,f):
    global n, s, d, directions, grid
    count = [[-1 for _ in range(n)]for _ in range(n)]
    qu = []
    qu.append([x-1,y-1])
    count[x-1][y-1] = 0
    while qu:
        nowx, nowy = qu.pop(0)
        if nowx == destx -1 and nowy == desty -1 :
            if count[nowx][nowy] <= f : return count[nowx][nowy]
            else: return -1            
        for dx, dy in directions:
            nextx = nowx + dx
            nexty = nowy + dy
            if 0 <= nextx < n and 0 <= nexty < n and count[nextx][nexty] == -1 and grid[nextx][nexty] != 1:
                qu.append([nextx,nexty])
                count[nextx][nexty] = count[nowx][nowy] + 1
    return -1
    
def findNext(x,y):
    global n, s, d, directions, grid
    count = [[-1 for _ in range(n)]for _ in range(n)]
    qu = []
    qu.append([x-1,y-1])
    count[x-1][y-1] = 0
    while qu:
        nowx, nowy = qu.pop(0)
        for dx, dy in directions:
            nextx = nowx + dx
            nexty = nowy + dy
            if 0 <= nextx < n and 0 <= nexty < n and count[nextx][nexty] == -1 and grid[nextx][nexty] != 1:
                qu.append([nextx,nexty])
                count[nextx][nexty] = count[nowx][nowy] + 1   
    minNum = 987654321
    nextx, nexty, c = (22, 22, 0)
    destx, desty = (22, 22)
    for i in range(m):
        sx, sy = s[i]
        dx, dy = d[i]
        if count[sx-1][sy-1] != -1 and count[sx-1][sy-1]  <= minNum and grid[sx-1][sy-1] != -1:
            if count[sx-1][sy-1] == minNum:
                if sx < nextx : nextx, nexty, c = (sx, sy,count[sx-1][sy-1]); destx, desty = (dx, dy)
                elif sx == nextx and sy < nexty : nextx, nexty,c = (sx, sy,count[sx-1][sy-1]); destx, desty = (dx, dy)
            else: nextx, nexty, c = (sx, sy, count[sx-1][sy-1]); destx, desty = (dx, dy)
            minNum = count[sx-1][sy-1]
    return nextx, nexty, c, destx, desty

def go(nowx, nowy):
    global n, f, grid
    nowf = f
    while True:
        nextx, nexty, needf, destx, desty = findNext(nowx,nowy)
        if isDone() : break
        if nextx == 22 and nexty == 22 : return -1
        if nowf - needf < 0 : return -1
        nowf -= needf
        grid[nextx-1][nexty-1] = -1
        nowx, nowy = nextx, nexty
        needf = move(nowx,nowy,destx,desty,nowf)
        if needf == -1 : return -1
        else :
            nowf -= needf
            nowf += needf * 2
        nowx, nowy = destx,desty
    return nowf

n, m, f = map(int,input().split())
grid = [list(map(int,input().split())) for _ in range(n)]
tx, ty = map(int,input().split())
s = []; d = []
directions = (-1, 0), (0, -1), (1, 0), (0, 1) 
for i in range(m):
    temp = list(map(int, input().split()))
    s.append([temp[0],temp[1]])
    d.append([temp[2],temp[3]])
print(go(tx,ty))