[ Baekjoon - 10/18 ] - 19238번: 스타트 택시

• 문제 링크 : https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

 

• 소요 시간 : 2시간

 

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 512MB
   • 문제
     
     • NxN의 지도(2≤N≤20), M명의 승객(1≤M≤N^2), 초기연료(1≤N≤500,000)
     • 지도의 크기및 상태가 주어지고 택시의 출발점, 각 승객의 출발지 도착지가 주어졌을때,
       주어진 연료를 사용하여 모든승객을 도착지로 데려다주고 남은 연료의 최댓값을 구하는 문제
   • 이해
     • 문제에서 주어진대로 그대로 구현하면 되는 문제이다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 문제의 입출력 형식과, 주어진 조건들을 수도코드?로 표현해 보았다.
3. 문제를 어떻게 해결할 것인가
   • 1st 접근 - BFS를 이용한 최단거리 구하기 )
     • 이 방법말고는 크게 생각나지 않았는데, 최단거리를 구할때 가장 자주쓰이는 알고리즘이기 때문이다.
     • 택시가 승객을 찾을때도 최단거리의 승객, 승객을 태워 목적지까지 이동할때도 최단거리이므로 두번 BFS를 이용해 해당 케이스마다 최단거리를 구해주면 답이된다!
4. 위 계획을 검증
   • 문제에서 주어진대로 수행했고, 완탐이라 생략하겠다.
5. 계획 수행 (실제코드 작성)
   1. Python 3

      1. from collections import deque
         
         dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
         
         def findPassengerStart(taxi):
             q = deque()
             q.append(taxi)
             visited = [[0] * N for _ in range(N)]
             minDistance = float('inf')
             passenger = []
             while q:
                 x,y = q.popleft()
                 if visited[x][y] > minDistance:
                     break
                 if [x,y] in passenger_start:
                     minDistance = visited[x][y]
                     passenger.append([x, y])
                 else:
                     for d in range(4):
                         nx, ny = x + dxy[d][0], y + dxy[d][1]
                         if 0 <= nx < N and 0 <= ny < N and board[nx][ny] != 1 and visited[nx][ny] == 0:
                             visited[nx][ny] = visited[x][y] + 1
                             q.append([nx, ny])
             if passenger:
                passenger.sort()
                return visited[passenger[0][0]][passenger[0][1]], passenger[0][0], passenger[0][1]
             else:
                return -1, -1, -1
         
         
         def findPassengerDesti(start, end):
             q = deque()
             q.append(start)
             visited = [[0] * N for _ in range(N)]
             while q:
                 x,y = q.popleft()
                 if [x,y] == end:
                     break
                 for d in range(4):
                     nx, ny = x + dxy[d][0], y + dxy[d][1]
                     if 0 <= nx < N and 0 <= ny < N and board[nx][ny] != 1 and visited[nx][ny] == 0:
                         visited[nx][ny] = visited[x][y] + 1
                         q.append([nx, ny])
             return visited[x][y], x, y
         
         
         if __name__ == "__main__":
             N, M, fuel = map(int, input().split())
             board = [list(map(int, input().split())) for _ in range(N)]
             intialX, initialY = map(int, input().split())
             taxi = [intialX - 1, initialY - 1]
         
             passenger_start = []
             passenger_end = []
             for _ in range(M):
                 sx, sy, ex, ey = map(int, input().split())
                 passenger_start.append([sx - 1, sy - 1])
                 passenger_end.append([ex - 1, ey - 1])
         
             for _ in range(M):
                 #1.현재 택시위치로부터 가장 가까운 승객의 출발지를 찾기
                 distS, sx, sy = findPassengerStart(taxi)
                 # 승객에게 도달 불가 or 연료부족일때
                 if distS == -1 or fuel < distS:
                     fuel = -1
                     break
                 # 도달 가능하다면 연료 -, 승객은 택시에 탔으니, 해당승객의 출발지 제거
                 fuel -= distS
                 idx = passenger_start.index([sx, sy])
                 passenger_start[idx] = [-1, -1]
         
                 #2. 승객의 출발지로부터 도착지까지 최단경로
                 distD, dx, dy = findPassengerDesti([sx, sy], passenger_end[idx])
                 # 목적지에 도달 불가 or 연료부족일때
                 if [dx, dy] != passenger_end[idx] or fuel < distD:
                     fuel = -1
                     break
                 # 도달 가능하다면 연료 쓴만큼 +, 택시 위치 갱신
                 fuel += distD
                 taxi = [dx, dy]
         
             print(fuel)

• 결과