[백준] 19238번 스타트 택시
문제 링크
https://www.acmicpc.net/problem/19238
문제 설명
- 택시 승객 태우고 데려다 주고 반복
- 한 칸에 1씩 연료 소모
- 데려다 주면 소모한 연료 * 2 충전
- 모두 데려다 줄 수 있으면 남은 연료 출력
- 아니면 -1 출력
풀이
- BFS로 가장 가까운 승객 찾기, 데려다 주기 반복
후기
- 지난번에도 같은 실수를 했던 것 같은데
- 상, 좌, 우, 하 순으로 BFS 돌면서 제일 처음 만나는 위치를 리턴했다.
- 이러면 반례가 발생한다ㅜ
코드
import sys
from collections import deque
def solution():
read = sys.stdin.readline
n, m, fuel = map(int, read().split())
board = [0]+[[0]+list(map(int, read().split())) for _ in range(n)]
ty, tx = map(int, read().split())
guests = dict()
for _ in range(m):
sy, sx, ey, ex = map(int, read().split())
guests[(sy, sx)] = {(ey, ex)}
possible = True
while guests:
# 최단 거리 승객 위치 찾기
dist, sy, sx = bfs(ty, tx, n, board, guests)
if dist > fuel:
possible = False
break
fuel -= dist
# 도착지 가기
dist, ey, ex = bfs(sy, sx, n, board, guests[(sy, sx)])
if dist > fuel:
possible = False
break
fuel -= dist
fuel += dist * 2
del guests[(sy, sx)]
ty, tx = ey, ex
if possible:
print(fuel)
else:
print(-1)
def bfs(sy, sx, n, board, dest):
guests = []
dy, dx = [-1,0,0,1], [0, -1, 1, 0]
visited = [[0]*(n+1) for _ in range(n+1)]
visited[sy][sx] = 1
q = deque([[sy, sx, 0]])
while q:
cy, cx, cd = q.popleft()
if (cy, cx) in dest:
guests.append([cd,cy,cx])
for d in range(4):
ny, nx = cy+dy[d], cx+dx[d]
if 1 <= ny <= n and 1 <= nx <= n:
if board[ny][nx] == 0 and not visited[ny][nx]:
visited[ny][nx] = 1
q.append([ny,nx,cd+1])
if guests:
guests.sort()
return guests[0]
return float('inf'), -1, -1
solution()
Author And Source
이 문제에 관하여([백준] 19238번 스타트 택시), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-19238번-스타트-택시
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- 지난번에도 같은 실수를 했던 것 같은데
- 상, 좌, 우, 하 순으로 BFS 돌면서 제일 처음 만나는 위치를 리턴했다.
- 이러면 반례가 발생한다ㅜ
코드
import sys
from collections import deque
def solution():
read = sys.stdin.readline
n, m, fuel = map(int, read().split())
board = [0]+[[0]+list(map(int, read().split())) for _ in range(n)]
ty, tx = map(int, read().split())
guests = dict()
for _ in range(m):
sy, sx, ey, ex = map(int, read().split())
guests[(sy, sx)] = {(ey, ex)}
possible = True
while guests:
# 최단 거리 승객 위치 찾기
dist, sy, sx = bfs(ty, tx, n, board, guests)
if dist > fuel:
possible = False
break
fuel -= dist
# 도착지 가기
dist, ey, ex = bfs(sy, sx, n, board, guests[(sy, sx)])
if dist > fuel:
possible = False
break
fuel -= dist
fuel += dist * 2
del guests[(sy, sx)]
ty, tx = ey, ex
if possible:
print(fuel)
else:
print(-1)
def bfs(sy, sx, n, board, dest):
guests = []
dy, dx = [-1,0,0,1], [0, -1, 1, 0]
visited = [[0]*(n+1) for _ in range(n+1)]
visited[sy][sx] = 1
q = deque([[sy, sx, 0]])
while q:
cy, cx, cd = q.popleft()
if (cy, cx) in dest:
guests.append([cd,cy,cx])
for d in range(4):
ny, nx = cy+dy[d], cx+dx[d]
if 1 <= ny <= n and 1 <= nx <= n:
if board[ny][nx] == 0 and not visited[ny][nx]:
visited[ny][nx] = 1
q.append([ny,nx,cd+1])
if guests:
guests.sort()
return guests[0]
return float('inf'), -1, -1
solution()
Author And Source
이 문제에 관하여([백준] 19238번 스타트 택시), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-19238번-스타트-택시
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
from collections import deque
def solution():
read = sys.stdin.readline
n, m, fuel = map(int, read().split())
board = [0]+[[0]+list(map(int, read().split())) for _ in range(n)]
ty, tx = map(int, read().split())
guests = dict()
for _ in range(m):
sy, sx, ey, ex = map(int, read().split())
guests[(sy, sx)] = {(ey, ex)}
possible = True
while guests:
# 최단 거리 승객 위치 찾기
dist, sy, sx = bfs(ty, tx, n, board, guests)
if dist > fuel:
possible = False
break
fuel -= dist
# 도착지 가기
dist, ey, ex = bfs(sy, sx, n, board, guests[(sy, sx)])
if dist > fuel:
possible = False
break
fuel -= dist
fuel += dist * 2
del guests[(sy, sx)]
ty, tx = ey, ex
if possible:
print(fuel)
else:
print(-1)
def bfs(sy, sx, n, board, dest):
guests = []
dy, dx = [-1,0,0,1], [0, -1, 1, 0]
visited = [[0]*(n+1) for _ in range(n+1)]
visited[sy][sx] = 1
q = deque([[sy, sx, 0]])
while q:
cy, cx, cd = q.popleft()
if (cy, cx) in dest:
guests.append([cd,cy,cx])
for d in range(4):
ny, nx = cy+dy[d], cx+dx[d]
if 1 <= ny <= n and 1 <= nx <= n:
if board[ny][nx] == 0 and not visited[ny][nx]:
visited[ny][nx] = 1
q.append([ny,nx,cd+1])
if guests:
guests.sort()
return guests[0]
return float('inf'), -1, -1
solution()
Author And Source
이 문제에 관하여([백준] 19238번 스타트 택시), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-19238번-스타트-택시저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)