일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 15686번
- 어른 상어
- 1789번
- 백준 알고리즘
- SW ExpertAcademy
- 보석 쇼핑
- 12869번
- HTML 기초
- 키패드 누르기
- SW Expert Academy
- python
- 빛의 경로 사이클
- 1038번
- 수식 최대화
- 프로그래머스
- 미세먼지 안녕!
- 파이썬
- 감소하는 수
- 19238번
- 9095번
- 거울 설치
- 12865번
- 2020 카카오 인턴십
- 베스트엘범
- 14499번
- QueryDSL 기초
- 16234번
- 경주로 건설
- 17144번
- 스타트 택시
Archives
- Today
- Total
보물창고 블로그
백준 알고리즘 19238번 스타트 택시 풀이 With Python 본문
728x90
문제 링크: https://www.acmicpc.net/problem/19238
19238번: 스타트 택시
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다
www.acmicpc.net
문제는 크게 2가지로 볼 수 있습니다. 첫 번째 문제는 현재 택시 위치에서 가장 가까운 손님을 태울 수 있는가? 태울 수 없다면 -1을 출력하고 태울 수 있다면 태울 손님의 위치와 연료를 계산하는 것입니다. 두 번째 문제는 손님을 태운 위치에서 목적지까지 손님을 태울 수 있는가? 없으면 -1을 출력하고 있다면, 손님을 목적지까지 태우고, 충전된 연료량을 계산하고 다시 첫 번째 문제로 돌아가는 것입니다. 저는 두 문제 모두 BFS(너비 우선 탐색)으로 해결하였습니다. 한 번에 연산하기 까다로워서 2개의 서브 함수로 문제를 해결하였습니다. 소스코드는 아래와 같습니다.
import sys
from collections import deque
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
def sub(bd, customer, sx, sy, fuel):
if customer.get((sx, sy)) is not None:
return sx, sy, fuel
queue = deque()
nque = deque()
point = []
visit = {(sx, sy): 1}
queue.append((sx, sy))
while 1:
while queue:
x, y = queue.popleft()
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if -1 < nx < n and -1 < ny < n and bd[nx][ny] == 0 and visit.get((nx, ny)) is None:
visit[(nx, ny)] = 1
if customer.get((nx, ny)) is not None:
point.append((nx, ny))
else:
nque.append((nx, ny))
fuel -= 1
if fuel < 0:
return -1, -1, -1
elif point:
if len(point) > 1:
point.sort()
return point[0][0], point[0][1], fuel
else:
queue = nque
nque = deque()
def sub2(bd, fuel, sx, sy, tx, ty):
if sx == tx and sy == ty:
return 0
queue = deque()
visit = {(sx, sy): 1}
queue.append((sx, sy, 0))
while queue:
x, y, count = queue.popleft()
if count > fuel:
return float('inf')
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if -1 < nx < n and -1 < ny < n and bd[nx][ny] == 0 and visit.get((nx, ny)) is None:
visit[(nx, ny)] = 1
if nx == tx and ny == ty:
return count + 1
queue.append((nx, ny, count + 1))
return float('inf')
answer = 0
n, m, fuel = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
gsx, gsy = map(int, sys.stdin.readline().split())
gsx -= 1
gsy -= 1
customer = {}
for _ in range(m):
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
customer[(x1 - 1, y1 - 1)] = [x2 - 1, y2 - 1]
while 1:
px, py, fuel = sub(board, customer, gsx, gsy, fuel)
if fuel < 0:
print(-1)
break
tx, ty = customer[(px, py)]
cal = sub2(board, fuel, px, py, tx, ty)
if cal > fuel:
print(-1)
break
else:
fuel += cal
del customer[(px, py)]
if not customer:
print(fuel)
break
gsx = tx
gsy = ty
첫 번째 문제를 구현한 것이 sub 함수이고, 두 번째 문제를 구현한 것이 sub2함수입니다. 소스코드에 대한 질문이 있으시면 댓글 남겨주시면 답변드리겠습니다.
'알고리즘 풀이 > 백준 알고리즘' 카테고리의 다른 글
백준 알고리즘 15686번 치킨 배달 풀이 With Python (0) | 2020.06.30 |
---|---|
백준 알고리즘 14499번 주사위 굴리기 풀이 With Python (0) | 2020.06.30 |
백준 알고리즘 19237번 어른 상어 풀이 With Python (0) | 2020.06.30 |
백준 알고리즘 19236번 청소년 상어 풀이 With Python (1) | 2020.06.30 |
백준 알고리즘 19235번 모노미도미노 풀이 With Python (6) | 2020.06.30 |
Comments